Bağlı Listeler

Merhabalar,
Bu yazımda sizlere bağlı liste veri yapısından bahsedeceğim. Veri yapısı deyince kulağa egzotik gelebilir. Ama inanın bildiğiniz şeylerden farklı bir şey anlatmayacağım. "Bildiklerimizi bir araya getirerek bilmediğimiz bir yapıyı tanımlama" şeklinde anlıyorum veri yapılarını...

Nedir? Neden gerek duyulmuştur?
Bağlı liste veri yapısı hafızanın farklı bölgelerinde bulunan verileri birbirine katar şeklinde bağlayan yapıdır.Dizi vb. yapılar zaten bu işi sağlamıyor mu? şeklinde bir soru aklınıza tam bu satırda gelmiş olmalı. Evet sağlıyor ama bir yere kadar. Diziler hafızanın belirli bir noktasında ardışıl olarak gelir. Yani dizinin ilk elemanı hafızanın 100 nolu adresinde bulunuyorsa dizinin ikinci elemanı 101 nolu gözde bulunacaktır. Ayrıca diziler ilk oluşturulduğunda uzunluğu belli olmak zorundadır. Daha sonra genişleme imkanı yoktur. Ancak tekrar boyutlandırma yapılabilir ki bu iş oldukça maliyetlidir. İşte böyle dinamik genişleyen ucuz maliyetli bir yapıya ihtiyaç duyulduğu sırada keşfedilmiş olmalı bağlı listeler.

Bağlı derken?
Bağlı listenin her bir elemanı hafızada birbirine bir sonraki elemanın aderesini gösterecek bilgiye sahiptir. Biz yalnızca ilk elemanın adresini biliriz. İkinci elemana ulaşmak için önce birinci elemana gideriz, ondan bir sonraki yani ikinici elemanın adresini alırız daha sonra ikinci elemana ulaşabiliriz. Üç, dört, beş ... hafıza dolana kadar üretilebilir, ulaşım mekanizması hep aynı. Bağlı derken bu mekanizma kastediliyor.

İhtiyaca göre...
Sorunlar farklı olunca çözümler, dolayısıyla gereksinimler de farklı oluyor. Bağlı liste veri yapısı iki çeşittir. Tek yönlü ve çift yönlü. İlkinde sadece ileri yönlü haraket yapmak mümkünken ikinci tipde geri gelme de mümkündür. Siz kendi probleminize en uygun tipi seçmelisiniz.

Bırak gevezeliği de biraz kod yaz!

Tek yönlü bağlı liste, C örneği

#include <stdio.h>
#include <stdlib.h>

typedef struct _eleman
{
 struct _eleman *sornakiEleman; // bir sonraki elemanı işaret eder.
 int veri; // yapının sakladığı veri. istenilen tipte istenildiği kadar veri eklenebilir.
} eleman;

typedef struct
{
 eleman *ilkEleman; // bağlı listeyi temsil eden yapı. Yalnızca ilk elemanı işaret ediyor.
} bagliListe;

bagliListe *bagliListeUret();
void elemanEkle(bagliListe*,int);
void elemanCikart(bagliListe*,int);
void listele(bagliListe*);

int main()
{
 bagliListe * bl = bagliListeUret(); // yeni bir bağlı liste ürettik.
 elemanEkle(bl,6); // eleman ekleyelim.
 elemanEkle(bl,34);
 elemanEkle(bl,987);
 elemanEkle(bl,5);
 elemanEkle(bl,2);
 listele(bl); // listele.
 system("pause");
 elemanCikart(bl,3); // 3. elemanı çıkart. ( ilk eleman 0'dan başlar)
 listele(bl); // tekrar listele, farkı gör.
 system("pause");
}

bagliListe *bagliListeUret()
{
 bagliListe* bl = (bagliListe*)malloc(sizeof(bagliListe)); // yeni bir bağlı listeyi hafızada oluşturup ilgili adresi alıyoruz.
 bl->ilkEleman = NULL;
 return bl;
}

void elemanEkle(bagliListe* bl,int veri)
{
 eleman *e = (eleman*)malloc(sizeof(eleman)); // yeni bir eleman oluşturalım.
 e->sornakiEleman = NULL;
 e->veri = veri;
 eleman *son = NULL; // katarın son elemanı.
 son = (eleman *)bl->ilkEleman; // başlangıç elemanını bağlı listeden alalım.
 if (son==NULL) // listemiz boş mu?
 {
  bl->ilkEleman = e;
  return;
 }
 while(son!=NULL) // değilse özyinelemeli olarak son elemana erişmeye çalış.
 {
  if (son->sornakiEleman==NULL)
   break;
  son = (eleman*)son->sornakiEleman; // düğümler arası atlama.
 }
 son->sornakiEleman = e; // nihayet son düğümün işaretçisine kendi adresimizi yazıyoruz.
}

void listele(bagliListe* bl)
{
 eleman *e = NULL;
 e=(eleman *)bl->ilkEleman;
 int i=0;
 while(e!=NULL) // özyinelemeli listeleme fonksiyonu.
 {
  printf("%i. eleman verisi = %i\n",i++,e->veri);
  e = (eleman*) e->sornakiEleman;
 }
}

void elemanCikart(bagliListe * bl, int sira)
{
 eleman *e = NULL;
 e=(eleman *)bl->ilkEleman;
 eleman *onceki = NULL;
 int i=0;
 if (e==NULL) // listemiz boş mu?
 {
  printf("Liste bos oldugu icin cikartma yapilamiyor!\n");
  return;
 }
 while(e!=NULL)
 {
  if (i==sira)
   break;
  i++;
  onceki = e;
  e = (eleman*) e->sornakiEleman; 
 }
 onceki->sornakiEleman = e->sornakiEleman; // silmek istediğimiz elemanın bir önceki düğümü ile bir sonraki düğümü birbirine bağlıyoruz. Böylelikle aradan çekilerek silinmiş izlenimi oluşturuluyor.
 free(e); // hafıza sızıntısını önlemek için serbert bıraktığımız elemanı hafızadan silmeyi unutmayalım.

}

Diğer yüksek seviyeli dillerde (Java, C# vb.) bu veri yapısını yapmak çok daha kolay. Mantıktan yola çıkarak o dillerde de sorunsuz bir şekilde bağlı liste veri yapısını oluşturabileceğinize inanıyorum.
Görüşmek üzere...