Двозв’язаний список — це складний тип зв’язаного списку, у якому вузол містить вказівник як на попередній, так і на наступний вузол у послідовності. Отже, у двозв’язаному списку вузол складається з трьох частин: даних вузла, покажчика на наступний вузол у послідовності (наступний покажчик), покажчика на попередній вузол (попередній покажчик). Зразок вузла у двозв’язаному списку показаний на малюнку.
На наступному зображенні показано подвійний зв’язаний список із трьома вузлами, які мають номери від 1 до 3 у частині даних.
У C структуру вузла у двозв’язаному списку можна подати так:
struct node { struct node *prev; int data; struct node *next; } The поперед частина першого вузла і в наступний частина останнього вузла завжди міститиме нуль, що вказуватиме кінець у кожному напрямку.
У однозв’язаному списку ми можемо рухатися лише в одному напрямку, тому що кожен вузол містить адресу наступного вузла, і він не має жодних записів своїх попередніх вузлів. Однак подвійно зв’язаний список долає це обмеження однозв’язаного списку. Через те, що кожен вузол списку містить адресу свого попереднього вузла, ми також можемо знайти всі подробиці про попередній вузол, використовуючи попередню адресу, збережену в попередній частині кожного вузла.
Пам'ять Представлення двозв'язаного списку
Зображення пам'яті двозв'язаного списку показано на наступному зображенні. Як правило, подвійний зв’язаний список займає більше місця для кожного вузла і, отже, спричиняє більші базові операції, такі як вставка та видалення. Однак ми можемо легко маніпулювати елементами списку, оскільки список підтримує покажчики в обох напрямках (вперед і назад).
На наступному зображенні перший елемент списку, тобто 13, зберігається за адресою 1. Головний покажчик вказує на початкову адресу 1. Оскільки це перший елемент, який додається до списку, тому поперед списку містить нуль. Наступний вузол списку знаходиться за адресою 4, тому перший вузол містить 4 у своєму наступному покажчику.
Ми можемо переглядати список таким чином, доки не знайдемо будь-який вузол, що містить null або -1 у своїй наступній частині.
Операції над двозв'язним списком
Створення вузла
struct node { struct node *prev; int data; struct node *next; }; struct node *head; Усі інші операції щодо двозв’язаного списку описані в наступній таблиці.
| SN | Операція | опис |
|---|---|---|
| 1 | Вставка на початку | Додавання вузла до пов’язаного списку на початку. |
| 2 | Вставка в кінці | Додавання вузла в пов'язаний список в кінець. |
| 3 | Вставка після вказаного вузла | Додавання вузла до пов’язаного списку після зазначеного вузла. |
| 4 | Видалення на початку | Видалення вузла з початку списку |
| 5 | Видалення в кінці | Видалення вузла з кінця списку. |
| 6 | Видалення вузла, який надав дані | Видалення вузла, який присутній одразу після вузла, що містить задані дані. |
| 7 | Пошук | Порівняння даних кожного вузла з елементом для пошуку та повернення розташування елемента в списку, якщо знайдений елемент, інакше поверне значення null. |
| 8 | Траверсування | Відвідування кожного вузла списку принаймні один раз, щоб виконати певну операцію, як-от пошук, сортування, відображення тощо. |
Програма на мові 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..