循環(huán)雙向鏈表是一種更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)類型匹耕，它的節(jié)點(diǎn)包含指向其前一節(jié)點(diǎn)以及下一節(jié)點(diǎn)的指針秧廉。 循環(huán)雙向鏈表在任何節(jié)點(diǎn)中都不包含NULL荧库。 鏈表的最后一個(gè)節(jié)點(diǎn)包含列表的第一個(gè)節(jié)點(diǎn)的地址膛壹。 鏈表的第一個(gè)節(jié)點(diǎn)還包含的前一個(gè)指針是指向最后一個(gè)節(jié)點(diǎn)的地址驾中。
循環(huán)雙向鏈表如下圖所示 -
image
由于循環(huán)雙向鏈表在其結(jié)構(gòu)中包含三個(gè)部分豆巨，因此每個(gè)節(jié)點(diǎn)需要更多空間和更昂貴的基本操作解寝。 但是痊远，循環(huán)雙向鏈表提供了對(duì)指針更方便的操作枚碗，搜索效率提高了兩倍想际。
1. 循環(huán)雙向鏈表的內(nèi)存管理
下圖顯示了為循環(huán)雙向鏈表分配內(nèi)存的方式损趋。 變量head包含鏈表的第一個(gè)元素的地址茫虽，即地址1屎勘，因此鏈表的起始節(jié)點(diǎn)包含數(shù)據(jù)A存儲(chǔ)在地址1中侄柔。因此共啃，鏈表的每個(gè)節(jié)點(diǎn)應(yīng)該具有三個(gè)部分，起始節(jié)點(diǎn)包含最后一個(gè)(也是前一個(gè))節(jié)點(diǎn)的地址暂题，即8和下一個(gè)節(jié)點(diǎn)移剪，即4。鏈表的最后一個(gè)節(jié)點(diǎn)薪者，存儲(chǔ)在地址8并包含數(shù)據(jù)6纵苛，包含鏈表的第一個(gè)節(jié)點(diǎn)的地址，如圖中所示言津，即地址1攻人。在循環(huán)雙向鏈表中，最后一個(gè)節(jié)點(diǎn)由第一個(gè)節(jié)點(diǎn)的地址標(biāo)識(shí)悬槽，該節(jié)點(diǎn)存儲(chǔ)在最后一個(gè)節(jié)點(diǎn)的next中怀吻，因此包含第一個(gè)節(jié)點(diǎn)地址的節(jié)點(diǎn)實(shí)際上是該節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)。
image
2. 循環(huán)雙向鏈表的操作
可以在循環(huán)雙鏈表上執(zhí)行各種操作初婆。循環(huán)雙鏈表的節(jié)點(diǎn)結(jié)構(gòu)類似于雙向鏈表蓬坡。 但是，循環(huán)雙向鏈表上的操作如下表所述磅叛。
| 編號(hào) | 操作 | 描述 |
|---|---|---|
| 1 | 在開頭插入節(jié)點(diǎn) | 在循環(huán)雙向鏈表的開頭添加節(jié)點(diǎn)屑咳。 |
| 2 | 在末尾插入節(jié)點(diǎn) | 在循環(huán)雙向鏈表的末尾添加節(jié)點(diǎn)。 |
| 3 | 刪除開頭節(jié)點(diǎn) | 刪除循環(huán)雙向鏈表開頭的節(jié)點(diǎn)弊琴。 |
| 4 | 刪除末尾節(jié)點(diǎn) | 刪除循環(huán)雙向鏈表末尾的節(jié)點(diǎn)乔宿。 |
在循環(huán)雙向鏈表中遍歷和搜索類似于循環(huán)單鏈表中的遍歷和搜索，因此不再說明访雪。
C語(yǔ)言實(shí)現(xiàn)的示例代碼 -
#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");
}
}
}
執(zhí)行上面示例代碼详瑞，得到以下結(jié)果 -
*********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
