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.
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.
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; }
Listede bir başlangıç (head) elemanı, birde sonuncu (tail) elamanı vardır. Listede aktif (current) eleman şu anda bilgilerine ulaşabileceğimiz elemandır.
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.
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.
İ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.
Ö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
İkinci işlemde hafızadan yeni bir adres isteme
Genel olarak görünümü aşağıdaki gibi olur.
Sonuç;
Ö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ç;
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
hocam güzel anlatmışsınız, konunun devamı gelecek mi?
Esra hanım, bilgisayar mühendisliği ögrencilerin 4 sene gördüğü bütün dersleri sitemize eklenecektir.