循环链表：优点和缺点

⚡ 智能摘要

循环链表通过排列节点，使最后一个节点循环回到第一个节点，从而形成连续的、无 NULL 值的结构，适用于轮询调度、令牌环以及任何需要无缝遍历的工作流。

📚 定义： 每个节点都包含一个值和一个指向下一个节点的指针，最后一个节点的指向下一个节点的指针链接回第一个节点，从而形成一个闭合循环。
📌 核心优势 Opera位置： 插入、删除和遍历都是围绕更新一个或两个下一个指针，同时保持循环不变而进行的。
🛠️ C语言实现： 基于结构的节点，其插入操作由 malloc 提供支持，删除操作由 free 提供支持，涵盖了当前位置和节点后的情况。
✅ 优点： 无 NULL 解引用、无缝从结尾到开头的转换，以及将最坏情况下的查找次数减半的双重循环变体。
⚠️ 缺点： 与单链表相比，循环控制更棘手，复杂度更高，如果终止条件编写错误，则会出现无限循环。
🎯 应用环境： 轮询 CPU 调度、令牌环网络、循环缓冲区、媒体播放列表和连续显示单元。

什么是循环链表？

循环链表是一种节点序列，其排列方式使得每个节点都可以被重新访问。trac每个“节点”都是一个自引用元素，带有指向其附近一个或两个节点的指针。

下面是具有 3 个节点的循环链表的描述。

在这里，你可以看到每个节点都是重新trac能够自身循环。上面的例子就是一个循环单链表。

注意：最简单的循环链表是一个单节点链表，其下一个指针指向下一个节点。 trac它会恢复到自身状态，如下所示。

基础版 Opera循环链表中的 tions

循环链表的三种基本操作是：

插入
删除和
穿越

插入是将节点放置在循环链表中指定位置的过程。
删除是从链表中移除现有节点的过程。节点可以通过其值的出现或其位置来识别。
循环链表的遍历是指显示并重新遍历整个链表内容的过程。trac返回到源节点。

下一节解释了插入操作的工作原理，以及在循环单链表中可能出现的两种插入类型。

插入 OperaTION

首先创建一个节点，其下一个指针指向自身，如下图所示。如果没有这个种子节点，第一次插入操作就会生成列表中的第一个节点。

接下来就有两种可能：

在循环链表的当前位置插入元素。这相当于在普通单链表的开头或结尾插入元素——在循环链表中，开头和结尾是同一个点。
插入到索引节点之后。该节点应通过与其元素值对应的索引号来标识。

要在循环链表的开头或结尾插入节点（即第一个节点被添加的位置），请按照以下步骤操作：

您必须断开与现有节点的现有自链接
新节点的下一个指针将链接到现有节点。
最后一个节点的下一个指针将指向插入的节点。

注意：标记圆的起点或终点的指针可以重新分配给任何节点。遍历操作仍然会返回到同一个节点，这一点将在本文后面讨论。

（a）i-iii中的步骤如下所示：

（现有节点）

步骤1） 打破现有链接

步骤2） 创建前向链接（从新节点到现有节点）

步骤3） 创建到第一个节点的循环链接

接下来，您将尝试在节点后插入。

例如，假设起始点是包含“VALUE0”的节点，则在包含“VALUE0”的节点后插入“VALUE2”。

断开第一个节点和第二个节点之间的连接，并将带有“VALUE2”的节点放在它们之间。
第一个节点的下一个指针指向新节点，新节点的下一个指针指向以前是第二个节点的位置。
其余部分保持不变。所有节点都已重新排列。trac能够独立自主。

注意：由于链表是循环的，因此无论选择哪个位置插入节点，操作步骤都相同。闭合循环的指针与其他链表指针的行为相同。

如下所示：

（假设只有两个节点。这是一个简单的情况）

步骤1） 删除连接节点之间的内链接

步骤2） 将左侧节点连接到新节点

步骤3） 将新节点连接到右侧节点。

缺失 OperaTION

假设一个包含 3 个节点的循环链表。删除操作有两种情况：

