LINKED LIST (Bağlı liste)

***Elemanları listelemek için Arrayi kullanalım ;

•   Öncelikle array dediğimiz  , soyut veri tipleri, sabit bir kapasite ile üretilir . örneğin int a[5];
•  Sabit üretilmiş bu kapasiteden daha fazla kapasiteye her ihtiyaç duyduğumuzda elimizdeki kapasiteyi ikiye katlayarak yeni kapasiteyi oluştururuz .

             Bu işlem mekanizmasi ile;

1. Listeyi_yazdır() fonksiyonumuz olsun ve bununla arrayimizdeki tüm elemanları yazdırmak istersek , eğer arrayimizin içinde N eleman olduğunu düşünürsek  hepsini yazdıracağımız zaman O(N) zaman harcamış oluruz .
2.  Kincı_Elemanı_Bul()  fonksiyonuzmuzda ise bu zaman O(1) zamanda bulmuş oluruz.. Niçin 0(1) ? Çünkü  a[3] bize direk 3.  elemanı getirir.
3.  Araya_ekle() ve Silme() fonksiyonları zaman bakımından daha masraflıdır.  Niçin?   

•  Bunu kötü durumda(worst case) inceleyecek olursak ; 0. pozisyona bir element eklenilmek istenildiğinde tüm arrayi 1 birim kaydırmak gerekir . Aynı eskide kullanılan daktilolar gibi bi harf yazılınca üstündeki şaryonun bir birim kayması örnek verilebilir.   bu da O(N) zaman alır . burdan zaman kazanmak için aarrayin hiç büyümeyeceğinden emin olmamız gerekir. Aksi halde bir birim kayma olayı hep olacaktır.

  **** Single Link Listleri  basitçe anlatmak gerekirse tren bunun için en uygun örnek olacaktır diye düşünüyorum. 

• Lokomotif (Head) - Nerden başlanılacak? sorusuna cevap verir ve ilk düğümdür(head node) .
• Vagonlar( düğümler ) - Lokomotiften sonra gelen düğümlerdir . Sonraki vagon nerde ? Sonraki vagonda ne var ?  sorularının cevabını biliyor . 
• En sondaki düğümde (Tail) ne yapsın hiç bişey bilmiyor olayın farkında değil yazık üzülmesin diye ona da “sende NULL u göster hadi” diyorsun . Null  ” boş ” demektir bu arada yani kandırıyoruz :)

                              

1. Listeyi_Yazdır() veya Bul() fonksiyonlarında  ;
2.   Listeyi_Yazdır() fonksiyonu array deki gibi aynı mantıkta ilerliyor O(N) zaman alıyor.
3.   Bul() fonksiyonu için iş biraz daa değişik çünkü link listlerde bir elementi bulabilmek için listeyi en baştan itibaren gezmek gerekiyor ,  elementi bulmak için gezdiğimiz node sayısına N dersek bir elementi bulmak için O(N) zaman harcamış oluyoruz.
4. K_Incı_bul() fonksiyonu O(N) zamanda buluruz çünkü örneğin 5. elemanı bulmak için listenin en başında başlayıp tüm nodeları teker teker gezmemiz gerek .
5. Remove işlemi ise şöyle gerçekleşir ;

                 Normalde A1 , A2 yi A2 , A3 gösterirken biz A2 yi öyle kuralsız biçimde silemeyiz . Çünkü A2 ,A3 ün bilgilerini tutuyor.A2 yi kuralsız biçimde silersek A1 den sonra program nereye gideceğini bilemez. Örnekle açıklayacak olursam sen hareket halindeki bir trende üç vagondan ortadakini ayırırsanız  ne olur ? Treni birarada tutamassınız demi öndeki vagon elinizden kaçıp gider Bu yüzden olduğumuz vagondan (A1)  üçüncü vagona (A3)  bi halat atarız ki kopma falan olmasın sonra ikinci vagonu aradan çıkartırız (A2). Artık uçarak mı çıkıyor devrilerek mi çıkıyor orasını bilemem :) . Böylelikle trenimiz aynı seyrinde devam eder.  

2)    Araya eleman ekleme işlemi ise ;

  X elemanı A1 ve A2  nin arasına sokulmak isteniyorsa, önce A1 , X i göstermeli ve X te A2 yi göstermelidir

1.  Bir Single linked liste ( bağlı listeye ) önden ekleme , ilk elemanı silme ,veya sondan ekleme, birim zamanda gerçekleştirilir. Big-oh notasyonuna göre de O(1) , yani constant zamandır.
2. Sondan eleman silme biraz yanıltıcı olabilir . Peki Neden ?

                   

• Çünkü herseferinde tail ( kuyruk ) i güncellememiz gerekmektedir. Bunu yapmak için en baştan ( Head ) gelerek en sondaki elemandan bi öncekli elemanı bulmamız gerekiyor .(Yukarıdaki resimde görüldüğü üzere kuyruğumuz güncellenmiştir yeni kuyruğumuz ( tail ) 7 elemanından bi önceki eleman olan 2 olmuştur. )

 

• Daha sonra ise bu yeni kuyruğumuzun (tail) bi sonraki elemanını (Next) NULL olarak belirtiriz.

• Daha sonra en sondaki silmek istediğimiz elemanı sileriz.

