Diziler ve Bağlantılı Listeler
Diziler, öğelerin koleksiyonunu depolamak için en yaygın kullanılan veri yapısıdır. Çoğu programlama dili, dizileri kolayca bildirmek ve dizilerdeki öğelere erişmek için yöntemler sağlar. Bağlantılı liste, daha doğrusu tek bağlantılı liste, aynı zamanda, öğelerin koleksiyonunu depolamak için kullanılabilecek bir veri yapısıdır. Bir dizi düğümden oluşur ve her düğümün dizideki bir sonraki düğüme bir referansı vardır.
Şekil 1'de gösterilen, tipik olarak bir diziye değer bildirmek ve atamak için kullanılan bir kod parçasıdır. Şekil 2, bir dizinin bellekte nasıl görüneceğini gösterir.
Yukarıdaki kod, 5 tamsayı depolayabilen bir diziyi tanımlar ve bunlara 0 ila 4 arasındaki indeksler kullanılarak erişilir. Bir dizinin önemli bir özelliği, tüm dizinin tek bir bellek bloğu olarak tahsis edilmesi ve her öğenin kendi alanına sahip olmasıdır. dizide. Bir dizi tanımlandıktan sonra boyutu sabitlenir. Bu nedenle, derleme zamanında dizinin boyutundan emin değilseniz, güvenli tarafta olmak için yeterince büyük bir dizi tanımlamanız gerekir. Ancak çoğu zaman aslında ayırdığımızdan daha az sayıda eleman kullanacağız. Yani hatırı sayılır miktarda bellek aslında boşa harcanıyor. Öte yandan, "yeterince büyük dizi" aslında yeterince büyük değilse, program çökecektir.
Bağlantılı bir liste, belleği kendi bloğundaki öğelerine ayrı ayrı tahsis eder ve bu öğelerin bir zincirdeki halkalar olarak bağlanmasıyla genel yapı elde edilir. Bağlantılı listedeki her öğe, Şekil 3'te gösterildiği gibi iki alana sahiptir. Veri alanı, depolanan gerçek verileri tutar ve sonraki alan, zincirdeki bir sonraki öğeye yapılan referansı tutar. Bağlantılı listenin ilk öğesi, bağlantılı listenin başı olarak depolanır.
| veri | sonraki |
Şekil 3: Bağlantılı Liste Öğesi
Şekil 4, üç elemanlı bağlantılı bir listeyi göstermektedir. Her öğe kendi verilerini depolar ve sonuncusu dışındaki tüm öğeler bir sonraki öğeye bir referans depolar. Son öğe, sonraki alanında boş bir değer tutar. Listedeki herhangi bir öğeye, baştan başlayarak ve gerekli öğeyi karşılayana kadar sonraki işaretçiyi izleyerek erişilebilir.
Diziler ve bağlantılı listeler, her ikisinin de öğe koleksiyonunu depolamak için kullanılması anlamında benzer olsa da, öğelerine bellek ayırmak için kullandıkları stratejiler nedeniyle farklılıklara neden olurlar. Diziler, tüm öğelerine tek bir blok olarak bellek ayırır ve dizinin boyutu çalışma zamanında belirlenmelidir. Bu, derleme zamanında dizinin boyutunu bilmediğiniz durumlarda dizileri verimsiz hale getirir. Bağlantılı bir liste, öğelerine ayrı ayrı bellek ayırdığından, derleme zamanında listenin boyutunu bilmediğiniz durumlarda çok verimli olacaktır. Bağlantılı bir listedeki öğelere bildirim ve erişim, dizinlerini kullanarak bir dizideki öğelere doğrudan nasıl eriştiğinize kıyasla doğrudan doğruya olmaz.
