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

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.

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

{
int data;
struct ListNode *next;
}

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

{
int data;
public ListNode next;
}

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.

public class ListNode{
int data;
public ListNode sonraki;
}

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.

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

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

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

Algorithm insert (newElement)
// bağlantılı listeye eklenecek yeni düğümü yarat
newNode = allocateNewNode (newElement)
// listenin başına yeni düğümü ekle
// yeni düğüm adresi, listeye yeni eklenme noktası olsun

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.

Düğüm Silme –Kaba Kod

Algorithm delete(element)
previousNode null
nextNode header
while nextNode != null and nextNode.element != element
do
previousNode nextNode // bir önceki düğümün referansını tut
nextNode nextNode‐‐>nextElement // bir sonraki düğüme ilerle
end while // yukarıdaki döngü eleman bulunduğunda veya liste tamamen tarandığı halde eleman bulunamadığında sonlanır
If nextNode != null // nextNode ile gösterilen düğüm silinecek düğümdür.
previousNode‐‐>nextElement = nextElement‐‐>nextElement // Önceki düğüm sonraki ile yer değiştirir
deallocate memory used by nextElement
else // eğer bir düğüm bulunamadıysa bu bölüme gelinir
// yapılacak bir silme işlemi yok

Liste Boyutu –Kaba Kod

Algorithm traverseList()
nextNode header
while nextNode != null and nextNode.element != element
do
// Bir sonraki düğüm null/0 olana veya bir sonraki
// bileşen bulunamayana kadar yapılacak işlemler
someOperation(nextNode) // bir sonraki düğüme ilerle
nextNode nextNode‐‐>nextElement
end while

Bağlantılı Listelerde Arama –Kaba Kod

Algorithm find(element)
nextNode header
while nextNode != null and nextNode.element != element
do
// sonraki elemana (düğüm) git
nextNode nextNode‐‐>nextElement
end while
// yukarıdaki döngü eleman bulunduğunda veya liste tamamen
//tarandığı halde eleman bulunamadığında sonlanır
If nextNode != null If nextNode != null
return nextNodeelement
else
// bir sonraki bileşen (düğüm) bulunulamıyor ise ELSE bloğuna girilir.
return null

İ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

#include <stdio.h>
#include <stdlib.h>
main() {
struct notlar {
int vize1;
struct notlar *bag;
} *yeniadres, *ilk, *son;
yeniadres=(struct notlar*) malloc(sizeof(struct notlar));
printf("Yeniadres:%d\n",yeniadres);
ilk=yeniadres;
son=yeniadres;
yeniadres->vize1=79;
yeniadres->bag=NULL;
printf("ilk:%d\n",ilk); //İlk elemanın adresini tutar
printf("son:%d\n",son); //Son elemanın adresini tutar
printf("T1 yeniadres->vize1:%d yeniadres->bag:%d\n",yeniadres->vize1,
yeniadres->bag);
//Hafızadan tekrar yer iste
yeniadres=(struct notlar*) malloc(sizeof(struct notlar));
printf("Yeniadres:%d\n",yeniadres);
son->bag=yeniadres;
yeniadres->vize1=95;
yeniadres->bag=NULL;
son=yeniadres;
printf("ilk:%d\n",ilk);
printf("son:%d\n",son);
printf("T2 yeniadres->vize1:%d yeniadres->bag:%d\n", yeniadres->vize1, yeniadres->bag);}

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TSIZE 45
struct filim {
char baslik[TSIZE];
int rating;
struct filim * sonraki; } ;
int main(void) {
struct filim * ilk = NULL;
struct filim * onceki, * simdiki;
char input[TSIZE];
puts("Filimin basligini girin (sonlandirmak icin enter (boşluk) girin):");
while (gets(input) != NULL && input[0] != '\0') {
simdiki = (struct filim *) malloc(sizeof(struct filim));
if (ilk == NULL) ilk = simdiki;
else onceki->sonraki = simdiki;
simdiki->sonraki = NULL;
strcpy(simdiki->baslik, input);
puts("Ratingi girin <0-10>:");
scanf("%d", &simdiki->rating);
while(getchar() != '\n') continue;
puts("Filimin basligini girin (sonlandirmak icin bosluk girin):");
onceki = simdiki;
}
if (ilk == NULL)
printf("Veri girilmemistir. ");
else
printf ("Filim Listesi:\n");
simdiki = ilk;
while (simdiki != NULL)
{
printf("Filim: %s Rating: %d\n", simdiki->baslik, simdiki->rating);
simdiki = simdiki->sonraki;
}
simdiki = ilk;
}

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

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

class Dugum
{
public int veri; // Değişik tiplerde çoğaltılabilir
public Dugum sonraki; // Sonraki düğümün adresi
public Dugum (int gelenVeri) // Yapıcı metot{ 
veri = gelenVeri; } // Düğüm yaratılırken değerini aktarır
public void yazdir() // Düğümün verisini yazdırır
{ System.out.print(" "+veri); 
}
}

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

class BListe{
private dugum bas; // Listenin ilk düğümünün adresini tutar
public BListe(){ // Bir BListe nesnesi yaratıldığında
bas=null; // boş liste olarak açılır.
}
public void basaEkle(int yeniEleman) // Liste bağına eleman ekler
{
Dugum yeniDugum = new Dugum(yeniEleman);
yeniDugum.sonraki = bas;
bas = yeniDugum;
}

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

public Dugum bul (int anahtar) {
//Listede anahtar değerini bulur
Dugum etkin = bas;
while(etkin.veri != anahtar)
{
if(etkin.sonraki==null)
return null;
else
etkin = etkin.sonraki;
}
return etkin; 
}

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

public Dugum sil(int anahtar)
{
// Verilen anahtar değerindeki düğümü siler
Dugum etkin = bas;
Dugum onceki = bas;
while(etkin.veri!=anahtar)
{
if(etkin.sonraki==null) return null;
else { onceki = etkin; etkin = etkin.sonraki; }
}
if(etkin==bas) bas = bas.sonraki;
else onceki.sonraki = etkin.sonraki;
return etkin;
}

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

public void listele()
{
System.out.println();
System.out.print("Bastan Sona Liste : ");
Dugum etkin = bas;
while(etkin!=null)
{ etkin.yazdir(); etkin=etkin.sonraki; }
}

Java-Bağlı Liste Örneği

// Bir bağlı liste oluşturarak, Bliste ve Dugum sınıflarını metotlarıyla birlikte test eden sınıf
class BListeTest {
public static void main(String args[]) {
BListe liste = new BListe(); // liste adlı bir bağlı liste nesnesi oluşturur.
liste.basaEkle(9);
for(int i=8; i>=1; --i) liste.basaEkle(i);
liste.listele(); int deger = 5; Dugum d = liste.bul(deger);
if(d==null) System.out.println("\n"+deger+" Listede Yok");
else System.out.println("\n"+deger+" Bulundu");
Dugum s = liste.sil(5);
liste.listele();
}
}

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

2 Yorum

Yorum Yap