Python 数据结构入门 - 循环链表（Circular List）

循环链表是什么

循环链表可以是单链表也可以是双链表。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环链表的应用

• 共享资源池的资源申请
  
• 循环调度算法

动手试一试

在我们的例子中，决定采用循环单链表。所以链表结点被定义如下。

除了多出一条尾部指向头部的指针，向循环链表中插入结点和单链表类似。循环链表定义如下。

删除结点时，当要删除结点在链表中间位置时，和单链表类似。当要删除结点在链表尾部时，同样多出一条新尾部指向头部的指针。代码重新定义如下

删除函数测试代码。对于循环链表的删除操作来说，有很多的边缘情况需要考虑。但是它的时间复杂度仍然是 O(n) 。

总的来说，循环链表和单链表不同的地方只是在头部和尾部之间添加了一条指针。这些额外的工作都可以在常数时间内完成，因此时间复杂度都是相同的。

时间复杂度

• 添加：O(1)
  
• 删除(给定要删除数据)：O(n)
• 计算大小：O(1)
• 查找：O(n)
• 清空：O(1)

参考链接：

• https://github.com/saiyangqi/Python-Data-Structures-and-Algorithms/blob/master/3-CircularList.ipynb