Bağlı listeler en önemli veri yapılarından biridir. Biz burada çift yönlü bir bağlı listeyi C++ kullanarak kodlayacak ve temel işlemleri tanımlayacağız. Bağlı liste veri yapısı diğer dillerle de kodlanabilir ancak biz C++ yı seçtik, tabiki bu seçimimizde C++ nın NYP(oop) desteği olması önemli bir faktör. Çift yönlü bağlı listeyi anlatarak tek yönlü bağlı liste işlemlerini de aynı zamanda aktarmış olacağız.

Sınıf yapımız şu şekilde:

class tnode{

private:

string content;

tnode *prev;

tnode *next;

friend class d_linked_list;

};

class d_linked_list{

private:

tnode head,tail;

tnode *head_ptr,*tail_ptr;

public:

d_linked_list(){/*constructor*/

head_ptr=&head;

tail_ptr=&tail;

head_ptr->next=&tail;

tail_ptr->prev=&head;

}

//metotlarımızı buraya yazacağız

};

d_linked_list adında head ve tail adlı nodlarımızı bulunduran bir sınıfımız var ve tahmin edeceğiniz gibi her nodu temsilen tnode adında bir sınıfımız var. C++ da bağlı listeleri kodlarkan mutlaka böyle bir yol kullanmak zorunda değilsiniz, mesela head ve tail nodları olmak zorunda değil yerine head ve tail diye sadece işaretçi(pointer) de tutabilirsiniz ancak head ve tail node larının olması işimizi kolaylaşatıracak ve sınır noktalarda oluşabilecek parçalama arızalarının(segmentation fault) riskini azaltacaktır.  Bunların haricinde sınıfımızda her nodun önüneki ve arkasındaki nodu gösteren next ve prev adında nod cinsinden işaretçileri var. d_linked_list sınıfının tnode sınıfının private elemanlarına ulaşabilmesi için  “friend class d_linked_list” bildirimi yaptık ve sınıflarımızı hazırlamış olduk.

Bu durumda main in içinde
d_linked_list list1; dediğimizde boş bir çift yönlü bağlı liste yapısını oluşturmuş oluyoruz. NOT: Ders boyunca resim veya animasyonlarda nodların gösterilmeyen işaretçileri NULL olarak kabul edilmiştir.

-Resim: Boş bir bağlı liste-

Yavaş yavaş bağlı listemizin kodlarını yazmaya başlayalalım.

Boş Kontrolü
Yukardaki resimden de anlaşıldığı gibi listemiz boşken head_ptr nin next işaretçisinin değeri tail_ptr ile aynıdır, bu durumda listenin boş olup olmadığını head_ptr nin next işaretçisini tail_ptr nin değeriyle karşılaştırarak kolaylıkla anlayabiliriz. Boş kontrolü(is_empty) metodumuzla başlayalım.
bool is_empty(){

if(head_ptr->next==tail_ptr)

return true;

else

return false;

}

Listeye Yeni Eleman Ekleme
Yeni nod ekleme(insert) metoduyla devam edelim. Insert metodu kendisine gönderdiğimiz bir işaretçi(pointer) ve veriyi(data) yı alıp gösterdiğimiz yerin bir önüne(veya bir arkasına, isteğimize kalmış) yeni nodu ekleyecek ve veri kısmına gönderdiğimiz veriyi yazacak. Biz veri türü olarak string seçtik.

void insert_newnode(tnode *ptr,string text){

tnode *temp;

temp=new tnode();//yeni nodumuz oluştu ancak şu anda listemizle bir alakası yok

temp->content=text;// veri kısmını hemen yazıp aradan çıkaralım

temp->next=ptr->next; //ilk bağ kuruldu

temp->prev=ptr;// artık nodumuz kendisini listeye bağladı ancak liste henüz kendisini almadı

ptr->next=temp;//listeden ilk bağ geldi

(temp->next)->prev=temp;// ekleme işi tamamlandı

}

“Yeni eleman ekleme”  metodunun hareketli gösterimi:

Listeden Eleman Silme
Listeden eleman silmek için tek gereken silmemiz istenen elemanı gösteren bir işaretçidir.  Silinecek elemanın listeyle bağlantısını kestikten sonra elemanın bellekte tuttuğu yerin tekrar kullanılabilmesi için bu bölge artık müsait mesajı veren reclaim işlemini yapıp silme işlemimiz bitireceğiz. Metodumuzu yazarken boş kontrolü gibi kontrolleri yapmadım,  sağlıklı bir uygulama geliştirebilmek için çeşitli kontroller yapmak durumundasınız(is_empty kullanmak veya işaretçinin değeri NULL mu diye bakmak gibi).

