在迴圈單鏈表中，鏈表的最後一個節點包含指向鏈表的第一個節點的指針。可以有迴圈單向鏈表以及迴圈雙鏈表。
遍曆一個迴圈單鏈表，直到到達開始的同一個節點。迴圈單鏈表類似於鏈表，但它沒有開始也沒有結束。任何節點的下一部分都不存在NULL值。
下圖顯示了一個迴圈單鏈表。
迴圈鏈表主要用於操作系統中的任務維護。有許多例子，迴圈鏈表用於電腦科學，包括流覽器，記錄用戶過去訪問過的頁面記錄也可以以迴圈鏈表的形式保存，並且可以在點擊前一個按鈕時再次訪問。
1. 迴圈鏈表的記憶體表示
在下圖中，包含4個科目中學生分數的迴圈鏈表的記憶體表示形式。但是，該圖顯示了迴圈列表如何存儲在內存中。鏈表的開頭或head指向索引為1的元素，data部分包含分數值為13，next部分包含地址為4。它與存儲在鏈表的第4個索引處的節點鏈接。
但是，由於記憶體中是迴圈鏈表，因此鏈表的最後一個節點包含鏈表的第一個節點的地址。
還可以在內存中有多個鏈表，並且不同的起始指針指向鏈表中的不同起始節點。 最後一個節點由其next部分標識，該部分包含鏈表的起始節點的地址。必須能夠識別任何鏈表的最後一個節點，以便可以找到遍曆鏈表時需要執行的迭代次數。
2. 迴圈單向鏈表上的操作
2.1. 插入
| 編號 | 操作 | 描述 |
|---|---|---|
| 1 | 插入開頭 | 將節點添加到迴圈單鏈表的開頭。 |
| 2 | 插入未尾 | 將節點添加到迴圈單鏈表的未尾。 |
2.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("*********Main Menu*********\n");
printf("Choose one option from the following list ...\n");
printf("===============================================\n");
printf("1.Insert in begining\n2.Insert at last\n");
printf("3.Delete from Beginning\n4.Delete from last\n");
printf("5.Search for an element\n6.Show\n7.Exit\n");
printf("Enter your choice?\n");
scanf("%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("OVERFLOW");
}
else
{
printf("Enter 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("node inserted\n");
}
}
void lastinsert()
{
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("OVERFLOW\n");
}
else
{
printf("Enter 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("node inserted\n");
}
}
void begin_delete()
{
struct node *ptr;
if (head == NULL)
{
printf("UNDERFLOW");
}
else if (head->next == head)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
ptr = head;
while (ptr->next != head)
ptr = ptr->next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("node deleted\n");
}
}
void last_delete()
{
struct node *ptr, *preptr;
if (head == NULL)
{
printf("UNDERFLOW");
}
else if (head->next == head)
{
head = NULL;
free(head);
printf("node deleted\n");
}
else
{
ptr = head;
while (ptr->next != head)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = ptr->next;
free(ptr);
printf("node deleted\n");
}
}
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");
}
}
}
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);
}
}
執行上面示例代碼，得到以下結果 -
*********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