--- title: 'Dinamik Diziler' source: 'https://academia.sh/tr/kurslar/veri-yapilari/dinamik-diziler' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:56+00:00' license: 'CC BY-SA 4.0' --- # Dinamik Diziler Kapasite büyütme, büyütme çarpanının seçimi, amortize maliyet çözümlemesi ve küçülme eşiği. Önceki ders, dizinin sabit boyutlu bir bitişik blok olduğunu ve bu bloğun sonradan büyütülemediğini kurdu. Eleman sayısı önceden bilinmediğinde bu kısıt bağlayıcıdır. Çözüm, kısıtı ortadan kaldırmak değil, onunla yaşamaktır: dizi dolduğunda daha büyük yeni bir dizi ayrılır, eski elemanlar oraya kopyalanır ve eski blok bırakılır. Bu yapıya **dinamik dizi (dynamic array)** denir. ## Kapasite ve Uzunluk Dinamik dizi iki sayı tutar: - **Uzunluk:** İçindeki gerçek eleman sayısı. - **Kapasite:** Ayrılmış bloğa sığabilecek en fazla eleman sayısı. Kapasite her zaman uzunluğa eşit veya ondan büyüktür. Aradaki fark, henüz kullanılmayan ama ayrılmış olan yerdir; sona ekleme bu boşluğu kullandığı sürece ucuzdur. Uzunluk kapasiteye ulaştığında **yeniden ayırma** gerekir: yeni ve daha büyük bir blok ayrılır, tüm elemanlar kopyalanır. Kopyalama, eleman sayısıyla orantılıdır — yani $O(n)$. ## Büyütme Çarpanı Kritik soru şudur: yeni kapasite ne kadar olmalıdır? **Sabit miktarda büyütme** — her seferinde kapasiteye sabit bir sayı eklemek — kötü bir seçimdir. Kapasite birer birer artırılsaydı, $n$ eleman eklemek için yapılan toplam kopyalama şu olurdu: $$ 1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2} $$ Bu, $O(n^2)$ demektir: bin eleman eklemek yaklaşık yarım milyon kopyalama yapar. **Katlayarak büyütme** — kapasiteyi her defasında bir çarpanla (yaygın olarak iki ile) çarpmak — toplam maliyeti kökten değiştirir. Kapasite $1$'den başlayıp ikiye katlanıyorsa, $n$ elemana ulaşana kadar yapılan kopyalamaların toplamı: $$ 1 + 2 + 4 + \dots + \frac{n}{2} < n $$ Geometrik toplamın kendisi, son terimin iki katından küçüktür. Yani $n$ ekleme için toplam kopyalama sayısı $n$'den azdır; ekleme başına düşen ortalama maliyet **sabittir**. ## Amortize Maliyet Bu gözlem bir kavramı gerektirir. Tek tek bakıldığında sona ekleme işlemlerinin çoğu $O(1)$, bazıları $O(n)$'dir; en kötü durum maliyeti doğrusaldır. Ancak pahalı işlemler seyrektir ve her pahalı işlemden sonra kapasite iki katına çıktığı için bir sonraki pahalı işleme kadar iki kat daha fazla ucuz işlem yapılır. Bir işlem dizisinin **toplam** maliyetini işlem sayısına bölerek elde edilen değere **amortize maliyet** denir. Dinamik dizide sona eklemenin amortize maliyeti $O(1)$'dir. Bu, "her ekleme sabit sürer" demek değildir; "$n$ ekleme toplamda $O(n)$ sürer" demektir. Ayrım, gecikmeye duyarlı sistemlerde önem kazanır: tek bir eklemenin uzun sürebileceği bilinmelidir. ```python class DinamikDizi: """Kapasitesini ikiye katlayarak büyüyen dizi.""" def __init__(self) -> None: self._blok: list = [None] # kapasite 1 ile başlar self._uzunluk = 0 self.kopyalama = 0 # ölçüm için sayaç def __len__(self) -> int: return self._uzunluk def kapasite(self) -> int: return len(self._blok) def ekle(self, deger: int) -> None: if self._uzunluk == self.kapasite(): self._buyut() self._blok[self._uzunluk] = deger self._uzunluk += 1 def _buyut(self) -> None: yeni = [None] * (self.kapasite() * 2) for i in range(self._uzunluk): # her eleman yeni bloğa taşınır yeni[i] = self._blok[i] self.kopyalama += 1 self._blok = yeni def __getitem__(self, i: int) -> int: if not 0 <= i < self._uzunluk: raise IndexError("dizin aralık dışında") return self._blok[i] dizi = DinamikDizi() for deger in range(16): dizi.ekle(deger) print(len(dizi), dizi.kapasite()) # 16 16 print(dizi.kopyalama) # 15 — toplam kopyalama, eleman sayısından az print(dizi[3]) # 3 ``` On altı ekleme için yapılan kopyalama sayısı $1 + 2 + 4 + 8 = 15$'tir. Ekleme başına ortalama bir kopyalamadan az; geometrik toplamın verdiği sınır sayımla doğrulanmıştır. Bu sayım, amortize çözümlemenin en sade biçimidir: her ekleme kendi maliyetinin yanında ileride yapılacak kopyalama için bir pay biriktirir; yeniden ayırma geldiğinde bu birikmiş paylar maliyeti karşılar. Çarpanın iki olması zorunlu değildir. Daha küçük bir çarpan (örneğin $1{,}5$) daha az boş yer bırakır ama daha sık kopyalar; daha büyük çarpan tersini yapar. Her iki durumda da amortize maliyet sabit kalır — değişen, sabit çarpanın büyüklüğüdür. ## Önceden Ayırma Eleman sayısı önceden biliniyorsa, büyüme hiç yaşanmayabilir. Çoğu dinamik dizi gerçekleştirimi, kapasiteyi baştan belirlemeye izin veren bir işlem sunar. Kazanç iki yönlüdür. Yeniden ayırma ve kopyalama tümüyle ortadan kalkar; ve ayrılan blok tek parça olduğu için bellek parçalanması azalır. Bin elemanlık bir sonucun üretileceği biliniyorsa, kapasitenin baştan bin verilmesi on yeniden ayırmayı önler. ```python sonuc = [] # Kapasite baştan bilinen durumda, dilin sunduğu ön ayırma kullanılır. # Ön ayırma yoksa, sonucu doğrudan hedef boyutta üretmek aynı işi görür: hazir = [0] * 1000 # tek ayırma, kopyalama yok for i in range(1000): hazir[i] = i * 3 print(len(hazir), hazir[999]) # 1000 2997 ``` Bu, erken eniyileme değildir: son boyutun bilindiği durumlarda ön ayırma, kodun okunabilirliğini de artırır — niyet açıkça yazılmış olur. ## Küçülme ve Salınım Elemanlar silindiğinde kapasitenin de düşürülmesi beklenir; aksi hâlde bir kez büyüyen dizi belleği bırakmaz. Küçültme eşiği dikkatle seçilmelidir. Kapasite, uzunluk kapasitenin yarısına indiğinde yarıya düşürülürse **salınım** oluşur: dizi tam sınırdayken art arda yapılan bir ekleme ve bir silme, her seferinde yeniden ayırma tetikler. Her işlem $O(n)$ olur ve amortize kazanç yok olur. Standart çözüm, eşikleri ayırmaktır: kapasite dolduğunda ikiye katlanır, ancak yalnızca uzunluk kapasitenin **dörtte birine** indiğinde yarıya düşürülür. Aradaki boşluk, sınırda gidip gelen işlemlerin yeniden ayırma tetiklemesini engeller. ## Gerçek Dillerdeki Karşılığı Çoğu dilin standart "liste" veya "vektör" yapısı, bir dinamik dizidir. Sona ekleme amortize sabit, başa ekleme doğrusaldır; bu asimetri, kod yazarken hangi ucun kullanılacağını belirler. Bir ayrıntı, elemanların ne saklandığıdır. Sabit genişlikli tipler doğrudan blokta tutulabilir; nesne referansları saklandığında ise blok işaretçiler taşır ve gerçek değerler öbekte dağınık durur. İkinci düzen esneklik verir, önbellek uyumunu düşürür. Bilgisayarlar Nasıl Çalışır kursundaki bitişik yerleşim tartışması bu ayrımı içeriyordu. ## Maliyet Tablosu | Yapı | Erişim | Arama | Başa ekleme | Sona ekleme | Ortadan silme | |---|---|---|---|---|---| | Dizi (sabit boyut) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ | | Dinamik dizi | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortize | $O(n)$ | \* Yer kaldığı sürece. ## Özet - Dinamik dizi, dolduğunda daha büyük bir blok ayırıp elemanları kopyalayarak sabit boyut kısıtını aşar. - Kapasite ayrılmış yeri, uzunluk gerçek eleman sayısını gösterir. - Sabit miktarda büyütme toplam maliyeti $O(n^2)$ yapar; katlayarak büyütmede toplam kopyalama $n$'den azdır. - Amortize maliyet, bir işlem dizisinin toplam maliyetinin işlem sayısına bölünmesidir; sona eklemenin amortize maliyeti sabittir, tek bir eklemeninki değildir. - Küçültme eşiği büyütme eşiğinden ayrı seçilir; aksi hâlde sınırdaki işlemler salınım üretir. ## Sonraki Adım Dinamik dizi, sona eklemeyi ucuzlattı ama başa ve ortaya ekleme hâlâ doğrusal. Kaydırma maliyetinin kaynağı bitişik yerleşimdi. Sonraki ders, bitişikliği tümüyle terk eden bir yapıyı — bağlı listeyi — ve bu değiş tokuşun neyi kazanıp neyi kaybettirdiğini ele alacak.