雙向鏈表是一種複雜類型的鏈表，它的節點包含指向序列中前一個節點和下一個節點的指針。 因此，在雙向鏈表中，節點由三部分組成：節點數據，指向下一個節點的指針(next指針)，指向前一個節點的指針(prev指針)。 雙向鏈表中的示例節點如圖所示。
包含三個節點的雙向鏈表在其數據部分中具有從1到3的數值，如下圖所示。
在C語言中，雙向鏈表中節點的結構體如下所示：
struct node
{
struct node *prev;
int data;
struct node *next;
}
第一個節點的prev部分和最後一個節點的next部分將始終包含指向NULL值。
在單鏈表中，只能在一個方向上遍曆，因為每個節點包含下一個節點的地址，並且它沒有其先前節點的任何記錄。 然而，雙重鏈表克服了單鏈表的這種限制。 由於列表的每個節點都包含其先前節點的地址，因此可以通過使用存儲在每個節點的前一部分內的先前地址來找到關於前一節點的所有細節。
1. 雙重鏈表記憶體表示
雙向鏈表的記憶體表示如下圖所示。 通常，雙向鏈表為每個節點消耗更多空間，因此它有更廣泛的基本操作，例如：插入和刪除。 但是，可以輕鬆地操作鏈表中的元素，因為鏈表在兩個方向(向前和向後)都保存指針。
在下面的圖像中，鏈表的第一個元素即13存儲在地址1中。頭指針指向起始地址1。由於這是第一個添加到鏈表的元素，因此鏈表的prev包含null。 鏈表的下一個節點位於地址4，因此第一個節點在其下一個指針(Next)中包含4。
可以用這種方式遍曆鏈表，直到在下一部分找到包含null或-1的節點。
2. 雙向鏈表上的操作
節點創建
struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;
有關雙向鏈表的所有操作如下表所述。
| 編號 | 操作 | 描述 |
|---|---|---|
| 1 | 在開頭插入節點 | 在鏈表的開頭添加節點。 |
| 2 | 在末尾插入節點 | 在鏈表的末尾添加節點。 |
| 3 | 在指定位置插入節點 | 在鏈表的指定位置之後插入節點。 |
| 4 | 在開頭刪除節點 | 從鏈表的開頭刪除節點。 |
| 5 | 在末尾刪除節點 | 從鏈表末尾刪除節點。 |
| 6 | 刪除給定數據的節點 | 刪除包含給定數據的節點。 |
| 7 | 搜索 | 將每個節點數據與要搜索的資料項目進行比較，如果找到資料項目則返回null，則返回鏈表中資料項目的位置。 |
| 8 | 遍曆 | 訪問鏈表的每個節點至少一次，以執行某些特定操作，如：搜索，排序，顯示等。 |
C語言程式實現雙向鏈表的所有操作，示例代碼如下 -
#include<stdio.h>
#include<stdlib.h>
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*********\n");
printf("Choose one option from the following list ...\n");
printf("===============================================\n");
printf("1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");
printf("Enter your choice?\n");
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\n");
}
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\n");
}
}
void insertion_last()
{
struct node *ptr, *temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("OVERFLOW\n");
}
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\n");
}
void insertion_specified()
{
struct node *ptr, *temp;
int item, loc, i;
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("OVERFLOW\n");
}
else
{
temp = head;
printf("Enter the location ");
scanf("%d", &loc);
for (i = 0;i < loc;i++)
{
temp = temp->next;
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\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if (head == NULL)
{
printf("UNDERFLOW\n");
}
else if (head->next == NULL)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
ptr = head;
head = head->next;
head->prev = NULL;
free(ptr);
printf("node deleted\n");
}
}
void deletion_last()
{
struct node *ptr;
if (head == NULL)
{
printf("UNDERFLOW\n");
}
else if (head->next == NULL)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
ptr = head;
if (ptr->next != NULL)
{
ptr = ptr->next;
}
ptr->prev->next = NULL;
free(ptr);
printf("node deleted\n");
}
}
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\n");
}
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\n");
}
}
void display()
{
struct node *ptr;
printf("printing values...\n");
ptr = head;
while (ptr != NULL)
{
printf("%d\n", ptr->data);
ptr = ptr->next;
}
}
void search()
{
struct node *ptr;
int item, i = 0, flag;
ptr = head;
if (ptr == NULL)
{
printf("Empty List\n");
}
else
{
printf("Enter item which you want to search?\n");
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\n");
}
}
}
執行上面示例代碼，結果如下 -
*********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..