void delete_node(tnode *ptr){

(ptr->prev)->next=ptr->next;

(ptr->next)->prev=ptr->prev;

delete(ptr);

//silme işlemi tamamlandı

}

“Listeden eleman silme”  metodunun hareketli gösterimi:

Listedeki Elemanları Gösterme

void show(){
tnode *ptr;
ptr=head_ptr->next;

while(ptr!=tail_ptr){
cout<< ptr->content << endl; ptr=ptr->next;
}
}

Kodların hepsinin bir arada yazılmış hali:

#include “iostream”

#include “string”

using namespace std;

class tnode{

private:

string content;

tnode *prev;

tnode *next;

friend class d_linked_list;

};

class d_linked_list{

private:

tnode head,tail;

tnode *head_ptr,*tail_ptr;

public:

d_linked_list(){/*constructor*/

head_ptr=&head;

tail_ptr=&tail;

head_ptr->next=&tail;

tail_ptr->prev=&head;

};

bool is_empty(){

if(head_ptr->next==tail_ptr)
return true;
else
return false;

}

void insert_newnode(tnode *ptr,string text){

tnode *temp;

temp=new tnode();//yeni nodumuz oluşu ancak şuanda listemizle bir alakası yok

temp->content=text;// veri kısmını hemen yazıp aradan çıkaralım

temp->next=ptr->next; //ilk bağ kuruldu

temp->prev=ptr;// artık nodumuz kendisini listeye bağladık ancak liste henüz kendisini almadı

ptr->next=temp;//listeden ilk bag geldi

(temp->next)->prev=temp;// ekleme işlemi tamamlandı

}

void delete_node(tnode *ptr){

(ptr->prev)->next=ptr->next;

(ptr->next)->prev=ptr->prev;

delete ptr;

}

void show(){

tnode *ptr;

ptr=head_ptr->next;

while(ptr!=tail_ptr){

cout<< ptr->content << endl; ptr=ptr->next;

}
}

int main(){

d_linked_list list1;

//işlemler

return 0;
}

Listeden eleman silme ve ekleme işlemlerini örneklendirebilmek için bir uygulamamız olması gerekiyor ancak biz burda sadece işlemin nasıl yapıldığını anlatıyoruz. Silme işleminde ve ekleme işleminde ptr adında bir işaretçi geçiyor. Nedir bu ptr, neyin nesidir diye sorabilirsiniz! Bu soruya cevap verebilmek için bir uygulama geliştiriyor olmamız gerekir. Örnek: Bir metin editörü yapıyorsunuz, veri yapısı olarak çift yönlü bağlı liste seçtiniz. Her satırı bir nod la temsil ediyorsunuz. Eğer yeni satır ekleme işlemini sona yapacaksanız bu durumda ekleme işlemi için sizin ptr niz tail_ptr->prev dir veya baştan 3 satır sonrasına ekleme yapmak istiyorsanız baştan itibaren sayarak ptr=ptr->next şeklinde ilerleyip 4. satıra gelindiğinde durursunuz ve ptr niz o anki ptr olur(aşağıya yazdım).
i=0;
tnode *ptr=head_ptr;
while(i<=2){ ptr=ptr->next;
i++;
}
Tabi bu işlemden önce listemizde en az 3 satır oldugunu bilmemiz gerekir aksi halde eğer 3 satır yoksa parçalama arızası(segmantation fault) alırız.

Aynı şekilde silme işlemi için kendi yazdığımız sınıftan bir örnek verelim: Listemizin her nodunun content bölümüne bakacağız ve content bölümünde ali yazan nodu sileceğiz, yine head_ptr den başlayıp tüm node ları kontrol ede ede gitmeliyiz(show metodunda olduğu gibi while içinde ptr=ptr->next diyerek). Eğer contenti ali olan nod varsa delete_node fonksiyonuna gönderecek ptr miz işte o ptr dir. Umarım demek istediklerim anlaşılmıştır. Yani metotlarda geçen ptr nin ne olacağına uygulamalarınızda siz karar vereceksiniz.

Bu derste çift yönlü bağlı listelerin temel işlemlerini yapmaya çalıştık, umarım sizlere faydalı olmuştur. Tam kodun bulunduğu dobly_linked_list.cpp dosyası, ekle.swf ve sil.swf nin bulunduğu d_linked_list.rar dosyasını burdan bilgisayarınıza indirebilirsiniz( not: kodlar linux(g++) altında derlenmiştir ). Sorularınızı forumlarımızda sorabilirsiniz, iyi çalışmalar…