القائمة المرتبطة بشكل مضاعف هي نوع معقد من القائمة المرتبطة التي تحتوي فيها العقدة على مؤشر إلى العقدة السابقة وكذلك العقدة التالية في التسلسل. لذلك، في القائمة المرتبطة بشكل مزدوج، تتكون العقدة من ثلاثة أجزاء: بيانات العقدة، مؤشر إلى العقدة التالية بالتسلسل (المؤشر التالي)، مؤشر إلى العقدة السابقة (المؤشر السابق). يظهر في الشكل عقدة نموذجية في قائمة مرتبطة بشكل مزدوج.

تظهر في الصورة التالية قائمة مرتبطة بشكل مزدوج تحتوي على ثلاث عقد تحتوي على أرقام من 1 إلى 3 في جزء البيانات الخاص بها.

في لغة C، يمكن إعطاء بنية العقدة في القائمة المرتبطة بشكل مزدوج على النحو التالي:

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

ال السابق جزء من العقدة الأولى و التالي سيحتوي جزء من العقدة الأخيرة دائمًا على قيمة فارغة تشير إلى النهاية في كل اتجاه.

في القائمة المرتبطة منفردة، يمكننا المرور في اتجاه واحد فقط، لأن كل عقدة تحتوي على عنوان العقدة التالية ولا تحتوي على أي سجل للعقد السابقة. ومع ذلك، فإن القائمة المرتبطة بشكل مضاعف تتغلب على هذا القيد المتمثل في القائمة المرتبطة بشكل فردي. ونظرًا لأن كل عقدة في القائمة تحتوي على عنوان العقدة السابقة لها، فيمكننا العثور على جميع التفاصيل حول العقدة السابقة أيضًا باستخدام العنوان السابق المخزن داخل الجزء السابق من كل عقدة.

تمثيل الذاكرة لقائمة مرتبطة بشكل مزدوج

الذاكرة يظهر تمثيل القائمة المرتبطة بشكل مزدوج في الصورة التالية. بشكل عام، تستهلك القائمة المرتبطة بشكل مزدوج مساحة أكبر لكل عقدة، وبالتالي تؤدي إلى عمليات أساسية أكثر اتساعًا مثل الإدراج والحذف. ومع ذلك، يمكننا بسهولة التعامل مع عناصر القائمة حيث أن القائمة تحتفظ بمؤشرات في كلا الاتجاهين (للأمام والخلف).

في الصورة التالية، العنصر الأول في القائمة، أي 13 مخزن في العنوان 1. يشير مؤشر الرأس إلى عنوان البداية 1. وبما أن هذا هو العنصر الأول الذي تتم إضافته إلى القائمة، فإن السابق من القائمة يتضمن باطل. العقدة التالية من القائمة موجودة في العنوان 4 وبالتالي فإن العقدة الأولى تحتوي على 4 في المؤشر التالي.

يمكننا اجتياز القائمة بهذه الطريقة حتى نجد أي عقدة تحتوي على قيمة خالية أو -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..