雙連結串列
雙向連結串列是一種複雜型別的連結串列，它的節點包含指向序列中前一個節點和下一個節點的指標。 因此，在雙向連結串列中，節點由三部分組成：節點資料，指向下一個節點的指標(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..