--- title: Diziler source: 'https://academia.sh/tr/kurslar/veri-yapilari/diziler' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:55+00:00' license: 'CC BY-SA 4.0' --- # Diziler Bitişik bellek yerleşimi, adres aritmetiğiyle sabit zamanlı erişim, sabit boyut kısıtı ve maliyet dili. Programlama Temelleri kursunda listeler kullanıldı: elemanlar eklendi, gezildi, süzüldü. Bu işlemlerin bellekte neye karşılık geldiği ve neden bazılarının diğerlerinden pahalı olduğu açık bırakıldı. Bu kurs o boşluğu doldurur. Sorusu şudur: veri bellekte nasıl düzenlenirse hangi işlem ucuz, hangisi pahalı olur? Yanıt her seferinde aynı iki kaynaktan gelir — Bilgisayarlar Nasıl Çalışır kursunda kurulan bellek modeli ve yapının kendi düzeni. ## Bitişik Yerleşim **Dizi (array)**, aynı tipteki elemanları bellekte **bitişik** tutan yapıdır. İlk elemanın adresi biliniyorsa, diğerlerinin adresi hesaplanabilir: $$ \text{adres}(i) = \text{taban} + i \times \text{eleman boyutu} $$ Dört baytlık tam sayılardan oluşan bir dizi `1000` adresinden başlıyorsa, üçüncü elemanın adresi $1000 + 3 \times 4 = 1012$'dir. Hesap tek bir çarpma ve bir toplamadır; dizinin uzunluğundan bağımsızdır. Bu, dizinin ayırt edici özelliğidir: **herhangi bir elemana, sırasını bilerek doğrudan erişilir.** Beşinci elemana ulaşmak için önceki dördünün üzerinden geçmek gerekmez. Yerleşimin ikinci sonucu, dizinin tek tip eleman taşımasıdır. Adres aritmetiği, elemanların eşit boyutta olmasına dayanır; farklı boyutlarda elemanlar bitişik dizilseydi $i$'nci elemanın yeri hesaplanamaz, aranması gerekirdi. ## Maliyet Dili Bu kurs boyunca işlemlerin maliyeti karşılaştırılacaktır. Karşılaştırma için üç ifade yeterlidir; biçimsel tanımları **Algoritmalar** kursunda verilir. - **Sabit zaman**, $O(1)$: İşin süresi veri büyüklüğünden bağımsızdır. Dizinin $i$'nci elemanına erişim böyledir. - **Doğrusal zaman**, $O(n)$: Süre, eleman sayısıyla orantılı büyür. Bir diziyi baştan sona taramak böyledir. - **Logaritmik zaman**, $O(\log n)$: Her adımda arama alanı sabit bir oranda küçülür. Sıralı bir dizide ikili arama böyledir. Gösterim, sabit çarpanları ve düşük dereceli terimleri yok sayar; ölçtüğü şey, veri büyüdükçe maliyetin **hangi hızla** arttığıdır. ## Dizinin İşlem Maliyetleri | İşlem | Maliyet | Gerekçe | |---|---|---| | $i$'nci elemana erişim | $O(1)$ | Adres aritmetiği | | Sıralı olmayan dizide arama | $O(n)$ | En kötü durumda tüm elemanlar | | Sıralı dizide arama | $O(\log n)$ | Her adımda aralık yarılanır | | Sona ekleme (yer varsa) | $O(1)$ | Tek yazma | | Başa veya ortaya ekleme | $O(n)$ | Sonraki elemanların kaydırılması | | Ortadan silme | $O(n)$ | Boşluğun kapatılması | Ekleme ve silmenin pahalı olması, bitişik yerleşimin doğrudan bedelidir. Beş elemanlı bir dizinin başına eleman eklemek, var olan beş elemanın her birini bir sıra ileri taşımayı gerektirir; yerleşim bitişik kalmalıdır, çünkü adres aritmetiği buna dayanır. ```python def basa_ekle(dizi: list[int], deger: int) -> int: """Diziyi bir sıra kaydırarak başa ekler; kaydırılan eleman sayısını döndürür.""" dizi.append(None) # sona yer aç kaydirma = 0 for i in range(len(dizi) - 1, 0, -1): # sondan başa doğru kaydır dizi[i] = dizi[i - 1] kaydirma += 1 dizi[0] = deger return kaydirma olcumler = [12, 18, 7, 25, 14] print(basa_ekle(olcumler, 30)) # 5 — beş eleman kaydırıldı print(olcumler) # [30, 12, 18, 7, 25, 14] ``` Kaydırma sayısı, dizinin uzunluğuna eşittir; bu, tablodaki $O(n)$ satırının sayımla gösterilmiş hâlidir. ## Sabit Boyut Kısıtı Klasik bir dizi, yaratıldığı anda boyutu belirlenen bir bellek bloğudur. Blok bitişik olduğundan, sonradan büyütmek genellikle mümkün değildir: dizinin hemen ardındaki bellek başka bir veri tarafından kullanılıyor olabilir. Bu kısıtın iki sonucu vardır. Gereğinden büyük ayrılan dizi bellek israfıdır; küçük ayrılan dizi ise dolduğunda kullanılamaz hâle gelir. Programın kaç eleman tutacağı önceden bilinmiyorsa, sabit boyutlu dizi doğrudan çözüm değildir. Sonraki dersin konusu, tam olarak bu kısıtın nasıl aşıldığıdır. ## Dizin Denetimi Adres aritmetiği, verilen dizinin geçerli olduğunu varsayar. Dizin aralık dışındaysa hesaplanan adres, dizinin dışındaki bir bellek konumunu gösterir. Diller bu duruma iki farklı yanıt verir. **Denetim yapanlar**, her erişimde dizini sınır ile karşılaştırır ve aşımda hata üretir; bedeli, erişim başına birkaç komuttur. **Denetim yapmayanlar** hesabı doğrudan uygular; erişim en hızlı hâlindedir, ancak aralık dışı bir dizin, komşu verinin okunmasına veya üzerine yazılmasına yol açar. İkinci davranış, Bilgisayarlar Nasıl Çalışır kursunda tanımsız davranış başlığı altında geçmişti. Sonucu yalnızca yanlış değer değildir: dizinin dışına yazmak, çağrı çerçevesindeki dönüş adresini bozabilir. Bu, bellek güvenliği açıklarının en bilinen sınıfıdır ve siber güvenlik müfredatında ayrıca ele alınır. ## Çok Boyutlu Diziler İki boyutlu bir dizi de bellekte tek boyutlu olarak durur; satırlar art arda yerleştirilir. Buna **satır öncelikli yerleşim** denir ve dizin hesabı şöyle olur: $$ \text{konum}(i, j) = i \times \text{sütun sayısı} + j $$ ```python SUTUN = 4 duz = [0] * (3 * SUTUN) # 3 satır, 4 sütunluk tablo tek dizide def yaz(i: int, j: int, deger: int) -> None: duz[i * SUTUN + j] = deger def oku(i: int, j: int) -> int: return duz[i * SUTUN + j] yaz(1, 2, 99) print(oku(1, 2), duz) # 99 [0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0] ``` `99` değerinin düz dizide altıncı konumda ($1 \times 4 + 2$) durması, iki boyutun tek boyuta nasıl indirildiğini gösterir. Bu yerleşimin başarım sonucu, Bilgisayarlar Nasıl Çalışır kursunun önbellek dersinde hesaplanmıştı: satır boyunca gezinme ardışık adresleri okur, sütun boyunca gezinme her adımda bir satır uzunluğu atlar. Aynı sayıda toplama için taşınan veri miktarı, önbellek satırına sığan eleman sayısı kadar farklıdır. ## Diziler Neden Yaygın Dizinin ekleme ve silme maliyetleri yüksek olmasına karşın, pratikte en sık kullanılan yapı olmasının üç nedeni vardır. **Erişim maliyeti en düşüktür.** Sabit zamanlı ve tek bir adres hesabı kadar ucuzdur. **Önbellek davranışı en iyisidir.** Bitişik yerleşim, uzamsal yerellikten en çok yararlanan düzendir; bir eleman getirildiğinde komşuları da önbelleğe girer. **Ek yer tutmaz.** Bağlantılı yapıların aksine, eleman başına işaretçi saklanmaz. Bu üç nedenle, "hangi yapı" sorusunun varsayılan yanıtı dizidir; başka bir yapı, ancak dizinin zayıf olduğu bir işlem baskınsa seçilir. Bu kursun geri kalanı, o durumların neler olduğunu ve hangi yapının hangi maliyeti düşürdüğünü gösterir. ## Maliyet Tablosu Kurs boyunca aşağıdaki tablo satır satır büyüyecektir. İlk satır bu dersin sonucudur: | Yapı | Erişim | Arama | Başa ekleme | Sona ekleme | Ortadan silme | |---|---|---|---|---|---| | Dizi (sabit boyut) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ | \* Yer kaldığı sürece; dizi dolduğunda ekleme yapılamaz. ## Özet - Dizi, aynı tipteki elemanları bitişik tutar; $i$'nci elemanın adresi taban adres ve eleman boyutundan hesaplanır. - Bu hesap dizinin uzunluğundan bağımsız olduğu için erişim sabit zamanlıdır. - Ekleme ve silme, bitişikliği korumak için eleman kaydırmayı gerektirir ve doğrusal zamanlıdır. - Sabit boyut kısıtı, bitişik bloğun sonradan büyütülememesinden doğar. - Çok boyutlu diziler bellekte tek boyutlu durur; satır öncelikli yerleşim, gezinme yönünün önbellek davranışını belirlemesine yol açar. - Erişim maliyeti, önbellek uyumu ve ek yer tutmaması nedeniyle dizi, varsayılan seçimdir. ## Sonraki Adım Sabit boyut kısıtı, eleman sayısı önceden bilinmeyen problemlerde diziyi kullanılamaz kılıyor. Sonraki ders, diziyi taşımaya dayalı bir çözümle bu kısıtı kaldıracak ve bu çözümün maliyetinin neden göründüğü kadar yüksek olmadığını — amortize maliyet kavramıyla — gösterecek.