# 数据结构&算法 循环链表

• ## 循环链表

循环链表是链表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表。
• ## 单链表作为循环

在单链表中，最后一个节点的下一个指针指向第一个节点。 • ## 双向链表作为循环

在双链表中，最后一个节点的下一个指针指向第一个节点，第一个节点的前一个指针指向最后一个节点，在两个方向上循环。 根据上面的说明，以下是要考虑的重点。
• 无论是单链列表还是双链表，最后一个链接的下一个都指向列表的第一个链接。
• 如果是双向链接列表，则第一个链接的前一个指向列表的最后一个节点。
• ## 基本操作

以下是循环链表支持的基本操作。
• 插入 -在列表的开头添加一个元素。
• 删除 -删除列表开头的元素。
• 显示 -显示列表。
• ## 插入操作

以下代码演示了基于单个链接列表的循环链接列表中的插入操作。
``````
insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
else
while next of temp is not head, do
temp := next of temp
done
next of temp := node
end if
End
```
```
• ## 删除操作

以下代码演示了基于单个链表的循环链表中的删除操作。-
``````
deleteFirst():
Begin
it is Underflow and return
else
while next of ptr is not head, do
ptr := next of ptr
next of ptr = next of head
end if
End
```
```
• ## 显示列表操作

下面的代码演示了循环链接列表中的显示列表操作。
``````
display():
Begin
Nothing to print and return
else
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End
```
```
• ## 循环链表的C语言实现

循环链表是链表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表。
``````
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;

struct node *next;
};

struct node *current = NULL;

bool isEmpty() {
}

int length() {
int length = 0;

//if list is empty
return 0;
}

length++;
current = current->next;
}

return length;
}

//insert link at the first location
void insertFirst(int key, int data) {

struct node *link = (struct node*) malloc(sizeof(struct node));

if (isEmpty()) {
} else {
//point it to old first node

//point first to new first node
}
}

//delete first item
struct node * deleteFirst() {

}

//mark next to first link as first

}

//display the list
void printList() {

printf("\n[ ");

//start from the beginning

while(ptr->next != ptr) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}

printf(" ]");
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");
printList();
}
```
```
如果我们编译并运行上述程序，它将产生以下结果-
``````
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[ ]
```
```