Eine doppelt verknüpfte Liste ist ein komplexer Typ einer verknüpften Liste, bei der ein Knoten einen Zeiger auf den vorherigen und den nächsten Knoten in der Sequenz enthält. Daher besteht ein Knoten in einer doppelt verknüpften Liste aus drei Teilen: Knotendaten, Zeiger auf den nächsten Knoten in der Reihenfolge (nächster Zeiger), Zeiger auf den vorherigen Knoten (vorheriger Zeiger). Ein Beispielknoten in einer doppelt verknüpften Liste ist in der Abbildung dargestellt.
Die folgende Abbildung zeigt eine doppelt verknüpfte Liste mit drei Knoten, deren Datenteil Nummern von 1 bis 3 aufweist.
In C kann die Struktur eines Knotens in einer doppelt verknüpften Liste wie folgt angegeben werden:
struct node { struct node *prev; int data; struct node *next; } Der vorh Teil des ersten Knotens und der nächste Ein Teil des letzten Knotens enthält immer Null, was das Ende in jede Richtung angibt.
In einer einfach verknüpften Liste könnten wir nur in eine Richtung durchlaufen, da jeder Knoten die Adresse des nächsten Knotens enthält und keine Aufzeichnung seiner vorherigen Knoten hat. Doppelt verknüpfte Listen überwinden jedoch diese Einschränkung einfach verknüpfter Listen. Aufgrund der Tatsache, dass jeder Knoten der Liste die Adresse seines vorherigen Knotens enthält, können wir auch alle Details über den vorherigen Knoten finden, indem wir die vorherige Adresse verwenden, die im vorherigen Teil jedes Knotens gespeichert ist.
Speicherdarstellung einer doppelt verknüpften Liste
Die Speicherdarstellung einer doppelt verknüpften Liste ist in der folgenden Abbildung dargestellt. Im Allgemeinen benötigen doppelt verknüpfte Listen mehr Platz für jeden Knoten und erfordern daher umfangreichere Grundoperationen wie Einfügen und Löschen. Allerdings können wir die Elemente der Liste leicht manipulieren, da die Liste Zeiger in beide Richtungen (vorwärts und rückwärts) verwaltet.
In der folgenden Abbildung wird das erste Element der Liste, d. h. 13, an Adresse 1 gespeichert. Der Kopfzeiger zeigt auf die Startadresse 1. Da dies das erste Element ist, das der Liste hinzugefügt wird, ist dies der Fall vorh der Liste enthält Null. Der nächste Knoten der Liste befindet sich an der Adresse 4, daher enthält der erste Knoten 4 in seinem nächsten Zeiger.
Wir können die Liste auf diese Weise durchlaufen, bis wir im nächsten Teil einen Knoten finden, der null oder -1 enthält.
Operationen auf einer doppelt verknüpften Liste
Knotenerstellung
struct node { struct node *prev; int data; struct node *next; }; struct node *head; Alle verbleibenden Vorgänge in Bezug auf doppelt verknüpfte Listen werden in der folgenden Tabelle beschrieben.
| SN | Betrieb | Beschreibung |
|---|---|---|
| 1 | Einfügung am Anfang | Hinzufügen des Knotens zu Beginn zur verknüpften Liste. |
| 2 | Einfügung am Ende | Hinzufügen des Knotens zur verknüpften Liste am Ende. |
| 3 | Einfügung nach dem angegebenen Knoten | Hinzufügen des Knotens zur verknüpften Liste nach dem angegebenen Knoten. |
| 4 | Löschung am Anfang | Entfernen des Knotens vom Anfang der Liste |
| 5 | Löschung am Ende | Entfernen des Knotens vom Ende der Liste. |
| 6 | Löschung des Knotens, der Daten angegeben hat | Entfernen des Knotens, der direkt nach dem Knoten vorhanden ist, der die angegebenen Daten enthält. |
| 7 | Suchen | Vergleichen Sie die Daten jedes Knotens mit dem zu durchsuchenden Element und geben Sie die Position des Elements in der Liste zurück, wenn das gefundene Element andernfalls Null zurückgibt. |
| 8 | Überqueren | Besuchen Sie jeden Knoten der Liste mindestens einmal, um einen bestimmten Vorgang wie Suchen, Sortieren, Anzeigen usw. auszuführen. |
Menügesteuertes Programm in C zur Implementierung aller Operationen einer doppelt verknüpften Liste
#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
'); } } } Ausgabe
*********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..