Bu işlem O(N)  zaman alır çünkü listeyi en baştan dolaşıyoruz tüm elemanları geziyoruz.  Peki bunu O(1) zamanda nasıl yapabiliriz ?

Bunun yerine demişsinizdir belki “ Ya ne var bi önceki elemanı gösteririm olur biter “ ama single link list tek yönlü çalışır. Yani geri dönemiyoruz öyle..  işte adamlar bunu da düşünmüş ve Double link list denilen bi mantık yapmışlar her iki yönede çalışıyor bu link list daha pratik ve listeyi en baştan dolaşmak yerine en sondaki elamnın bi öncek elamnını direkt olarak gösterebiliyoruz.

Doubly Link list örneği de bu şekildedir

 

Kısaca , nedir bu Array implemantasyonu ile List implementasyonu arasındaki fark diyecek olur isek ?

        Array implementasyonu ;

               Avantajları : Kolay dizinlenebilir yapılardır .

               Dezavantajları :Elemanların  Araya ekleme (insertion) ve Kaldırma ( Removal) işlemlerinin maliyetli olması .

         List implementasyonu ;

Bu ise arrayin tam tersidir .

           Avantajları : Elemanların  Araya ekleme (insertion) ve Kaldırma ( Removal) işlemlerinin ucuz olması .

            Dezavantajları : kolaylikla dizinlenebilir olmaması .

Şimdi kod yazımına geçelim bu yapı nasıl işliyor ona adım adım bakalım.

  Resimlerde her bir blok(node) iki parçaya bölünmüş . Bu parçalardan ilk , yani soldaki , bi değer veya veri tutuyor  , diğeri ise sağındaki (Next) elemanı refere ediyor.

class Node {
  int veri;// veri veya bi değer depolandı
  Node* next;// yanındaki nodu refere eder. son node için 

   public:
     Node() {};//constructor (Yapıcısı)
     void Verikur(int aVeri) { veri= aVeri; };
     void NextKur(Node* aNext) { next = aNext; };
     int Veri() { return veri; };
     Node* Next() { return next; };
};// ana yapımız böyle buralarda hep node, next falan // bunları oluşturduk

// LİST sınıfımızı oluşturuyoruz
class List {
   Node *head;
   public:
      List() { head = NULL; };
      void yazdir();
      void ekle(int veri);
      void sil(int veri);
};

/**
* Listemizin içeriğini yazdırmak için yazdır fonksiyonunu kullanıyoruz
*/
void List::yazdir() {

/* node umuzdan çıkan tmp adında bi pointer(işaretçi) oluşturduk bunu da aldık listemizin en başına koyduk
*/

   Node *tmp = head;

// eğer hiç node umuz yok ise
if ( tmp == NULL ) {
   cout « “BOS” « endl;
     return;
}

// Eğer listemizde yalnızca bir node umuz var ise;
if ( tmp->Next() == NULL ) {
  cout « tmp->Veri(); // içindeki veriyi göster
  cout « ” —> “;// işaretini koy
  cout « “NULL” « endl; // sonra NULL yaz
}
else {
// Eğer bir node dan daha fazla var ise
do {
  cout « tmp->Veri();//liseyi gezerek veriyileri al
  cout « ” —> “;//işaretini koy
  tmp = tmp->Next();//nextine geç
}
 while ( tmp != NULL ); // NULL yani en sona gelene kadar

cout « “NULL” « endl;
 }
}

/**
* Listemize yeni bi Node eklemek
*/
void List::ekle(int veri) {

// Yeni bi node oluşturalım
  Node* newNode = new Node();
  newNode->Verikur(veri);
  newNode->NextKur(NULL);

// bu node içinde bi tane pointer yaratalım
 Node *tmp = head;

if ( tmp != NULL ) {
// Nodes hali hazırla listede bulunuyorsa
// Listenin sonuna kadar ayrıştır
  while ( tmp->Next() != NULL ) {
    tmp = tmp->Next();
}

// yeni node un nex ini göster
tmp->NextKur(newNode);
}
else {
// Listemizdeki ilk node
head = newNode;
}
}
/**
*Listeden node silme
*/
void List::sil(int veri) {

// yeni pointer oluştur
  Node *tmp = head;

// silecek bi node yok ise
if ( tmp == NULL )
  return;

//sileceğimiz node list in son elemanı ise
if ( tmp->Next() == NULL ) {
   delete tmp;
   head = NULL;
}
else {

Node *prev;
do {
  if ( tmp->Veri() == veri ) break;
  prev = tmp;
  tmp = tmp->Next();
} while ( tmp != NULL );

//pointerları ayarla
prev->NextKur(tmp->Next());

// şuanki node u sil
delete tmp;
 }
}
//Bu da main fonksiyonumuz

int main()
{
// yeni listemizi oluşturalım
List list;

// node ekleyelim
list.ekle(100);
list.yazdir();
list.ekle(200);
list.yazdir();
list.ekle(300);
list.yazdir();

// listemizde nodeları silelim

list.sil(300);
list.yazdir();
list.sil(200);
list.yazdir();
list.sil(100);
list.yazdir();
}

References

1-Doç.Dr. Cem EVRENDİLEK ’ lecture notes

2-algolist.net

3-codeproject.com -Nasif M.