logo

Çift bağlantılı liste

Çift bağlantılı liste, bir düğümün dizideki önceki ve sonraki düğüme yönelik bir işaretçi içerdiği karmaşık bir bağlantılı liste türüdür. Bu nedenle, çift bağlantılı bir listede bir düğüm üç bölümden oluşur: düğüm verileri, sıradaki bir sonraki düğüme işaretçi (sonraki işaretçi), önceki düğüme işaretçi (önceki işaretçi). Şekilde çift bağlı listedeki örnek bir düğüm gösterilmektedir.


Çift bağlantılı liste

Veri kısmında 1'den 3'e kadar sayılara sahip üç düğüm içeren çift bağlantılı bir liste aşağıdaki resimde gösterilmektedir.


Çift bağlantılı liste

C'de çift bağlantılı listedeki bir düğümün yapısı şu şekilde verilebilir:

 struct node { struct node *prev; int data; struct node *next; } 

önceki ilk düğümün bir parçası ve Sonraki son düğümün bir kısmı her zaman her yönde sonu belirten boş değer içerecektir.

Tek bağlantılı bir listede yalnızca bir yönde hareket edebiliriz çünkü her düğüm bir sonraki düğümün adresini içerir ve önceki düğümlerin herhangi bir kaydına sahip değildir. Ancak çift bağlantılı liste, tek bağlantılı listenin bu sınırlamasını ortadan kaldırır. Listedeki her düğüm, bir önceki düğümün adresini içerdiğinden, her düğümün önceki kısmında saklanan önceki adresi kullanarak da bir önceki düğüme ilişkin tüm detayları bulabiliriz.

Çift bağlantılı bir listenin Bellek Temsili

Çift bağlantılı bir listenin Bellek Gösterimi aşağıdaki resimde gösterilmektedir. Genel olarak çift bağlantılı liste, her düğüm için daha fazla yer kaplar ve dolayısıyla ekleme, silme gibi temel işlemlerin daha kapsamlı olmasına neden olur. Ancak liste her iki yönde de (ileri ve geri) işaretçiler bulundurduğundan listenin öğelerini kolayca değiştirebiliriz.

Aşağıdaki görüntüde listenin ilk elemanı yani 13, adres 1'de saklanmaktadır. Baş işaretçisi başlangıç ​​adresi 1'i işaret etmektedir. Bu listeye eklenen ilk eleman olduğundan dolayı önceki listenin içerir hükümsüz. Listenin bir sonraki düğümü adres 4'te bulunur, dolayısıyla ilk düğüm bir sonraki işaretçisinde 4'ü içerir.

Bir sonraki bölümünde null veya -1 içeren herhangi bir düğüm bulana kadar listeyi bu şekilde dolaşabiliriz.


Çift bağlantılı liste

Çift bağlantılı listedeki işlemler

Düğüm Oluşturma

 struct node { struct node *prev; int data; struct node *next; }; struct node *head; 

Çift bağlantılı listeye ilişkin geri kalan tüm işlemler aşağıdaki tabloda açıklanmıştır.

SN Operasyon Tanım
1 Başlangıçta ekleme Düğümün başlangıçta bağlantılı listeye eklenmesi.
2 Sonunda ekleme Düğümün bağlantılı listenin sonuna eklenmesi.
3 Belirtilen düğümden sonra ekleme Düğümün, belirtilen düğümden sonra bağlantılı listeye eklenmesi.
4 Başlangıçta silme Düğümün listenin başından kaldırılması
5 Sonunda silme Düğümün listenin sonundan kaldırılması.
6 Veri verilen düğümün silinmesi Verilen verileri içeren düğümden hemen sonra bulunan düğümün kaldırılması.
7 Aranıyor Her düğüm verisini aranacak öğeyle karşılaştırın ve öğenin bulunması durumunda öğenin listedeki konumunu döndürün.
8 Geçiş Arama, sıralama, görüntüleme vb. gibi belirli işlemleri gerçekleştirmek için listedeki her düğümü en az bir kez ziyaret etmek.

Çift bağlantılı listenin tüm işlemlerini uygulamak için C'deki Menü Odaklı Program

 #include #include struct node { struct node *prev; struct node *next; int data; }; struct node *head; void insertion_beginning(); void insertion_last(); void insertion_specified(); void deletion_beginning(); void deletion_last(); void deletion_specified(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: insertion_beginning(); break; case 2: insertion_last(); break; case 3: insertion_specified(); break; case 4: deletion_beginning(); break; case 5: deletion_last(); break; case 6: deletion_specified(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void insertion_beginning() { struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter Item value'); scanf('%d',&item); if(head==NULL) { ptr->next = NULL; ptr->prev=NULL; ptr->data=item; head=ptr; } else { ptr->data=item; ptr->prev=NULL; ptr->next = head; head->prev=ptr; head=ptr; } printf('
Node inserted
'); } } void insertion_last() { struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value'); scanf('%d',&item); ptr->data=item; if(head == NULL) { ptr->next = NULL; ptr->prev = NULL; head = ptr; } else { temp = head; while(temp->next!=NULL) { temp = temp->next; } temp->next = ptr; ptr ->prev=temp; ptr->next = NULL; } } printf('
node inserted
'); } void insertion_specified() { struct node *ptr,*temp; int item,loc,i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
 OVERFLOW'); } else { temp=head; printf('Enter the location'); scanf('%d',&loc); for(i=0;inext; if(temp == NULL) { printf('
 There are less than %d elements', loc); return; } } printf('Enter value'); scanf('%d',&item); ptr->data = item; ptr->next = temp->next; ptr -> prev = temp; temp->next = ptr; temp->next->prev=ptr; printf('
node inserted
'); } } void deletion_beginning() { struct node *ptr; if(head == NULL) { printf('
 UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf('
node deleted
'); } else { ptr = head; head = head -> next; head -> prev = NULL; free(ptr); printf('
node deleted
'); } } void deletion_last() { struct node *ptr; if(head == NULL) { printf('
 UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf('
node deleted
'); } else { ptr = head; if(ptr->next != NULL) { ptr = ptr -> next; } ptr -> prev -> next = NULL; free(ptr); printf('
node deleted
'); } } void deletion_specified() { struct node *ptr, *temp; int val; printf('
 Enter the data after which the node is to be deleted : '); scanf('%d', &val); ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) { printf('
Can't delete
'); } else if(ptr -> next -> next == NULL) { ptr ->next = NULL; } else { temp = ptr -> next; ptr -> next = temp -> next; temp -> next -> prev = ptr; free(temp); printf('
node deleted
'); } } void display() { struct node *ptr; printf('
 printing values...
'); ptr = head; while(ptr != NULL) { printf('%d
',ptr->data); ptr=ptr->next; } } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('
item found at location %d ',i+1); flag=0; break; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('
Item not found
'); } } } 

Çıktı

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value12 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 2 Enter value89 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 3 Enter the location1 Enter value12345 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12345 12 89 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 4 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 5 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 12345 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 123 item found at location 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 Can't delete *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 9 Exited..