循环链表导论和应用

在本文中，我们将概述链表。它们如何工作，它们的属性以及可以使用循环链表作为底层数据结构的重要应用示例。我们还将展示一些 Python 代码示例，以演示如何实现循环链表。

什么是循环链表？

链表是计算机科学和编程中使用的数据结构之一。它们提供了一种存储和组织需要频繁插入和删除操作的数据的方法。

循环链表是链表结构的一个变体，其中最后一个节点连接回第一个节点，从而形成一个排列。与链表的这种区别赋予了链表独特的特性和优势，适用于特定用例。

理解链表对任何程序员来说都很有价值，因为它们在操作系统、数据库和网络中很常见。它们的循环性质与环形缓冲区、循环媒体播放和周期性事件等现实场景非常吻合。在本文结束时，您将对循环链表的基础知识有扎实的掌握，并能够评估何时它们可能是比数组、普通链表或其他数据结构更适合应用程序的选择。

让我们详细了解循环链表。

循环链表是链表的一个变体，其中最后一个节点指向第一个节点，形成一个连续的圆。这与以 null 指针标记结尾的常规单向或双向链表不同。

循环链表的主要优点是它没有需要遍历的末端。这允许无限的前向和后向循环遍历。

循环链表的一些关键属性

• 第一个节点指向第二个节点，第二个节点指向第三个节点，依此类推，直到最后一个节点，最后一个节点指向第一个节点。这形成了一个非结束的循环。
• 结尾没有 null 引用。循环无限继续。
• 它们可以是单向链表（每个节点有一个指针）或双向链表（每个节点有两个指针 - 指向前一个和后一个）
• 循环列表没有开始或结束节点。每个节点都可以被视为头节点和尾节点。
• 适用于实现固定大小的缓冲区和队列。在循环遍历后，新数据将覆盖最旧的数据。
• 它通常用于表示重复事件或具有固定大小但没有真正开始或结束的集合，例如一副扑克牌。
• 算法需要包含对循环连接的检查，以防止在遍历期间出现无限循环。当前节点的下一个指向头部表示结束。
• 常数 O(1) 时间的插入和删除，因为只需重新分配指针，无需移动元素。访问是 O(n)。
• 循环双向链表允许有效地双向遍历列表。

总之，循环链表由于其循环性质，提供高效的原地操作和无限遍历。它们对于缓冲区、历史记录、调度和其他需要固定大小数据结构的领域很有用。

循环链表的一些优点

高效的内存使用

• 循环连接允许链表重用相同的节点，在固定空间中存储数据。无需动态调整大小。这使得循环列表对于固定大小的缓冲区和队列很有用。

无限遍历

• 循环性质允许通过跟踪指针在列表中向前和向后无限遍历。适用于需要重复访问的数据，例如游戏回合或音频播放列表。

常数时间插入/删除

• 添加或删除节点只需重新分配几个指针，而无需向下移动元素或查找插入点。

预分配内存

• 循环列表允许预先分配节点，因为大小是固定的。这避免了动态请求更多内存的运行时开销。

比数组访问更快

• 通过指针跟踪可以快速检索下一个或上一个元素。数组需要计算索引偏移量。

隐藏的末端

• 循环结构隐藏了实际的开始和结束位置。算法可以将其中的任何节点视为第一个元素。

历史跟踪

• 循环列表提供了一种有效的方法来存储事件或状态的历史记录在一个固定缓冲区中，该缓冲区在达到容量后将被覆盖。

循环/重复处理

• 适用于模拟循环过程，例如轮循调度。节点可以连续遍历，没有明显的结束。

有限的资源使用

• 限制列表大小会限制内存使用。遍历完一圈后，新数据会自动覆盖旧数据。

简化的代码

• 循环列表上的算法更简单。无需特殊处理越界错误或端点。

主要优点是高效的内存使用、快速的插入和删除、预分配、无限遍历、隐藏的末端、历史跟踪和简化的循环算法。当数据表现出循环或重复模式时，循环列表效果最佳。

循环链表的应用

环形缓冲区

环形缓冲区是固定大小的缓冲区，它们以先进先出（FIFO）的顺序工作，在达到容量时用新数据覆盖旧数据。循环链表提供了一种高效的底层数据结构来实现环形缓冲区。添加元素时，链表会增长直到达到容量。然后，附加下一个元素会将列表循环回头部，覆盖最旧的条目。这种循环覆盖行为使循环列表成为环形缓冲区的理想选择。恒定的插入和删除时间意味着添加或删除元素速度很快，即使在容量已满时也是如此。循环结构还允许预先分配缓冲区大小而不会浪费内存。循环连接和恒定的时间操作使得循环链表非常适合实现用于内存缓存、网络数据缓冲区、文件系统缓冲区等的环形缓冲区。

浏览器历史记录

