TechCodeview

A duplán linkelt lista egy összetett típusú csatolt lista, amelyben egy csomópont tartalmaz egy mutatót a sorozat előző és következő csomópontjára. Ezért egy duplán linkelt listában egy csomópont három részből áll: csomópontadatok, mutató a sorrendben következő csomópontra (következő mutató) , mutató az előző csomópontra (előző mutató). Az ábrán látható egy minta csomópont egy duplán linkelt listában.

A következő képen egy duplán linkelt lista látható, amely három csomópontot tartalmaz, amelyek adatrészükben 1-től 3-ig terjednek.

C-ben a duplán linkelt listában lévő csomópont szerkezete a következőképpen adható meg:

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

A előz része az első csomópontnak és a következő az utolsó csomópont egy része mindig tartalmazni fogja a nullát jelző véget minden irányban.

Egy egyedileg linkelt listában csak egy irányba haladhatunk, mert minden csomópont tartalmazza a következő csomópont címét, és nincs rekordja az előző csomópontjairól. A duplán linkelt listák azonban felülmúlják az egyszeresen linkelt listák korlátait. Tekintettel arra, hogy a lista minden csomópontja tartalmazza az előző csomópont címét, minden részletet megtalálhatunk az előző csomópontról is az egyes csomópontok előző részében tárolt korábbi cím használatával.

Memória Duplán linkelt lista ábrázolása

Memória Egy duplán linkelt lista ábrázolása a következő képen látható. Általában a duplán linkelt lista minden csomóponthoz több helyet foglal el, és ezért kiterjedtebb alapműveleteket, például beszúrást és törlést eredményez. A lista elemeit azonban könnyen módosíthatjuk, mivel a lista mindkét irányba (előre és hátra) mutat mutatókat.

A következő képen a lista első eleme, azaz 13 az 1-es címen van tárolva. A fejmutató az 1-es kezdőcímre mutat. Mivel ez az első elem, amely a listához kerül, ezért a előz a listáról tartalmaz nulla. A lista következő csomópontja a 4-es címen található, ezért az első csomópont következő mutatójában 4-et tartalmaz.

Addig járhatunk így a listán, amíg a következő részében nem találunk nullát vagy -1-et tartalmazó csomópontot.

Műveletek duplán linkelt listán

Csomópont létrehozása

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

A duplán linkelt listával kapcsolatos összes többi műveletet a következő táblázat ismerteti.

Menüvezérelt program C nyelven a duplán linkelt lista összes műveletének végrehajtásához

 #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
'); } } } 

Kimenet

 *********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..