Veri Yapısı - Çift Bağlantılı Liste

Çift Bağlantılı Liste, Tek Bağlantılı Liste ile karşılaştırıldığında ileri ve geri kolayca gezinmenin her iki şekilde de mümkün olduğu Bağlantılı listenin bir varyasyonudur. Aşağıdakiler, çift bağlantılı liste kavramını anlamak için önemli terimlerdir.

Link - Bağlantılı bir listenin her bağlantısı, öğe adı verilen bir veriyi depolayabilir.
Next - Bağlantılı listenin her bağlantısı, Sonraki adlı sonraki bağlantıya bir bağlantı içerir.
Prev - Bağlantılı bir listenin her bağlantısı, Önceki adlı önceki bağlantıya bir bağlantı içerir.
LinkedList - Bağlantılı Liste, İlk adlı ilk bağlantıya ve Son adlı son bağlantıya bağlantı bağlantısını içerir.

Çift Bağlantılı Liste Temsili

Yukarıdaki şekle göre, dikkate alınması gereken önemli noktalar aşağıdadır.

Çift Bağlantılı Liste, ilk ve son olarak adlandırılan bir bağlantı öğesi içerir.
Her bağlantı bir veri alanı ve next ve prev olarak adlandırılan iki bağlantı alanı taşır.
Her bağlantı, bir sonraki bağlantısı kullanılarak bir sonraki bağlantıya bağlanır.
Her bağlantı, önceki bağlantısı kullanılarak önceki bağlantıya bağlanır.
Son bağlantı, listenin sonunu işaretlemek için boş olarak bir bağlantı taşır.

Temel işlemler

Bir liste tarafından desteklenen temel işlemler aşağıdadır.

Insertion - Listenin başına bir öğe ekler.
Deletion - Listenin başındaki bir öğeyi siler.
Insert Last - Listenin sonuna bir öğe ekler.
Delete Last - Listenin sonundaki bir öğeyi siler.
Insert After - Listedeki bir öğeden sonra bir öğe ekler.
Delete - tuşunu kullanarak listeden bir öğeyi siler.
Display forward - Tam listeyi ileriye doğru görüntüler.
Display backward - Tam listeyi geriye doğru görüntüler.

Yerleştirme İşlemi

Aşağıdaki kod, çift bağlantılı bir listenin başlangıcındaki ekleme işlemini gösterir.

Misal

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Silme İşlemi

Aşağıdaki kod, çift bağlantılı bir listenin başlangıcındaki silme işlemini gösterir.

Misal

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Bir İşlemin Sonunda Yerleştirme

Aşağıdaki kod, çift bağlantılı listenin son konumundaki ekleme işlemini gösterir.

Misal

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Uygulamayı C programlama dilinde görmek için lütfen buraya tıklayın .