Veri Yapıları — Ünite 6 Soru-Cevap

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. Dizide sıralı eleman eklemek için birçok elemanı kaydırmak gerekebilir.

Verileri bağlantılı listelerde tutmak, ekleme ve çıkarma işlemlerinin maliyetlerini azaltır.

Dizi yapısındaki örneği tekrar ele alırsak listenin ortasına
eleman ekleme işlemi iki adımda çözülebilir. İlk olarak önceki elemanın referans alanını yeni eklenen elemanın referans alanına kopyalamak, ardından da yeni elemanın referansını önceki elemanın referans alanına yazmak yeterlidir

Bağlantılı liste yapılarının avantajlarını maddeler hâlinde inceleyecek olursak;
• Ekleme ve silmeler, dizi yapılarına göre
daha az maliyetle yapılabilir.
• Büyük kayıtlarda, yapıdaki elemanları taşımak veya yer değiştirmek birçok işlem gerektirir. Bunun yerine ögelerin işaretçilerini
taşımak çok daha az maliyetlidir.
• Bağlantılı listelerde, liste boyutu ihtiyaç oldukça arttırılır. Önceden bellek ayırmaya gerek
yoktur. Gereksiz bellek kullanımını azaltır.
• Yığın, kuyruk gibi veri yapıları; bağlantılı
listeler ile kolaylıkla uygulanabilir

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, 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.

Bağlantılı listenin sonundaki düğüm ise Son Düğüm olarak adlandırılır. Son düğümün bir ardıl düğümü gösterecek Sonraki alanı boş(null) olarak atanmalıdır. Bağlantılı listeler üzerinde yapacağımız işlemlerde, listenin sonuna geldiğimizi fark edebilmek için düğümün Sonraki alanı boş olmalıdır.

Dugum sınıfının tanımını tamamlamak için en az iki kurucu metoda ihtiyacımız var. Düğüm oluşturulurken hem Oge, hemde Link null olarak atanmalıdır. İlk metodumuz bu atamaları yapan varsayılan kurucu metodudur. İkinci metodumuz ise, düğüme veriyi atayan metoddur.

BagliListe sınıfı, bağlantılı listemizin düğümleri arasındaki bağlantıyı oluşturmak için kullanılır.

Sınıf, listeye düğüm eklemek, listeden düğümleri kaldırmak, listede gezinmek ve listede bir düğüm bulmak için çeşitli metotlar içerir. 

Bağlantılı listede, yeni düğüm eklemek için ilk olarak, yeni düğümden önceki düğümün bulunması gerekir. Önceki düğümü bulmak için, listedeki tüm düğümlerin ögelerini tarayarak bir eşleşme arayan Bul metodunu oluşturmalıyız.

Bul metodu, listede ögeleri taramaya başlarken ilk olarak boş bir düğüm oluşturur ve bu düğüme başlık düğümünü atar. Daha sonra, parametre olarak gönderilen oge ile mevcut düğümün içeriğinin aynı olup olmadığını kontrol eder. İçerikler eşleşmiyorsa, bir sonraki düğümü gösteren Link, mevcut düğüm olarak seçilir. Bu işlem while döngüsü içerisinde tekrarlanır. İstenilen düğüme ulaşıldığında düğüm geri döndürülecektir.

Bağlantılı listeden düğüm kaldırmak için, kaldırılmak istenilen düğümden önceki düğümü bulup, sonraki düğümü referans olarak göstermeliyiz. Aksi takdirde listenin bağlantısı kopacak ve sonraki düğümler kaybolacaktır. Önceki düğümün Link alanına sonraki düğümü yazmamız, istenilen ögeyi kaldırabilmek için yeterlidir.

İ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.

Düğüm sınıfında, önceki düğümün referansını tutabilmek için bazı değişiklikler yapmamız gerekiyor. Sınıfta sonraki düğümü referans gösteren Link’i, SLink olarak değiştireceğiz. Önceki düğümü gösterecek alan ise OLink olarak adlandırılacak.

Düğüm yapısı değiştirildikten sonra bağlantılı listede işlem yapmak için kullanılan yöntemlerde de değişiklik yapılması gerekir. Ekle metodunda, mevcut ögenin, SLink alanına yeni düğümü ekledikten sonra yeni düğümün OLink alanına da mevcut düğümün referansı verilmelidir.

Çift bağlantılı listelerde düğümün kaldırılması, tek bağlantılı listelere göre daha kolaydır. Kaldırılmak istenilen düğüm bulunduktan sonra, önceki düğümün SLink alanına kaldırılacak düğümün SLink alanı yazılmalıdır. Kaldırılacak düğümün OLink alanına ise kaldırılacak düğümün OLink alanının yazılması
yeterlidir.

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.

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.

Dairesel bağlantılı liste yapısı için kodumuzda yapmamız gereken tek değişiklik, yeni bir düğüm oluşturulduğunda Link alanına başlık düğümünün referansını atmaktır. Bu sayede her yeni düğüm eklediğimizde, son düğüm başlık düğümünü işaret edecektir.

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.

İ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.

İteratör sınıfı kullanarak bağlantılı listeden bir düğümü kaldırmak oldukça kolaydır. Basitçe önceki düğümün Link alanına mevcut düğümün Link alanında yazan değeri kopyalamak, mevcut düğümü bağlantılı listeden çıkaracaktır.