删除当前元素
删除一个元素之后。

在开始/结尾处删除：

从最后一个节点遍历到第一个节点。
从末尾删除只需要一次遍历，从最后一个节点到第一个节点。
删除最后一个节点和第一个节点之间的链接。
将最后一个节点链接到第一个节点的下一个元素。
释放第一个节点。

（现有设置）

步骤1） 移除圆形链接

步骤2） 删除第一个和下一个之间的链接，将最后一个节点链接到第一个节点之后的节点

步骤3） 释放/解除第一个节点的资源

删除某个节点后：

遍历直到下一个节点是要删除的节点。
遍历到下一个节点，将指针放在前一个节点上。
使用下一个指针将前一个节点连接到当前节点之后的节点。
释放当前（已解除链接的）节点。

步骤1） 假设我们需要删除一个名为“VALUE1”的节点。

步骤2） 移除前一个节点与当前节点之间的链接，然后将前一个节点直接连接到当前节点的下一个指针所指向的节点（VALUE1 之后的节点）。

步骤3） 释放或者取消分配当前节点。

循环链表的遍历

要从最后一个指针遍历循环链表，首先检查最后一个指针是否为 NULL。如果不为 NULL，则检查链表是否只有一个元素。否则，使用临时指针遍历链表，直到再次到达最后一个指针为止，如下面的动画所示。

循环链表的优点

循环链表的一些优点是：

代码中无需分配 NULL。循环列表永远不会指向 NULL 指针，除非完全释放。
循环链表有利于执行链表末尾操作，因为链表的开头和结尾重合。 Algorithms 例如，轮询调度可以干净利落地处理排队的进程，而不会遇到悬空指针或空指针。
循环链表仍然支持单链表的所有常规操作。双向链表甚至可以省去遍历整个列表来定位元素的需要——在最坏的情况下，目标元素位于起始指针的对面，因此最多只需要遍历列表的一半。

循环链表的缺点

使用循环链表的缺点如下：

循环列表比循环列表更复杂。单链表.
Rev反转循环链表比反转单链表或双链表更复杂。
如果循环终止处理不当，遍历代码可能会进入无限循环。
找到列表的末尾并编写正确的循环控制条件比较困难。
从实现角度来看，在列表开头插入元素需要遍历整个列表才能到达最后一个节点。

单链表作为循环链表

鼓励您阅读并实现以下 C 代码。它演示了与循环单链表相关的指针运算。

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

代码说明：

前两行代码是必须包含的头文件。
下一节定义了每个自引用节点的结构。它包含一个值和一个与结构类型相同的指针。
每个结构实例都链接到相同类型的其他结构对象。
有不同的函数原型：
1. 向空链表添加元素
2. 插入 目前指向 循环链表的位置。
3. 在特定索引链接列表中的值。
4. 删除/移除特定索引链接列表中的值。
5. 删除循环链表当前指向的位置
最后一个函数在链表的任何状态下通过循环遍历打印每个元素。

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

代码说明：

对于 addToEmpty 代码，使用 malloc() 函数分配一个空节点。
将传入的数据放入临时节点。
将临时节点分配给最后一个节点，并将其下一个指针设置为自身，以便该单个节点指向自身。
将最后一个指针返回到 main() / 应用程序上下文。

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
&#8230;

代码解释

如果列表为空，则将控制权交给 addToEmpty() 并返回控制权。
创建一个临时节点，放置在当前节点之后。
按照上图所示连接指针。
返回与上一个函数中使用的模式匹配的最后一个指针。

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

代码说明：

如果列表为空，则忽略搜索键，将当前项作为列表中的唯一节点添加进去，并返回控制权。
在 do-while 循环的每次迭代中，前一个指针保存着上次遍历的结果。
只有在这种情况下，才会进行下一个遍历步骤。
当找到目标数据或临时指针再次到达最后一个指针位置时，do-while 循环终止。以下代码块决定如何处理找到的数据项。

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

代码说明：

