Dubbel gekoppelde lijst is een complex type gekoppelde lijst waarin een knooppunt een verwijzing bevat naar zowel het vorige als het volgende knooppunt in de reeks. Daarom bestaat een knooppunt in een dubbel gekoppelde lijst uit drie delen: knooppuntgegevens, aanwijzer naar het volgende knooppunt in de reeks (volgende aanwijzer), aanwijzer naar het vorige knooppunt (vorige aanwijzer). Een voorbeeldknooppunt in een dubbel gekoppelde lijst wordt weergegeven in de figuur.
Een dubbel gekoppelde lijst met drie knooppunten met nummers van 1 tot 3 in hun gegevensgedeelte wordt weergegeven in de volgende afbeelding.
In C kan de structuur van een knooppunt in een dubbel gekoppelde lijst worden gegeven als:
struct node { struct node *prev; int data; struct node *next; } De vorige een deel van het eerste knooppunt en de volgende een deel van het laatste knooppunt zal altijd een nul bevatten die het einde in elke richting aangeeft.
In een enkelvoudig gekoppelde lijst kunnen we slechts in één richting doorlopen, omdat elk knooppunt het adres van het volgende knooppunt bevat en geen enkele registratie heeft van de vorige knooppunten. Dubbel gekoppelde lijsten overwinnen echter deze beperking van enkelvoudig gekoppelde lijsten. Vanwege het feit dat elk knooppunt van de lijst het adres van het vorige knooppunt bevat, kunnen we ook alle details over het vorige knooppunt vinden door het vorige adres te gebruiken dat in het vorige deel van elk knooppunt is opgeslagen.
Geheugen Weergave van een dubbel gekoppelde lijst
Geheugen De weergave van een dubbel gekoppelde lijst wordt weergegeven in de volgende afbeelding. Over het algemeen neemt een dubbel gekoppelde lijst meer ruimte in beslag voor elk knooppunt en veroorzaakt daarom uitgebreidere basisbewerkingen, zoals invoegen en verwijderen. We kunnen de elementen van de lijst echter gemakkelijk manipuleren, omdat de lijst verwijzingen in beide richtingen behoudt (vooruit en achteruit).
In de volgende afbeelding is het eerste element van de lijst, dat wil zeggen 13, opgeslagen op adres 1. De hoofdaanwijzer wijst naar het startadres 1. Aangezien dit het eerste element is dat aan de lijst wordt toegevoegd, is de vorige van de lijst bevat nul. Het volgende knooppunt van de lijst bevindt zich op adres 4, daarom bevat het eerste knooppunt 4 in de volgende pointer.
We kunnen op deze manier door de lijst lopen totdat we in het volgende deel een knooppunt vinden dat nul of -1 bevat.
Bewerkingen op dubbel gekoppelde lijst
Knooppunt creatie
struct node { struct node *prev; int data; struct node *next; }; struct node *head; Alle resterende bewerkingen met betrekking tot dubbel gekoppelde lijsten worden in de volgende tabel beschreven.
| SN | Operatie | Beschrijving |
|---|---|---|
| 1 | Invoeging aan het begin | Het knooppunt aan het begin aan de gekoppelde lijst toevoegen. |
| 2 | Invoeging aan het einde | Het knooppunt aan het einde van de gekoppelde lijst toevoegen. |
| 3 | Invoeging na gespecificeerd knooppunt | Het knooppunt toevoegen aan de gekoppelde lijst na het opgegeven knooppunt. |
| 4 | Verwijdering aan het begin | Het knooppunt aan het begin van de lijst verwijderen |
| 5 | Verwijdering aan het einde | Het knooppunt aan het einde van de lijst verwijderen. |
| 6 | Verwijdering van het knooppunt dat gegevens heeft verstrekt | Het verwijderen van het knooppunt dat aanwezig is net na het knooppunt dat de gegeven gegevens bevat. |
| 7 | Zoeken | Het vergelijken van de gegevens van elk knooppunt met het item dat moet worden doorzocht en het retourneren van de locatie van het item in de lijst als het anders gevonden item nul retourneert. |
| 8 | Doorkruisen | Elk knooppunt van de lijst minstens één keer bezoeken om een specifieke bewerking uit te voeren, zoals zoeken, sorteren, weergeven, enz. |
Menugestuurd programma in C om alle bewerkingen van een dubbel gekoppelde lijst te implementeren
#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
'); } } } Uitvoer
*********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..