Data Structures Algorithms 简明教程
Circular Linked List Data Structure
What is Circular Linked List?
Circular Linked List 是链表的一个变体，其中第一个元素指向最后一个元素，而最后一个元素指向第一个元素。单向链表和双向链表都可以变成循环链表。
Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.
Singly Linked List as Circular
在单向链表中，最后一个节点的下一个指针指向第一个节点。
In singly linked list, the next pointer of the last node points to the first node.
Doubly Linked List as Circular
在双向链表中，最后一个节点的下一个指针指向第一个节点，而第一个节点的前一个指针指向最后一个节点，使两者都成为循环。
In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.
根据上述说明，以下是要考虑的重要事项。
As per the above illustration, following are the important points to be considered.
-
The last link’s next points to the first link of the list in both cases of singly as well as doubly linked list.
-
The first link’s previous points to the last of the list in case of doubly linked list.
Basic Operations in Circular Linked List
循环列表支持以下重要操作。
Following are the important operations supported by a circular list.
-
insert − Inserts an element at the start of the list.
-
delete − Deletes an element from the start of the list.
-
display − Displays the list.
Circular Linked List - Insertion Operation
循环链表的插入操作只在列表开头插入元素。这不同于通常的单链表和双向链表，因为此列表中没有特定的开始和结束点。插入在列表的开头或特定节点（或给定位置）之后。
The insertion operation of a circular linked list only inserts the element at the start of the list. This differs from the usual singly and doubly linked lists as there is no particular starting and ending points in this list. The insertion is done either at the start or after a particular node (or a given position) in the list.
Circular Linked List - Deletion Operation
循环链表的删除操作可以从列表中删除特定节点。这种类型的列表中的删除操作可以在开始处或给定位置或结束处执行。
The Deletion operation in a Circular linked list removes a certain node from the list. The deletion operation in this type of lists can be done at the beginning, or a given position, or at the ending.
Algorithm
1. START
2. If the list is empty, then the program is returned.
3. If the list is not empty, we traverse the list using a
current pointer that is set to the head pointer and create
another pointer previous that points to the last node.
4. Suppose the list has only one node, the node is deleted
by setting the head pointer to NULL.
5. If the list has more than one node and the first node is to
be deleted, the head is set to the next node and the previous
is linked to the new head.
6. If the node to be deleted is the last node, link the preceding
node of the last node to head node.
7. If the node is neither first nor last, remove the node by
linking its preceding node to its succeeding node.
8. END