Tek Bağlı Listeler(Linked Lists)

Merhaba herkese,

Uzun bir aradan sonra bir konu anlatımına başlayacağız. Konumuz Tek Bağlı Liste.. Hatırlarsanız bizim birçok veri modelimiz vardı: liste, ağ, hiyerarşik, ilişkisel vs. Tek bağlı listeler de liste veri modelinin bir uygulamasıdır desek yanlış sayılmaz.

Bir işi yaparken bir veri grubundan yararlanmanız gerekebilir. Örneğin okul için düşünecek olursak; öğrenci adı, soyadı, numarası bizim verilerimiz olacak, bunları bir arada tuttuğumuzda, daha açık şekilde söylemek gerekirse, bunları birbirlerine bağladığımızda bir veri grubu elde ederiz. Tek bağlı liste yapısı iki kısımdan oluşur: Veri ve İşaretçi. Veri kısmına öğrenci ile ilgili tüm bilgileri yazarız. İşaretçi ise bir sonraki öğrencinin bellekteki yerini bize söyler. Eğer kendisinden sonra öğrenci yoksa, işaretçi alanı NULL değerini tutar.

Çizmekten üşendiğim için netten hazır çizilmiş bir örnek aldım:
Şekilde de gördüğünüz üzere, liste 2 elemanı ile başlıyor(sol en üstteki eleman). 2 verisinin bellekte tutulduğu adres "2003" imiş. İşaretçi kısmında ise 2184 değerini görüyoruz. Yani bu ne demek? Bir sonraki eleman da 2184 numaralı bellek adresinde imiş. Altta yazan değerler bellek adresleri.. 2184 numaralı bellek adresi de 4 verisine sahip, sol alttaki elemanın adresi imiş. Hemen oraya bağlandık. Tabi bu bağ sanal... 4 verisine sahip elemanın işaretçi kısmında ise 3225 değeri var. Hemen 3225 bellek adresine sahip elemanı buluyoruz:6. Bu şekilde tüm liste oluşturulur, arada sanal bir bağ olacak şekilde. En son 7 değerine sahip elemanın işaretçi kısmında NULL yazmakta. Bu, o elemanın listenin en son elemanı olduğunu, başka bir deyişle, kendisinden sonra henüz bir eleman olmadığını gösterir.

Bu mantıkla kodunu da çok basit bir şekilde yazabiliriz. Ben kısa bir iki kod yazayım hemen:

struct ListNode
{
int data;
struct ListNode *nextPtr;
};
typedef struct ListNode ListNode;
typedef ListNode *ListNodePtr;

Öncelikle yukarıdaki gibi int değer tutan bir data kısmı ve bir sonraki adresi gösteren işaretçi kısmını tanımladık ve bir struct oluşturduk.

Şimdi mesela tek bağlı listemize bir eleman ekleyelim. Bir metot yazalım hemen. Gerçi C'de buna fonksiyon deniyordu yanlış hatırlamıyorsam ama isimlere takılmayın, aynı şey.

void insertListNode(ListNodePtr *startPtr,int data)
{
if((*startPtr)==NULL)
{
(*startPtr)=(ListNodePtr)malloc(sizeof(LİstNode));
(*startPtr)->data=data;
(*startPtr)->nextPtr=NULL;
}
else
{
insertListNode(&((*startPtr)->nextPtr),data);
}
}

Fonksiyonda, eğer işaretçinin içeriği NULL ise hemen bir liste elemanı yaratıyor ve değerlerini giriyoruz. Eğer NULL değilse bir sonraki elemana gidip aynı işlemi tekrardan yaptırmaya çalışıyoruz..

Kodları derleyicide yazmadım ufak tefek hatalar çıkarsa affola.. Genel anlamda tek bağlı listeler böyle.. Diğer işlemleri de aynı mantıkla sizler de yapabilirsiniz..

Birazdan görüşürüz..