Doğrusal ve Dairesel Bağlı Listeler

Bağlı listeler, verileri bilgisayar üzerinde etkili şekilde inşa etmenin önemli yollarından biridir. Bu yazıda doğrusal ve dairesel bağlı listelerden hem tek hem de çift yönlü olanlarına değinilerek, C dilinde örneklenmiştir. Örnek kodlara buradan erişebilirsiniz.

Birbiriyle anlamlı birden çok veriyi bir araya getirmek gerektiğinde, başvurduğumuz araçlardan biri genellikle dizidir. Belirli bir veri büyüklüğü için tanımlanan diziler, bilgisayar hafızasında aşağıdaki gibi bir mimariyle oluşturulur:

Başlangıç adresi bilinen bir dizinin herhangi bir elemanına, bu adrese programcının belirttiği indis ve veri büyüklüğü çarpımının eklenmesiyle ulaşılabilir. Sözgelimi şekildeki dizinin 4. elemanına (indisi 3) erişilmek isteniyor olsun. Bu durumda gerekli adres aşağıdaki gibi hesaplanır:

Hex(0 + 4 (Byte) * 3) = 0x0C

Statik dizilerde hafıza erişimi bu kadar kolayken, dizinin sabit boyutlu olması bir dezavantajtır. Çünkü program derlenirken hafızada diziler için ayrılan boyutlar, siz o boyutun ne kadarını kullanırsanız kullanın aynıdır. Dolayısıyla kullanılmayan kısımlar hafızada gereksiz yer işgal etmiş olur. Ek olarak beklediğinizden daha fazla veya farklı tipte verileri aynı diziye eklemek isterseniz, bu kez dizinin boyutu veya veri tipi uygun olmayacağı için programınız hataya düşebilir. Bu ve benzer nedenlerden dolayı, verileri dinamik ve daha verimli yollarla hafızada saklamak için bağlı listeler kullanılagelmiştir. En basit bağlı listeyi, aşağıdaki gibi ifade edebiliriz:

Bağlı listenin her bir elemanı genellikle düğüm (node) olarak isimlendirilir. Her bir düğüm; saklanacak veri ve kendinden sonra gelen verinin adresini işaret eden bir işaretçiden (pointer) oluşmaktadır. Yukarıda belirttiğimiz gibi dizinin hafızadaki yerleşiminin aksine, düğümlerin hafızaya art arda yazılması gerekmez. Her düğüm, hafızada kendisini saklamaya uygun bir alana yazılır ve ancak toplam düğüm sayısı kadar alan işgal edilmiş olur. Doğal olarak gereksiz hafıza kullanımı önlenir. Aynı zamanda düğümler tıpkı bir lego gibi birbirine bağlandığı için; istediğiniz kadar veri, farklı veri tipinde olsalar dahi, birbirlerine bağlanabilir. Bağlı listelerin önemli dezavantajlarından biriyse; saklanacak her veri için, sonraki verileri işaret eden fazladan değişkenlere gerek duyulmasıdır. Ayrıca statik dizilerde herhangi bir elamana doğrudan indis değeri üzerinden kolaylıkla ulaşılabilirken, bağlı listeleri oluşturan düğümlerin hafızadaki aritmetik olmayan dağılımı nedeniyle, aynı işlem bağlı listelerde daha fazla zaman maliyetiyle gerçekleşecektir.

Bağlı listeler işaret ettikleri düğümlere göre tek yönlü ve çift yönlü olarak oluşturulabilir. Her bir düğümü, yalnızca kendinden sonraki düğüme işaret eden bağlı listeler tek yönlüyken; kendinden önceki düğümü de işaret eden düğümlere sahip bağlı listelerse çift yönlüdür.

Tek ve çift yönlü bağlı liste için aşağıdaki gibi bir tip tanımı yapılabilir:

Listeye tek yönlü düğüm eklemek için:

Çift yönlü düğüm eklemek için:

Dikkat ettiyseniz, listenin son düğümü her zaman NULL değerini işaret ederek son düğüm olduğunu vurgulamaktadır.

Dairesel farklı listeler, doğrusal listelerden mütevazi bir farkla ayrılır. Doğrusal listelerde son düğüm NULL değerini işaretlerken, dairesel listelerde son düğüm ilk düğümü işaret etmektedir. Bu yolla bağlı liste bir çember oluşturur.

Tip tanımı için yukarıdakinin aynısı kullanılabilir. Tek yönlü dairesel bağlı listeye düğüm eklemek için:

Çift yönlü içinse: