Bağlı Liste Detaylı Konu Anlatımı

2
1.291 Defa Okundu
bagli-liste-ornekleri

Bugün sizelere detaylı olarak bağlı listenin ne olduğunu, “bağlı liste çeşitlerini”, c ve java dillerinde yazılmış “bağlı liste örnekleri anlatacam yararlı olması dileğiyle. Bellekte elemanları ardışık olarak bulunmayan listelere bağlı liste denir. Bağlı listelerde her eleman kendinden sonraki elemanın nerede olduğu bilgisini tutar. İlk elemanın yeri ise yapı türünden bir göstericide tutulur. Böylece bağlı listenin tüm elemanlarına ulaşılabilir.

Bağlı liste dizisinin her elemanı bir yapı nesnesidir. Bu yapı nesnesinin bazı üyeleri bağlı liste elemanlarının değerlerini veya taşıyacakları diğer bilgileri tutarken, bir üyesi ise kendinden sonraki bağlı liste elemanı olan yapı nesnesinin adres bilgisini tutar.Bağlantılı liste yapıları iki boyutlu dizi yapısına benzemektedir. Aynı zamanda bir boyutlu dizinin özelliklerini de taşımaktadır.

Bu veri yapısında bir boyutlu dizilerde olduğu gibi silinen veri alanları hala listede yer almakta veri silindiği halde listenin boyu kısalmamaktadır.Eleman eklemede de listenin boyutu yetmediğinde kapasiteyi arttırmak gerekmektedir. Bu durumda istenildiği zaman boyutun büyütülebilmesi ve eleman çıkarıldığında listenin boyutunun kendiliğinden küçülmesi için yeni bir veri yapısına ihtiyaç vardır.

BAĞLI LİSTE ÇEŞİTLERİ

Doğrusal veri yapılarında dinamik bir yaklaşım yoktur. İstenildiğinde bellek alanı alınamaz ya da eldeki bellek alanları iade edilemez. Bağlantılı listeler dinamik veri yapılar olup yukarıdaki işlemlerin yapılmasına olanak verir. Bağlantılı listelerde düğüm ismi verilen bellek büyüklükleri kullanılır.

Bağlantılı listeler çeşitli tiplerde kullanılmaktadır;

1- Tek yönlü doğrusal bağlı liste
2- İki yönlü doğrusal bağlı liste
3- Tek yönlü dairesel bağlı liste
4- İki yönlü dairesel bağlı liste

Örnek: C dilinde bağlı liste yapısı struct ListNode

Bağlı listenin ilk elemanının adresi global bir göstericide tutulabilir. Son elemanına ilişkin gösterici ise NULL adresi olarak bırakılır. Bağlı liste elemanları malloc gibi dinamik bellek fonksiyonları ile oluşturulur.

Örnek: Java dilinde bağlı liste yapısı public class ListNode

Bağlı Listelerle Dizilerin Karşılaştırılması

Diziler;

• Boyut değiştirme zordur
• Yeni bir eleman ekleme zordur
• Bir elemanı silme zordur
• Dizinin tüm elemanları için hafızada yer ayrılır

Bağlı listeler ile bu problemler çözülebilir.
dizilerde-bagli-liste
Ayrıca,
Her dizi elamanı için ayrı hafıza alanı ayrılır. Bilgi kavramsal olarak sıralıdır ancak hafızada bulunduğu yer sıralı değildir. Her bir eleman (node) bir sonrakini gösterir.
bagli-liste-1

Listeler;

Listedeki her bir eleman data (veri) ve link (bağlantı) kısmından oluşur. Data kısmı içerisinde saklanan bilgiyi ifade eder. Link kısmı ise kendisinden sonraki elamanı işaret eder.

bagli-liste-2 Listede bir başlangıç (head) elemanı, birde sonuncu (tail) elamanı vardır. Listede aktif (current) eleman şu anda bilgilerine ulaşabileceğimiz elemandır.bagli-liste-3

Bağlı Liste İşlemleri

Listeler ile yapılan işlemler,

1- Listeye eleman ekleme

• Başa
• Sona
• Sıralı

2- Listeden eleman silme

• Baştan
• Sondan
• Tümünü
• Belirlenen bilgiye sahip elemanı
• İstenen sıradaki elemanı

3- Arama

4- Listeleme

• İstenen bilgiye göre

5- Kontrol

• Boş liste
• Liste boyutu

Tek Yönlü Bağlı Listeler

Listedeki elemanlar arasında sadece tek bir bağ vardır. Bu tür bağlı listelerde hareket yönü sadece listenin başından sonuna doğrudur.

Bağlı bir listeye eleman eklemek için önce liste tanımlanır. Bunun için listede tutulacak verinin türü ve listenin eleman sayısı verilir. Aşağıda verilen listeyi ele alarak bu listeye ‘G’ harfini eklemek isteyelim. Önce listede bu veri için boş bir alan bulunur ve bağ alanlarında güncelleme yapılır. ‘G’ verisini 6.sıraya yazarsak ‘F’ nin bağı ‘G’ yi, ‘G’ nin bağı da ‘H’ yi gösterecek şekilde bağ alanları değiştirilir.tek-yonlu-bagli-liste

tek-yonlu-bagli-liste-1Boşlar listesinden boş bir düğüm alınarak düğümün adresi bir değişkene atanır.tek-yonlu-bagli-liste-2Yeni düğümün veri alanına saklanması gereken ‘G’ değeri yazılır.

