循环链表的有序插入

循环链表是一种链式数据结构，其中最后一个节点指向第一个节点，形成一个循环。这种循环连接使得列表可以无限次地遍历。循环链表在多种应用中有用，例如缓冲区实现、表示循环数据等。

在排序的循环链表中插入新节点，需要在保持循环连接性的同时找到正确的插入点。本文将介绍如何在Python中实现循环链表的排序插入操作。排序插入算法涉及从头节点开始遍历列表，比较节点数据以找到插入新节点的合适位置。

什么是循环链表？

循环链表是链表的一种变体，其中最后一个节点指向第一个节点，形成一个循环。这使得列表可以无限次地遍历，而无需到达末尾。

例如

在这里，我们创建一个CircularLinkedList对象和三个持有数据1、2和3的Node对象。

• 第一个节点被指定为链表的头节点。
• 头节点的下一个指针指向第二个节点。
• 第二个节点的下一个指针指向第三个节点。
• 第三个节点的下一个指针指向第一个节点，形成一个循环。
• 这种循环连接允许我们无休止地遍历列表。例如：

输出

1
2
3

循环链表的主要优点是我们可以连续地遍历列表，这在环形缓冲区等情况下很有用。我们还可以避免处理列表末尾的特殊情况。

缺点是插入和删除节点需要更小心地维护循环结构。

Python 程序

输出

1 3 5 7 9 10

说明

该程序有两个类——Node和CircularLinkedList。

Node 类很简单——它只存储数据和一个next指针。

CircularLinkedList 类包含：

• init() 方法将head初始化为None。
• sortedInsert() 方法按排序顺序插入新节点。它处理3种情况：
  1. 如果列表为空，则将新节点作为头节点。
  2. 如果新节点的数据小于头节点的数据，则在新节点之前插入新节点。
  3. 否则，遍历列表以在数据较大的节点之前找到插入点。
• printList() 方法打印列表数据。

sortedInsert() 方法首先检查列表是否为空。如果是，它会将新节点设为头节点。

然后，它检查新节点是否应该成为头节点。如果新节点的数据大于当前头节点的数据，就会发生这种情况。在这种情况下，我们遍历到末尾，将末尾节点连接到新节点，并将新节点连接到原始头节点。

最后，如果新节点要插入到中间，我们遍历直到找到数据更大的节点。在新节点之前插入一个新节点。

主函数

• 创建CircularLinkedList对象。
• 通过调用sortedInsert()按排序顺序插入节点。
• 调用printList()显示内容。

这通过处理空列表、新头节点插入和中间插入等所有情况，实现了循环链表的逐步排序插入。

遍历正确地围绕循环列表进行，并在遍历时检查头节点。