Dinamik dizi

Bellek tahsisi yaparken geometrik artırma yöntemi kullanılarak dinamik dizinin sonuna eleman ekleniyor. Boş kutular uzatılmış belleği ifade ediyor. Eklemeler sabit zamanlı (Θ(1)) ancak ekleme kapasitenin sonuna denk geldiğinde yeniden bellek tahsisi gerektirdiğinden yavaş (Θ(n) zaman) kalıyor (kaplumbağa ile gösterilmiştir). Dizinin boyu (logical size) ve kapasitesi (capacity) sonda gösterilmiştir.

Dinamik dizi, tutabileceği eleman sayısının derleme zamanında bilinmesine gerek olmayan dizidir. Dinamik dizi tanımlandığında, kapasitesini belirten bir bellek tahsis edilir ve kullanımda kapasiteye erişildiğinde yeniden bir dinamik bellek tahsisi yapılır. Dinamik diziye elemanlar eklenebilir, diziden elemanlar silinebilir; dizinin boyutu azaltılabilir ve arttırılabilir. Bazı programlama dillerinde vektör adıyla anılan bu yapıyı birçok modern programlama dili kendi kütüphaneleriyle sunmaktadır.

Diziler ve sabit boyutun dezavantajları

İdeal veri yapılarının ortak özelliği değiştirilebilir ve esnek olmasıdır. İyi bir kullanıcının kullanacağı veri yapısı da bu özellikleri sağlamalıdır. Programlamanın temel veri yapısı olan diziler sabit boyutlu olmaları nedeniyle bu yeterliliğe erişememektedir. Bu sebeple programlama dillerinin gelişmesiyle paralel olarak farklı özelliklere ve esnekliklere sahip veri yapıları ortaya sunulmuş, kullanılmıştır.

Bazı kod dizilerinde sabit boyutlu bir dizi ihtiyacı karşılasa da bazı durumlarda yetersiz kalmaktadır. Kullanılacak veri sayısının belirsiz olması ya da önceden saptanamaması bu noktadaki temel problemdir. Bu probleme çözüm olarak klasik fakat verimsiz bir çözüm yolu sunulmaktadır. Bu çözüm yolu, ihtiyaç duyulandan daha fazla ya da anormal büyük boyutta bir dizi tanımlamaktır. Kimi zaman çözüm yolu olarak seçilen bu yöntem dizilerin yetersiz olması durumunu değiştirmemektedir. Çünkü, sabit boyuttaki bir dizinin bu boyutuna sığmayacak sayıda veri içermesi gerekliliği hiçbir zaman önceden saptanamaz. Diğer bir taraftan da bu çözüm yolu kod dizisinin çalışmak için ihtiyaç duyacağı hafıza miktarını arttıracaktır. Bu da kod dizisini hantallaştırmakla beraber çalışabilirliğini de düşürmektedir.

Çalışma şekli

Dinamik dizilerdeki ekleme ve silme işlemlerinin temel mantığı dizilerdeki gibidir. Aradaki farklılık sabit boyutlu bir dizinin kapasitesi dolduğunda yeni veri ekleme işleminin hata ile sonuçlanması, dinamik dizilerde ise aynı işlemin yeni bellek tahsisi kullanılarak başarılı olmasıdır.

En basit dinamik dizi yapısında arka planda çalışan iki dizi kullanılmaktadır. Bunlardan ilki veriyi tutmaktadır, ikincisi ise tampon bölge olarak görev yapmaktadır. Birinci bölge oluşturulduğunda dizi yeni oluşturulan daha büyük boyutlu bir diziye kopyalanarak ilk dizi silinmektedir.

Sınır durumdaki ekleme işlemi hakkında bir irdeleme yapılmalı ve dinamik dizinin ne zaman genişletilmesi gerektiğine çok iyi karar verilmelidir. Çünkü genişletme, eklemeye göre daha masraflı bir işlemdir. Birkaç elemandan oluşan dizilerde bu masraf göz ardı edilebilecek kadar düşük bir maliyette olsa da dizinin eleman sayısı arttıkça bu maliyette artmaktadır.

Performans

Operasyon	Bağlı liste	Dizi	Dinamik dizi
Erişim ve güncelleme	Θ(n)	Θ(1)	Θ(1)
Ekleme	Θ(1)	Θ(1)	Θ(1)
Genişleme gerektiren ekleme	Θ(1)	-	Θ(n)
Gereksiz hafıza kullanımı	0	Θ(n)	Θ(n)

Dinamik diziler performans olarak dizilere benzer performans gösterseler de genişleme durumlarındaki eklemelerde maliyet üst seviyelere varmaktadır.

• Dizi içindeki bir elemana ulaşma ya da elemanı değiştirme performansı sabittir (Θ(1)).
• Ekleme işlemi de aynı performanstadır ve sabittir (Θ(1)).
• Genişleme gerektiren ekleme ise dizi içerisindeki eleman sayısına bağlı olarak artan bir performansa sahiptir (Θ(n)).
• Gereksiz hafıza kullanımı genişlemeden önceki durumda minimumdur, diğer durumlarda yüksektir.

Dizilere bakarak erişim, güncelleme, ekleme açısından aynı performanstadır. Genişleme gerektiren ekleme yüksek maliyete sahiptir.

Bağlı listelerle kıyaslandığında ise erişim ve güncelleme daha hızlıdır. Genişleme gerektiren ekleme daha yüksek bi maliyete sahiptir. Bağlı listelerde sıfır olan gereksiz hafıza kullanımı dinamik dizilerde yüksektir.

Diller ve dinamik diziler

• C ve pascal dilinde dinamik dizi sağlanmamaktadır. Fakat kullanıcı bunu simüle edebilir.
• C++ dilindeki std::vector dinamik dizi implementasyonu sağlar.
• C# dilinde List<> sınıfı dizi kullanımı sağlar.
• Delphi ve D dilleri dinamik dizi kullanımı sağlamaktadır.
• Java dilinde dinamik diziler, java.util paketinde bulunan Vector ve ArrayList sınıfları tarafından sağlanır.
• Python list yapısını sağlar.
• Rust std::vec::Vec yapısını sağlar.

Kaynakça

• Veri Yapıları ve Algoritma, M.Ümit Karakaş, Beta Basım Yayın, 2000
• Algoritma Geliştirme ve Veri Yapıları, Bülent Çobanoğlu, Pusula Yayıncılık, 2008
• Data Structures and Algorithms, Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft, Addison-Wesley, 2005