tek-yonlu-bagli-liste-3Yeni düğümün listedeki yeri bulunur. Bunun için düğümün arasına gireceği düğümlerin adresi belirlenerek bunların adresleri i,j değişkenlerine atanır.

tek-yonlu-bagli-liste-4

x adresli düğümün bağ alanına j düğümünün adresi yazılır. Bu şekilde yeni düğüm daha önce i düğümü tarafından işaretlenen j düğümünü gösterir. i, düğümünün bağ alanına da x düğümünün adresi yazılır ve yeni düğüm listeye eklenmiş olur.

Tek Yönlü Bağlı Listeler: Düğüm Ekleme –Kaba Kod

newNode <——- nextElement header

header <——- address (newNode)

Bağlı bir listeden eleman silme; önce listeden çıkarılmak istenen eleman bulunur. Eğer silinecek eleman listede yoksa bu durum bir mesaj ile bildirilir. Eleman bulunduğunda bağ alanlarında güncelleme yapılarak eleman listeden silinir.

Örneğimizdeki oluşturulan listeden ‘G’ düğümünü çıkarmak isteyelim. Bunun için yapılacak işlem, ‘G’ elemanından önce gelen ‘F’ elemanının bağ alanına çıkarılacak olan ‘G’ elemanının bağ alanındaki adresi yazmaktır.

Bu durumda ‘F’ düğümü ,’H’ düğümünü göstereceği için ‘G’ düğümü listeden çıkarılmış olur. ‘G’ elemanından sonra gelen düğümler değişmediği için herhangi bir kaydırma işlemine gerek kalmaz. Bu işlem dizi kullanılarak yapılsa idi, G den sonra gelen elemanların bir eleman sola çekilmesi gerekirdi.

tek-yonlu-bagli-listeler-dugum-ekleme–kaba-kod

Düğüm Silme –Kaba Kod

Liste Boyutu –Kaba Kod

Bağlantılı Listelerde Arama –Kaba Kod

İki Yönlü Bağlı Listeler

Listedeki elemanlar arasında iki yönlü bağ vardır. Elemanın bağlantı bilgisi bölümünde iki gösterici bulunur. Bu göstericinin biri kendisinden sonra gelen elemanı diğeri ise kendisinden önce gelen elamanın adres bilgisini tutar.

Bu sayede listenin hem başından sonuna hem de listenin sonundan başına doğru hareket edilebilir. Bu yöntem daha esnek bir yapıya sahip olduğundan bazı problemlerin çözümünde daha işlevsel olabilmektedir.

iki-yonlu-bagli-liste

Dairesel Bağlı Listeler

Tek Yönlü Dairesel Bağlı Listeler

Listedeki elemanlar arasında tek yönlü bağ vardır. Tek yönlü bağlı listelerden tek farkı ise son elemanın göstericisi ilk listenin ilk elamanının adresini göstermesidir. Bu sayede eğer listedeki elemanlardan birinin adresini biliyorsak listedeki bütün elemanlara erişebiliriz.tek-yonlu-dairesel-bagli-liste

İki Yönlü Dairesel Bağlı Listeler

Hem dairesellik hem de çift bağlılık özelliklerine sahip listelerdir. İlk düğümden önceki düğüm son, son düğümden sonraki düğüm de ilk düğümdür.

iki-yonlu-dairesel-bagli-liste

Örnekler- C++

Örnek 1: Tek yönlü bağlı liste

İlk işlemde hafızadan yeni bir adres isteme

bagli-liste-c++-ornegi

İkinci işlemde hafızadan yeni bir adres isteme

bagli-liste-c++-ornegi-1

Genel olarak görünümü aşağıdaki gibi olur.

bagli-liste-c++-ornegi-2

Sonuç;

bagli-liste-c++-ornegi-3

Örnek: 2- Çift yönlü bağlı liste ile filim adlarının saklanması

Sonuç;
bagli-liste-c++-ornegi-4

Java Programlama Dilinde Bağlı Liste Örneği: Bağlı Listenin Düğüm Yapısı

Java-Bağlı Liste ve Bağlı Listede Ekleme Yapısı

Java-Bağlı Listeye Arama Yapısı

Java-Bağlı Listede Silme Yapısı

Java-Bağlı Listede Listeleme Yapısı

Java-Bağlı Liste Örneği

Ekran Çıktısı :
// Bastan Sona Liste : 1 2 3 4 5 6 7 8 9
// 5 Bulundu
// Bastan Sona Liste : 1 2 3 4 6 7 8 9

Kaynaklar;

Yrd. Doç. Dr. Aybars UĞUR
Yrd.Doç.Dr. M. Ali Akcayol
Dr. Rifat ÇÖLKESEN
Yabancı kaynaklar

Yeni yazılarımız yayınlanır yayınlanmaz e-posta kutunuza gelmesini istiyorsanız ve e-posta abonelerimize göndereceğimiz fırsatlar için abone olabilirsiniz.

E-posta aboneliğiniz kaydedilmiştir. Bundan sonra davutsahin.net'in süpersonik yazılarını ilk siz e-posta kutunuzda göreceksiniz 😉

Bir şeyler yanlış gitti.

2 YORUMLAR

CEVAP VER

Please enter your comment!
Please enter your name here