Web 浏览器使用循环链表按时间顺序存储用户访问过的页面，从而实现后退/前进导航按钮。随着访问的页面越来越多，旧页面会在列表中向后移动，直到达到容量后以 FIFO 的方式被覆盖。循环列表结构保证页面保持顺序，但最终会在列表循环回头部后被覆盖。双向链表的性质还允许高效的双向遍历历史记录。与数组相比，循环列表更适合浏览器历史记录，因为插入速度更快。总的来说，循环链表非常适合存储浏览器历史记录，因为它们的循环结构以 FIFO 顺序维护固定大小的有序页面缓冲区。

循环调度

在轮循调度中，进程以循环轮换的方式分配 CPU 时间片。这种均等的 CPU 共享可以通过进程的循环链表有效地建模。当调度程序遍历列表时，每个进程都有执行的机会。循环结构确保没有终点，进程会以公平的循环顺序被重新访问。插入和删除进程也很容易和快速。无限遍历和常数时间插入/删除使得循环链表非常适合建模操作系统中使用的轮循调度系统。

媒体播放列表

媒体应用程序使用循环链表来存储和播放音频/视频文件，形成一个连续循环的播放列表。循环结构在播放完最后一个元素后可以无缝地循环回起始媒体。双向链表还可以实现向后搜索。由于只需更新指针，因此播放列表的添加速度很快且内存效率高。总的来说，循环循环和高效的插入使得循环链表能够有效地存储和播放循环媒体播放列表。

回合制游戏

玩家按顺序轮流进行的游戏可以使用循环链表来模拟回合顺序，每个回合后进入下一位玩家。循环结构自然地模拟了循环回合的概念，没有明显的开始或结束点。插入和删除玩家也通过指针更新速度很快。由于插入/删除的灵活性和速度，在游戏中通常优先使用循环链表而不是数组。无限遍历和固定大小的可能性也很好地适用于重复的回合制游戏。

操作系统进程调度

操作系统可以通过将进程保留在循环链表中来实现轮循调度。调度程序遍历此列表，为每个进程分配一个时间片，然后移至下一个。这会在循环中连续进行。循环列表提供了一种有效地模拟轮循循环序列的方法。进程的添加和删除速度也很快。总的来说，循环链表允许简单地模拟操作系统中的重复公平调度。

纸牌游戏

可以通过将一副牌建模为循环链表来实现纸牌游戏。可以通过随机指向牌堆中任何位置的头部来模拟洗牌。发牌只是从任何位置删除元素。洗牌和发牌后，循环列表可保持牌堆的连续性。双向链表允许反向发牌顺序。总的来说，循环列表很好地封装了纸牌牌堆中的循环排序。

矩阵遍历

可以使用循环链表来存储路径序列，从而以螺旋形或同心矩形等模式遍历矩阵。循环列表自然地模拟了循环形状，无需在端点进行特殊逻辑。复杂的嵌套循环被避免了。添加或删除单元格的速度也很快。因此，循环链表简化了矩阵遍历算法的实现。

循环缓冲区

可以通过循环链表实现的固定大小的循环缓冲区来收集来自设备的输入数据。添加新数据，在达到容量后以 FIFO 顺序覆盖最旧的数据。固有的循环行为使得循环列表成为这些用于设备驱动程序、数据采集系统、队列等的循环缓冲区的理想选择。

DNA 分析

质粒等环状 DNA 结构没有真正的起始或结束点。可以通过将序列视为循环链表来分析它们，以识别基因、密码子、基序等。循环连接通过消除特殊的边缘情况来简化算法。插入和删除对于突变分析也很快。因此，循环列表可以有效地模拟环状 DNA。

Python 实现循环链表

输出

说明

1. Node 类定义了每个节点对象，包含数据和 next 指针。
2. CircularSinglyLinkedList 类包含一个指向第一个节点的 head 指针。
3. prepend(data) 在头部插入新节点
   • 创建一个包含给定数据的新节点
   • 将其 next 指向当前 head
   • 找到尾节点（在 head 之前）并将尾节点指向新节点
   • 将 head 更新为新节点
4. append(data) 在尾部插入
   • 创建一个包含给定数据的新节点
   • 使用循环找到尾节点
   • 将尾节点的 next 指向新节点
   • 将新节点的 next 指向 head
5. print_list() 打印每个节点中的数据
   • 从 head 开始
   • 打印数据并遍历到下一个
   • 当 next 指向 head 时中断
6. remove(key) 删除具有给定键的节点
   • head 节点时的特殊情况
   • 否则，使用循环找到 prev 和 node
   • 将 prev 指向 node 的 next
7. len() 返回长度
   • 初始化计数器
   • 遍历列表直到回到 head
   • 返回计数
8. split_list() 在中点分割循环列表
   • 计算长度
   • 使用 prev, cur 指针遍历前 mid 个节点
   • 在中点处中断循环
   • 将 prev 的 next 指向 head（打破循环）
   • 创建一个包含剩余节点的新循环列表
   • 打印两个列表

关键方面是

• 正确维护循环指针连接
• 在 head 之前找到尾节点
• 处理 head 节点的特殊情况
• 打破循环连接以分割列表

使用 prev cur 指针进行遍历和重新链接