BİL207U-VERİ YAPILARI
Ünite 6: Bağlantılı Listeler
Giriş
Günlük yaşamdaki birçok veri, listeler hâlinde saklanır. Kitabınızın bu bölümünde verilerin listeler hâlinde tutulmasına imkân sağlayan bağlantılı listeleri inceleyeceğiz. Bunun yanında farklı bağlantılı liste tasarımları da bu bölümde incelenecektir.
Bağlantılı Listeler
Programlama dillerinin birçoğu, verileri liste hâlinde tutmak için dizi yapılarıyla gelir. Depolanan ögelere erişimin hızlı olması ve veriler üzerinde kolay çalışma imkânı sağladığı için dizilerin kullanımı yaygındır. Kullanım kolaylığının yanında dizilerin performans kullanımı ile ilgili problemleri olabilir. Dil ile birlikte tasarlanan bu yapıda, sırasız dizilerdeki ögeleri arama işlemi yavaştır. İstenen ögeye ulaşabilmek için dizinin tüm ögelerini kontrol etmek gerekebilir. Sıralı dizilerde ise ekleme ve çıkarma işlemleri maliyetlidir. Verileri bağlantılı listelerde tutmak, ekleme ve çıkarma işlemlerinin maliyetlerini azaltır.
Bağlantılı liste yapılarının avantajlarının yanında dezavantajları da vardır. Bunlar;
• Aynı boyuttaki dizi elemanı ile bağlantılı listenin kullandığı bellek miktarına bakılacak olursa bağlantılı listelerin daha fazla bellek alanı kullandığı görülecektir. Bunun nedeni; bağlantılı listelerde ögelere ayrılan alanın yanında, sonraki düğümün adresleri içinde alan ayrılmalıdır. • Listeyi oluşturan düğümler arasında dolaşmak, dizi yapılarına göre daha zordur. • Tek yönlü bağlantılı listelerde önceki elemana dönmek mümkün değildir. Bunun için farklı tasarımlar geliştirilmiştir. İlerleyen konularda bu tasarımlar incelenecektir. • Bellekte düğüm alanları ihtiyaç oldukça oluşturulur bu yüzden liste elemanlarına rastgele erişim mümkün değildir.
Bağlantılı Liste Yapısı
Bağlantılı liste, düğüm(node) adı verilen sınıf nesnelerinin oluşturduğu bir yapıdır. Düğümler, verileri tutacakları alanlardan ve referans için ayrılan bölümlerden oluşur. Her düğüm, bir sonraki düğümün referans adresini tutar. Düğümlerin referans noktaları ile birleştirilmesi bağlantı olarak adlandırılır.
Nesne Odaklı Bağlantılı Liste Tasarımı
C# ile bağlantılı liste yapısını oluşturmak için iki sınıf hazırlayacağız. Düğüm yapımız için Dugum ve liste için BagliListe sınıfları oluşturulacaktır. Listeye eklenecek her yeni eleman için bir Dugum sınıfı başlatılacak. Listedeki düğümler, birbirlerine, referanslar ile bağlanacaktır. Bu referanslar için ayrıca BagliListe sınıfı oluşturulacaktır.
Bağlantılı Listelerde Farklı Tasarımlar
Geliştiriciler, çözmek istedikleri programların gereksinimlerine göre farklı bağlantılı listeler tasarlayabilirler. Veri türlerine göre bağlantılı liste tasarlayabileceği gibi programın akışına göre de farklı tasarımlara ihtiyaç duyabilirler.
Çift Bağlantılı Liste
Veri sayısının çok olmadığı listelerde tek yönlü yapı, program performansına zarar vermeyebilir. 10 elemanlı bir listede 10. düğümdeyken 9. düğüme gelmek için başlik düğümünden itibaren 9 gezinme yeterli olacaktır ancak 1000. elemanda iken 999. ögeye gelmek oldukça maliyetli bir işlemdir. Bu gibi ihtiyaçlar için çift bağlantılı liste (doubly linked list) tasarımı geliştirilmiştir. Listede önceki düğümü referans gösteren bir alan daha eklersek ters yönde gezinmek de mümkün olacaktır. İki yönlü referans alanına sahip olan düğümlerden oluşan listeye çift bağlantılı liste denmektedir.
Çift bağlantılı liste kullanımının bazı avantajları vardır. Bunlar;
• Her iki yönde gezinmeye imkân sağlar. • Bir önceki düğüme erişim olduğu için bir düğüm kolayca silinebilir. • Ters çevirmek kolaydır. • Dinamik olarak büyüyebilir veya küçülebilir. • Diğer çeşitli veri yapılarının uygulanmasında kullanışlıdır.
Çift bağlantılı liste yapılarının dezavantajları ise;
• Tek yönlü bağlantılı bir listeyle karşılaştırıldığında her düğüm fazladan bir referans alanına sahiptir. Bu yüzden bellekte daha fazla alan kaplar. • İşlemler, tek bağlı listelere kıyasla fazladan işaretçileri işlemenin ek yükü nedeniyle daha fazla zaman gerektirir. • Bu tasarımda da ögelere rastgele erişim imkânı yoktur.
Dairesel Bağlantılı Liste
Bağlantılı listelerle ilgili inceleyeceğimiz ikinci tasarım ise bağlantılı listenin son elemanının ilk düğümü işaret ettiği Dairesel Bağlantılı Liste’dir. Bu veri yapısında her düğüm, bir sonraki düğümü işaret eder. Listenin son düğümü ise ilk düğümü işaret eder. Bu özelliği, onun dairesel olarak adlandırılmasına neden olmuştur. Dairesel bağlantılı listelerin bir sonu olmadığını bilmek önemlidir. Tek yönlü bağlantılı listedeki gibi gezinme yapıldığında sürekli başa dönülür. Bağlantılı listenin sonunu kontrol etmek için son düğümün Link alanının boş olması değil, başlık düğümünü gösterip göstermediği kontrol edilir.
Dairesel bağlantılı listelerin avantajlarından bazıları aşağıda listelenmiştir;
• Kodda NULL(boş) atamasına gerek yoktur. Liste üzerinde gezinerek başa dönülebilir. • Dairesel bağlantılı listeler, başlangıç ve bitiş arka arkaya geldiği için son işlemlerde avantajlıdır. Round Robin zamanlaması gibi algoritmalar, bu liste yapılarında uygulanabilir. • Dairesel bir listede herhangi bir düğüm, başlangıç noktası olabilir. Herhangi bir düğümden başlayarak tüm liste kolayca taranabilir.
Dairesel bağlantılı listenin dezavantajlarından bazıları aşağıda listelenmiştir;
• Tek yönlü bağlantılı listelere göre daha komplekstir. • Dikkatli kodlama yapılmadığı takdirde program sonsuz döngüye girer. • Dairesel bağlantılı listeyi tersine çevirmek, diğer yapılara göre daha zordur. • Listenin sonunu ve döngü kontrolünü bulmak daha zordur.
Bağlantılı Listeler İçin İteratör Sınıfı
BagliListe sınıfı aynı anda iki konuma ulaşılmasına imkân vermez. Yalnızca listedeki herhangi bir konuma (geçerli düğüm, önceki düğüm, vb.) ulaşılabilir ancak iki veya daha fazla konuma ulaşılmak istenirse (örneğin bir dizi düğümü listeden çıkarmak istiyorsak) daha gelişmiş yapıya ihtiyaç duyulacaktır. Bu bölümde gelişmiş yapı için iteratör sınıfı geliştirilecektir.
Hazırlayacağımız iteratör sınıfı, bağlantılı listeyi depolayan bir alan ve geçerli düğümü depolayan alanlardan oluşacaktır. Yapıcı metodunda bağlantılı liste nesnesi iletilir. Metot, geçerli alanı iletilen listenin başlık düğümü olarak atar. İteratör sınıfımızda yeni düğüm eklemek için iki yeni yöntem hazırlayabiliriz. Bunlardan ilki, mevcut düğümün önüne ekleme yapmak için OnuneEkle ve mevcut düğümün arkasına eklemek için ArkasinaEkle metodudur (Ders kitabınızın 124 ve 125. sayfalarında verilen kodları inceleyiniz).
Yeni LinkedList Sınıfı
Yetenekli bir iteratör sınıfı elde edilmesi sayesinde BagliListe sınıfını yeniden düzenleyerek sadeleştirebiliriz.
Kod 6.21
public class BagliListe() { private Dugum baslik; public BagliListe() { baslik= new Dugum("baslik"); } public bool BosMu() { return (baslik.Link == null); } public Dugum IlkDugumuGetir() {
return baslik; } public void ListeyiGoster() { Dugum mevcut= baslik.Link; while (!(mevcut == null)) { Console.WriteLine(mevcut.Element); mevcut= mevcut.Link; } } }
İteratör Sınıfı ile Örnek
Yineleyici sınıfını kullanarak bağlantılı bir listede gezinmek için etkileşimli program yazmak kolaydır. Bu aynı zamanda bize hem Iterator sınıfının hem de LinkedList sınıfının tüm kodunu tek bir yerde toplama şansı verir.
Ders kitabınızın 117. sayfasındaki Ek 6.1’de paylaşılan kod bloğu, konsol ekranında çalışan bir uygulamadır. Bağlantılı liste yapılarında şimdiye kadar incelenen konuların tekrar edilmesi için basit ama öğreticidir. Program geliştiricileri, hazırladıkları programların ihtiyacına göre farklı bağlantılı liste tasarımları yapabilirler.