循环双向链表

2025年4月21日 | 6分钟阅读

循环双向链表是一种更复杂的数据结构，其中一个节点包含指向其前一个节点和下一个节点的指针。循环双向链表中没有任何节点包含 NULL。链表的最后一个节点包含链表第一个节点的地址。链表的第一个节点在其前驱指针中也包含最后一个节点的地址。

下图显示了一个循环双向链表。

由于循环双向链表的结构包含三个部分，因此它在每个节点上需要更多的空间，并且基本操作的开销也更大。但是，循环双向链表提供了方便的指针操作，并且搜索效率提高了一倍。

循环双向链表的内存管理

下图显示了为循环双向链表分配内存的方式。变量 head 包含链表第一个元素的地址，即 1，因此链表的起始节点包含数据 A，存储在地址 1。由于链表的每个节点都应该包含三个部分，因此链表的起始节点包含最后一个节点的地址，即 8，以及下一个节点，即 4。链表中存储在地址 8 并包含数据 6 的最后一个节点，包含链表第一个节点的地址，如图所示，即 1。在循环双向链表中，最后一个节点通过存储在最后一个节点 next 部分的第一个节点的地址来识别，因此包含第一个节点地址的节点实际上是链表的最后一个节点。

循环双向链表上的操作

可以在循环双向链表上执行各种操作。循环双向链表的节点结构与双向链表类似。但是，循环双向链表上的操作在下表中描述。

序号	操作	描述
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("\n*********Main Menu*********\n");
		printf("\nChoose one option from the following list ...\n");
		printf("\n===============================================\n");
		printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search\n6.Show\n7.Exit\n");
		printf("\nEnter 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("\nOVERFLOW");
   }
   else
   {
    printf("\nEnter 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("\nNode inserted\n");
}
   
}
void insertion_last()
{
   struct node *ptr,*temp;
   int item;
   ptr = (struct node *) malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
       printf("\nEnter 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("\nnode inserted\n");
}

void deletion_beginning()
{
    struct node *temp;
    if(head == NULL)
	{
		printf("\n UNDERFLOW");
	}
	else if(head->next == head)
	{
		head = NULL; 
		free(head);
		printf("\nnode 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("\n UNDERFLOW");
	}
	else if(head->next == head)
	{
		head = NULL; 
		free(head);	
		printf("\nnode deleted\n");
	}
	else 
	{
		ptr = head; 
		if(ptr->next != head)
		{
			ptr = ptr -> next; 
		}
		ptr -> prev -> next = head;
		head -> prev = ptr -> prev;  
		free(ptr);
		printf("\nnode deleted\n");
	}
}

void display()
{
	struct node *ptr;
	ptr=head;
	if(head == NULL)
	{
		printf("\nnothing to print");
	}	
	else
	{
		printf("\n 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("\nEmpty List\n");
	}
	else
	{ 
		printf("\nEnter 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

下一主题数据结构中的栈

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

循环双向链表

循环双向链表的内存管理

循环双向链表上的操作

C 语言实现循环双向链表所有操作的程序

示例

相关帖子

双向链表

循环链表

数据结构中的链表

单向链表

链表类型

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器