循环链表

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

在循环单链表中，链表的最后一个节点包含一个指向链表第一个节点的指针。我们可以有循环单链表，也可以有循环双链表。

我们遍历循环单链表，直到到达我们开始的同一个节点。循环单链表没有开始也没有结束。任何节点的下一个部分都没有空值。

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

循环链表主要用于操作系统中的任务维护。在计算机科学中有许多循环链表的使用示例，包括浏览器浏览，其中用户过去访问的页面记录以循环链表的形式维护，并且可以通过单击“上一个”按钮再次访问。

循环链表的内存表示

在下面的图像中，循环链表的内存表示包含了一个学生在4门学科中的分数。然而，这张图片只是展示了循环链表在内存中存储的概览。链表的开始或头部指向索引为1的元素，数据部分包含13，下一个部分包含4。这意味着它连接到链表中存储在索引4的节点。

然而，由于我们考虑的是内存中的循环链表，因此链表的最后一个节点包含指向链表第一个节点的地址。

我们也可以在内存中有多个链表，具有指向列表中不同开始节点的不同开始指针。最后一个节点由其下一个部分标识，该部分包含列表开始节点的地址。我们必须能够识别任何链表的最后一个节点，以便在遍历列表时找出需要执行的迭代次数。

循环单链表上的操作

插入

序号	操作	描述
1	在开头插入	在循环单链表的开头添加一个节点。
2	在末尾插入	在循环单链表的末尾添加一个节点。

删除与遍历

序号	操作	描述
1	在开头删除	从循环单链表的开头删除节点。
2	在末尾删除	从循环单链表的末尾删除节点。
3	搜索	比较节点中的每个元素与给定项，并返回项在列表中出现的位置，否则返回null。
4	遍历	至少访问列表中的每个元素一次，以执行某些特定操作。

用C语言实现的菜单驱动程序，用于实现所有操作

在循环单链表上

示例

#include<stdio.h>
#include<stdlib.h>
struct node 
{
	int data;
	struct node *next; 
};
struct node *head;

void beginsert (); 
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
	int choice =0;
	while(choice != 7) 
	{
		printf("\n*********Main Menu*********\n");
		printf("\nChoose one option from the following list ...\n");
		printf("\n===============================================\n");
		printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search for an element\n6.Show\n7.Exit\n");
		printf("\nEnter your choice?\n");		
		scanf("\n%d",&choice);
		switch(choice)
		{
			case 1:
			beginsert();	
			break;
			case 2:
			lastinsert();		
			break;
			case 3:
			begin_delete();		
			break;
			case 4:
			last_delete();		
			break;
			case 5:
			search();		
			break;
			case 6:
			display();		
			break;
			case 7:
			exit(0);
			break;
			default:
			printf("Please enter valid choice..");
		}
	}
}
void beginsert()
{
	struct node *ptr,*temp; 
	int item; 
	ptr = (struct node *)malloc(sizeof(struct node));
	if(ptr == NULL)
	{
		printf("\nOVERFLOW");
	}
	else 
	{
		printf("\nEnter the node data?");
		scanf("%d",&item);
		ptr -> data = item;
		if(head == NULL)
		{
			head = ptr;
			ptr -> next = head;
		}
		else 
		{	
			temp = head;
			while(temp->next != head)
				temp = temp->next;
			ptr->next = head; 
			temp -> next = ptr; 
			head = ptr;
		} 
		printf("\nnode inserted\n");
	}
			
}
void lastinsert()
{
	struct node *ptr,*temp; 
	int item;
	ptr = (struct node *)malloc(sizeof(struct node));
	if(ptr == NULL)
	{
		printf("\nOVERFLOW\n");
	}
	else
	{
		printf("\nEnter Data?");
		scanf("%d",&item);
		ptr->data = item;
		if(head == NULL)
		{
			head = ptr;
			ptr -> next = head;	
		}
		else
		{
			temp = head;
			while(temp -> next != head)
			{
				temp = temp -> next;
			}
			temp -> next = ptr; 
			ptr -> next = head;
		}
		
		printf("\nnode inserted\n");
	}

}

void begin_delete()
{
	struct node *ptr; 
	if(head == NULL)
	{
		printf("\nUNDERFLOW");	
	}
	else if(head->next == head)
	{
		head = NULL;
		free(head);
		printf("\nnode deleted\n");
	}
	
	else
	{	ptr = head; 
		while(ptr -> next != head)
			ptr = ptr -> next; 
		ptr->next = head->next;
		free(head);
		head = ptr->next;
		printf("\nnode deleted\n");

	}
}
void last_delete()
{
	struct node *ptr, *preptr;
	if(head==NULL)
	{
		printf("\nUNDERFLOW");
	}
	else if (head ->next == head)
	{
		head = NULL;
		free(head);
		printf("\nnode deleted\n");

	}
	else 
	{
		ptr = head;
		while(ptr ->next != head)
		{
			preptr=ptr;
			ptr = ptr->next;
		}
		preptr->next = ptr -> next;
		free(ptr);
		printf("\nnode deleted\n");

	}
}

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");
		}
	}	
		
}

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);
	}
			
}

编译并运行

输出

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
1

Enter the node data?10

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
2

Enter Data?20

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
2

Enter Data?30

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
3

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.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.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
5

Enter item which you want to search?
20
item found at location 1
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?
6

 printing values ... 
20

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
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

联系信息

关注我们

教程

面试题

在线编译器