迴圈雙向鏈表是一種更複雜的數據結構類型，它的節點包含指向其前一節點以及下一節點的指針。 迴圈雙向鏈表在任何節點中都不包含NULL。 鏈表的最後一個節點包含列表的第一個節點的地址。 鏈表的第一個節點還包含的前一個指針是指向最後一個節點的地址。
迴圈雙向鏈表如下圖所示 -
由於迴圈雙向鏈表在其結構中包含三個部分，因此每個節點需要更多空間和更昂貴的基本操作。 但是，迴圈雙向鏈表提供了對指針更方便的操作，搜索效率提高了兩倍。
1. 迴圈雙向鏈表的記憶體管理
下圖顯示了為迴圈雙向鏈表分配記憶體的方式。 變數head包含鏈表的第一個元素的地址，即地址1，因此鏈表的起始節點包含數據A存儲在地址1中。因此，鏈表的每個節點應該具有三個部分，起始節點包含最後一個(也是前一個)節點的地址，即8和下一個節點，即4。鏈表的最後一個節點，存儲在地址8並包含數據6，包含鏈表的第一個節點的地址，如圖中所示，即地址1。在迴圈雙向鏈表中，最後一個節點由第一個節點的地址標識，該節點存儲在最後一個節點的next中，因此包含第一個節點地址的節點實際上是該節點的最後一個節點。
2. 迴圈雙向鏈表的操作
可以在迴圈雙鏈表上執行各種操作。迴圈雙鏈表的節點結構類似於雙向鏈表。 但是，迴圈雙向鏈表上的操作如下表所述。
| 編號 | 操作 | 描述 |
|---|---|---|
| 1 | 在開頭插入節點 | 在迴圈雙向鏈表的開頭添加節點。 |
| 2 | 在末尾插入節點 | 在迴圈雙向鏈表的末尾添加節點。 |
| 3 | 刪除開頭節點 | 刪除迴圈雙向鏈表開頭的節點。 |
| 4 | 刪除末尾節點 | 刪除迴圈雙向鏈表末尾的節點。 |
在迴圈雙向鏈表中遍曆和搜索類似於迴圈單鏈表中的遍曆和搜索，因此不再說明。
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 deletion_beginning();
void deletion_last();
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 Beginning\n2.Insert at last\n");
printf("3.Delete from Beginning\n4.Delete from last\n");
prinft("5.Search\n6.Show\n7.Exit\n");
printf("Enter your choice?\n");
scanf("\n%d", &choice);
switch (choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
deletion_beginning();
break;
case 4:
deletion_last();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("OVERFLOW");
}
else
{
printf("Enter Item value");
scanf("%d", &item);
ptr->data = item;
if (head == NULL)
{
head = ptr;
ptr->next = head;
ptr->prev = head;
}
else
{
temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = ptr;
ptr->prev = temp;
head->prev = ptr;
ptr->next = head;
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");
}
else
{
printf("Enter value");
scanf("%d", &item);
ptr->data = item;
if (head == NULL)
{
head = ptr;
ptr->next = head;
ptr->prev = head;
}
else
{
temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = ptr;
ptr->prev = temp;
head->prev = ptr;
ptr->next = head;
}
}
printf("node inserted\n");
}
void deletion_beginning()
{
struct node *temp;
if (head == NULL)
{
printf("UNDERFLOW");
}
else if (head->next == head)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = head->next;
head->next->prev = temp;
free(head);
head = temp->next;
}
}
void deletion_last()
{
struct node *ptr;
if (head == NULL)
{
printf("UNDERFLOW");
}
else if (head->next == head)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
ptr = head;
if (ptr->next != head)
{
ptr = ptr->next;
}
ptr->prev->next = head;
head->prev = ptr->prev;
free(ptr);
printf("node deleted\n");
}
}
void display()
{
struct node *ptr;
ptr = head;
if (head == NULL)
{
printf("nothing to print");
}
else
{
printf("printing values ... \n");
while (ptr->next != head)
{
printf("%d\n", ptr->data);
ptr = ptr->next;
}
printf("%d\n", ptr->data);
}
}
void search()
{
struct node *ptr;
int item, i = 0, flag = 1;
ptr = head;
if (ptr == NULL)
{
printf("Empty List\n");
}
else
{
printf("Enter item which you want to search?\n");
scanf("%d", &item);
if (head->data == item)
{
printf("item found at location %d", i + 1);
flag = 0;
}
else
{
while (ptr->next != head)
{
if (ptr->data == item)
{
printf("item found at location %d ", i + 1);
flag = 0;
break;
}
else
{
flag = 1;
}
i++;
ptr = ptr->next;
}
}
if (flag != 0)
{
printf("Item not found\n");
}
}
}
執行上面示例代碼，得到以下結果 -
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
1
Enter Item value123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
2
Enter value234
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
1
Enter Item value90
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
2
Enter value80
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
3
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
4
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
6
printing values ...
123
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
5
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 Beginning
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search
6.Show
7.Exit
Enter your choice?
7