Diziler ve Bağlı Listeler
Diziler ve bağlı listeler, sıralı bir eleman dizisini depolamanın iki temel yoludur: diziler, sabit zamanlı indeksli erişim için elemanları bitişik belleğe yerleştirirken, bağlı listeler, ucuz ekleme ve silme işlemleri için onları işaretçiler aracılığıyla zincirler.
Tanım
Bir dizi, elemanları konumlarına göre indekslenmiş bitişik bellek konumlarında depolar ve sabit zamanlı rastgele erişime olanak tanır; bir bağlı liste ise, her biri bir sonraki (ve muhtemelen önceki) düğüme referans tutan ayrı düğümlerde elemanları depolar ve bir düğüm referansı verildiğinde sabit zamanlı ekleme veya çıkarmaya olanak sağlar.
Kapsam
Bu konu, doğrusal, dizi tabanlı yapıları ve bunlar üzerine inşa edilen soyut veri tiplerini — statik ve dinamik diziler, tek ve çift yönlü bağlı listeler ile yığın ve kuyruk ADT'lerini — kapsamaktadır. Erişim, ekleme ve silme maliyetlerini karşılaştırmakta, dinamik dizi yeniden boyutlandırmasını ve bunun amortize analizini ele almakta, ayrıca önbellek yerelliği gibi bellek düzeni sonuçlarını açıklamaktadır. Karma tablolar ve arama ağaçları altında ele alınan ilişkisel ve hiyerarşik yapılar bu kapsamın dışındadır.
Temel sorular
- Bitişik (dizi) depolama, işaretçi bağlantılı (liste) depolamadan ne zaman daha iyi performans gösterir?
- Dinamik bir dizi, ara sıra yeniden boyutlandırmaya rağmen amortize edilmiş sabit zamanlı eklemeyi nasıl başarır?
- Ekleme, silme ve erişim için diziler ve bağlı listeler arasındaki maliyet takasları nelerdir?
- Yığınlar ve kuyruklar bu yapılar üzerine nasıl uygulanır?
- Bellek düzeni, önbellek davranışı aracılığıyla gerçek dünya performansını nasıl etkiler?
Anahtar kavramlar
- bitişik bellek
- indeksli erişim
- dinamik dizi yeniden boyutlandırma
- tek ve çift yönlü bağlı listeler
- yığınlar (LIFO)
- kuyruklar (FIFO)
- amortize maliyet
- önbellek yerelliği
Temel kuramlar
- Rastgele erişim ve sıralı bağlantı
- Diziler O(1) indeksli erişimi destekler ancak ortada O(n) ekleme veya silme maliyeti vardır; bağlı listeler ise bir düğüm verildiğinde O(1) birleştirme/ayırma işlemini destekler ancak konuma göre erişim O(n) maliyetlidir; doğru seçim, işlem karışımına bağlıdır.
- Dinamik dizilerin amortize edilmiş büyümesi
- Dolu olduğunda kapasitesini iki katına çıkaran dinamik bir dizi, ara sıra O(n) kopyalama işlemleri gerçekleştirir ancak herhangi bir işlem dizisi boyunca ekleme başına O(1) amortize maliyetle çalışır; bu, toplam veya potansiyel yöntemle analiz edilir.
Klinik önem
Diziler ve listeler, hemen hemen her programın temelini oluşturmaktadır: dinamik diziler çoğu dildeki varsayılan liste/vektör tiplerini uygulamakta, kuyruklar zamanlama ve genişlik öncelikli aramanın temelini oluşturmakta, yığınlar fonksiyon çağrı yönetimini ve ifade değerlendirmesini desteklemekte ve dizi-liste takas dengesi, performansı etkileyen rutin bir pratik tasarım kararıdır.
Tarihçe
Diziler, ilk programlama dillerinde mevcut olan en eski veri yapılarından biridir ve bağlı listeler, 1950'lerin sonlarında sembolik ve liste işleme (özellikle Newell, Shaw ve Simon'ın IPL'sinde ve daha sonra Lisp'te) için tanıtılmıştır. Knuth'un Bilgisayar Programlama Sanatı (The Art of Computer Programming) adlı eserindeki sistematik ele alışı, bunların kanonik analizini oluşturmuştur.
Öne çıkan isimler
- Donald Knuth
- Robert Sedgewick
İlgili konular
Temel eserler
- knuth1997vol1
- cormen2009
Sıkça sorulan sorular
- Diziler hızlı rastgele erişimi destekliyorsa neden bağlı liste kullanılmalıdır?
- Bağlı listeler, bir düğüme referans verildiğinde diğer elemanları kaydırmadan sabit zamanda ekleme veya silme işlemine izin verir ki diziler bunu ortada yapamaz. Dizi sık sık değiştiğinde ve konumsal rastgele erişime ihtiyaç duyulmadığında kullanışlıdırlar.
- Yeniden boyutlandırma her şeyi kopyalıyorsa dizi eklemeleri neden sabit zamanlı kabul edilir?
- Yeniden boyutlandırma nadiren gerçekleşir çünkü kapasite genellikle iki katına çıkar, bu nedenle n ekleme üzerindeki toplam kopyalama işi n ile orantılıdır. Tüm eklemelere yayıldığında, bireysel yeniden boyutlandırmalar O(n) olsa bile, bu ekleme başına amortize edilmiş sabit bir maliyet sağlar.