Data Structures Algorithms 简明教程

Circular Linked List Data Structure

What is Circular Linked List?

Circular Linked List 是链表的一个变体，其中第一个元素指向最后一个元素，而最后一个元素指向第一个元素。单向链表和双向链表都可以变成循环链表。

Singly Linked List as Circular

在单向链表中，最后一个节点的下一个指针指向第一个节点。

singly linked list as circular

Doubly Linked List as Circular

在双向链表中，最后一个节点的下一个指针指向第一个节点，而第一个节点的前一个指针指向最后一个节点，使两者都成为循环。

doubly linked list as circular

根据上述说明，以下是要考虑的重要事项。

  1. 单链表和双向链表的最后链接的下一个指针在两种情况下都指向列表的第一个链接。

  2. 在双向链表的情况下，第一个链接的前一个指针指向列表的最后一个指针。

Basic Operations in Circular Linked List

循环列表支持以下重要操作。

  1. insert − 在列表开头插入一个元素。

  2. delete − 从列表开头删除一个元素。

  3. display − 显示列表。

Circular Linked List - Insertion Operation

循环链表的插入操作只在列表开头插入元素。这不同于通常的单链表和双向链表，因为此列表中没有特定的开始和结束点。插入在列表的开头或特定节点（或给定位置）之后。

Algorithm

1. START
2. Check if the list is empty
3. If the list is empty, add the node and point the head
   to this node
4. If the list is not empty, link the existing head as
   the next node to the new node.
5. Make the new node as the new head.
6. END

Example

以下是该操作在各种编程语言中的实现 −

Circular Linked List - Deletion Operation

循环链表的删除操作可以从列表中删除特定节点。这种类型的列表中的删除操作可以在开始处或给定位置或结束处执行。

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

Example

以下是该操作在各种编程语言中的实现 −

Circular Linked List - Displaying the List

显示列表操作访问列表中的每个节点，并将它们全部打印在输出中。

Algorithm

1. START
2. Walk through all the nodes of the list and print them
3. END

Example

以下是该操作在各种编程语言中的实现 −

Circular Linked List - Complete Implementation

以下是各种编程语言中对循环链表的完整实现 −