如果已遍历整个列表但未找到该项目，则显示“未找到元素”消息并将控制权返回给调用者。
如果找到目标节点，则分配一个新节点来插入该值。
链接将前一个节点链接到新节点，并将新节点的下一个指针链接到 temp（遍历变量）。
这会将新元素放置在循环链表中目标节点之后。然后控制权返回给调用者。

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

代码解释

要删除最后一个（当前）节点，首先要检查列表是否为空。如果列表为空，则无法删除任何元素。
临时变量向前移动一个链路。
将最后一个指针链接到第一个节点之后的节点。
释放临时指针以释放未链接的节点。

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

代码解释

与之前的删除函数一样，首先检查列表是否为空。如果为空，则无法删除任何元素。
二指针被分配特定位置来定位要删除的元素。
指针依次前进（之前的轨迹温度）。
遍历过程持续进行，直到找到目标元素或下一个指针再次到达最后一个节点为止。

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

节目说明

如果遍历整个链表后仍未找到目标元素，则会显示“未找到元素”消息。
否则，该元素将在步骤 3 和 4 中被取消链接并释放。
前一个指针指向 temp 的下一个指针所指向的节点（即被删除节点之后的节点）。
然后释放临时指针。

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

代码解释

如果节点数为零，则无法进行窥视遍历——用户必须先分配或插入一个节点。
如果只有一个节点，则无需遍历——直接打印节点的内容，while 循环不会执行。
如果存在多个节点，则临时打印每个元素，直到最后一个元素。
当到达最后一个元素时，循环终止，函数将控制权返回给 main()。

循环链表的应用

实现系统进程的循环调度和高速图形的循环调度。
计算机网络中的令牌环调度。
用于需要连续遍历数据的显示单元，例如数字商店看板。

常见问题

GitHub Copilot 和 ChatGPT 等 AI 助手会生成节点结构、基于 malloc 的插入器以及循环安全的遍历循环。开发人员会在将生成的代码合并到生产数据结构之前，检查其终止条件和内存清理是否正确。

机器学习管道使用基于循环链表的循环缓冲区来保存滚动的流数据窗口、用于强化学习代理的回放缓冲区样本，以及用于生产者-消费者工作者向训练批次提供数据的循环队列。

单链表以空指针结尾，而循环链表的最后一个节点指向第一个节点。这种闭环结构避免了在链表尾部进行空指针检查，并支持在单个循环中实现连续的、循环遍历。

循环双向链表每个节点有两个指针——next 和 prev——并且两端可以相互循环。这种结构支持双向遍历，最坏情况下查找次数最多为链表长度的一半。

弗洛伊德龟兔赛跑算法使用两个速度不同的指针。如果它们相遇，则说明存在循环。该算法的时间复杂度为 O(n)，额外空间复杂度为 O(1)，是循环检测的标准面试题解决方案。

在循环链表的当前位置进行插入或删除操作的时间复杂度为 O(1)。 Opera针对特定值或索引的操作的时间复杂度为 O(n)，因为必须遍历列表才能找到目标节点。

Operating 系统调度器使用它们进行轮询 CPU 调度，令牌环网络在站点之间传递控制权，媒体播放器循环播放播放列表，嵌入式系统使用由循环列表支持的循环缓冲区来处理传感器流。

常见错误包括插入或删除后忘记更新两个端点指针、缺少终止条件以及……ping 永远释放一个节点而不重新连接其邻居，并在丢弃列表时泄漏内存。

循环链表：优点和缺点

什么是循环链表？

基础版 Opera循环链表中的 tions

插入 OperaTION

缺失 OperaTION

循环链表的遍历

循环链表的优点

循环链表的缺点

单链表作为循环链表

循环链表的应用

常见问题

总结一下这篇文章：

注册简报

什么是循环链表？

基础版 Opera循环链表中的 tions

插入 OperaTION

缺失 OperaTION

相关文章

循环链表的遍历

循环链表的优点

循环链表的缺点

单链表作为循环链表

循环链表的应用

常见问题

总结一下这篇文章：

注册简报