רשימה מקושרת כפולה היא סוג מורכב של רשימה מקושרת שבה צומת מכיל מצביע לצומת הקודם וגם לצומת הבא ברצף. לכן, ברשימה מקושרת כפולה, צומת מורכב משלושה חלקים: נתוני צומת, מצביע לצומת הבא ברצף (המצביע הבא), מצביע לצומת הקודם (המצביע הקודם). צומת לדוגמה ברשימה מקושרת כפולה מוצג באיור.

רשימה מקושרת כפולה המכילה שלושה צמתים עם מספרים מ-1 עד 3 בחלק הנתונים שלהם, מוצגת בתמונה הבאה.

ב-C, ניתן לתת מבנה של צומת ברשימה מקושרת כפולה כ:

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

ה הקודם חלק מהצומת הראשון וה- הַבָּא חלק מהצומת האחרון תמיד יכיל null המציין סוף לכל כיוון.

ברשימה מקושרת בודדת, נוכל לעבור רק בכיוון אחד, מכיוון שכל צומת מכיל כתובת של הצומת הבא ואין לו שום תיעוד של הצמתים הקודמים שלו. עם זאת, רשימה מקושרת כפול מתגברת על מגבלה זו של רשימה מקושרת יחידה. בשל העובדה שכל צומת ברשימה מכיל את הכתובת של הצומת הקודם שלו, נוכל למצוא את כל הפרטים על הצומת הקודם גם על ידי שימוש בכתובת הקודמת המאוחסנת בחלק הקודם של כל צומת.

ייצוג זיכרון של רשימה מקושרת כפולה

ייצוג זיכרון של רשימה מקושרת כפול מוצג בתמונה הבאה. בדרך כלל, רשימה מקושרת כפולה צורכת יותר מקום עבור כל צומת ולכן גורמת לפעולות בסיסיות רחבות יותר כגון הכנסה ומחיקה. עם זאת, אנו יכולים לתפעל בקלות את רכיבי הרשימה מכיוון שהרשימה שומרת על מצביעים בשני הכיוונים (קדימה ואחורה).

בתמונה הבאה, האלמנט הראשון של הרשימה, כלומר 13 מאוחסן בכתובת 1. מצביע הראש מצביע על כתובת ההתחלה 1. מכיוון שזהו האלמנט הראשון שמתווסף לרשימה ולכן הקודם של הרשימה מכיל ריק. הצומת הבא ברשימה נמצא בכתובת 4 ולכן הצומת הראשון מכיל 4 במצביע הבא שלו.

אנו יכולים לעבור את הרשימה בדרך זו עד שנמצא כל צומת המכיל null או -1 בחלק הבא שלו.

פעולות ברשימה מקושרת כפולה

יצירת צומת

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

כל הפעולות הנותרות לגבי רשימה מקושרת כפולה מתוארות בטבלה הבאה.

תוכנית מונחית תפריט ב-C כדי ליישם את כל הפעולות של רשימה מקושרת כפולה

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

תְפוּקָה

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