循环链表：优点和缺点

什么是循环链表？

循环链表是一种节点序列，其排列方式使得每个节点都可以追溯到自身。这里的“节点”是一个自引用的元素，其中包含指向其紧邻的一个或两个节点的指针。

下面是包含 3 个节点的循环链表的示意图。

在这里，您可以看到每个节点都可以追溯到自身。上面显示的例子是一个循环单链表。

注意：最简单的循环链表是仅指向自身的节点，如下所示

循环链表中的基本操作

循环链表上的基本操作是

插入
删除，以及
遍历

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

在下一节中，您将了解节点插入以及循环单链表中可能出现的插入类型。

插入操作

最初，您需要创建一个指向自身的节点，如图所示。没有这个节点，插入会创建第一个节点。

接下来，有两种可能性

在循环链表的当前位置插入。这对应于在常规单链表的开头或结尾插入。在循环链表中，开头和结尾是相同的。
在索引节点之后插入。节点应由对应于其元素值的索引号标识。

要在循环链表的开头/结尾插入，也就是在添加第一个节点的位置，

您需要打破与现有节点的现有自链接
新节点的下一个指针将链接到现有节点。
最后一个节点的下一个指针将指向插入的节点。

注意：作为令牌主控或圆的开头/结尾的指针可以更改。在遍历时，它仍然会返回到同一个节点，稍后将进行讨论。

下面显示了 (a) i-iii 中的步骤

(现有节点)

第一步) 断开现有链接

第二步) 创建前向链接（从新节点到现有节点）

第三步) 创建到第一个节点的循环链接

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

例如，让我们在值为“VALUE0”的节点之后插入“VALUE2”。假设起始点是值为“VALUE0”的节点。

您需要断开第一个和第二个节点之间的链接，并将值为“VALUE2”的节点放在中间。
第一个节点的下一个指针必须链接到此节点，并且此节点的下一个指针必须链接到之前的第二个节点。
其余的排列保持不变。所有节点都可以追溯到自身。

注意：由于存在循环排列，插入节点涉及所有节点的相同过程。完成循环的指针就像任何其他节点一样完成循环。

下面展示了这一点

(假设只有两个节点。这是一个平凡的案例)

第一步) 移除连接节点之间的内部链接

第二步) 将左侧节点连接到新节点

第三步) 将新节点连接到右侧节点。

删除操作

假设有一个 3 节点循环链表。删除的案例如下

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

删除开头/结尾

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

(现有设置)

第一步) 移除循环链接

第二步) 移除第一个和下一个之间的链接，将最后一个节点链接到第一个后面的节点

第三步) 释放/解除分配第一个节点

删除节点之后

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

第一步) 假设我们需要删除值为“VALUE1”的节点。

第二步) 移除前一个节点和当前节点之间的链接。将其前一个节点与其当前节点（值为“VALUE1”）指向的下一个节点链接起来。

第三步) 释放或解除分配当前节点。

循环链表的遍历

要遍历循环链表，从最后一个指针开始，检查最后一个指针本身是否为 NULL。如果此条件不成立，请检查是否只有一个元素。否则，使用临时指针进行遍历，直到再次到达最后一个指针，或者根据需要进行多次遍历，如下面的 GIF 所示。

循环链表的优点

循环链表的一些优点是

代码中无需分配 NULL。循环列表除非完全解除分配，否则永远不会指向 NULL 指针。
循环链表在末尾操作方面具有优势，因为开头和结尾是重合的。诸如轮循调度之类的算法可以整洁地消除以循环方式排队的进程，而不会遇到悬空或 NULL 引用指针。
循环链表也执行单链表的所有常规功能。事实上，下面讨论的循环双向链表甚至可以消除完全遍历以查找元素的需要。该元素最多只会与起点完全相对，只完成链表的一半。

循环链表的缺点

使用循环链表的缺点如下

与单链表相比，循环链表更复杂。
与单链表或双向链表相比，反转循环链表更复杂。
如果处理不当，代码可能会陷入无限循环。
难以找到列表的末尾和控制循环。
插入到开头，我们必须遍历整个列表才能找到最后一个节点。（从实现角度）

单链表作为循环链表

鼓励您尝试阅读并实现下面的代码。它展示了与循环链表相关的指针算术。

#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)

代码解释

对于 addEmpty 代码，使用 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;
…

代码解释

如果没有要插入的元素，则应确保添加到空列表并返回控制。
创建一个临时元素放在当前元素之后。
按所示链接指针。
与上一个函数一样，返回最后一个指针。

...
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 循环中的每次迭代，确保有一个前一个指针保存上一次遍历的结果。
只有这样才能进行下一次遍历。
如果找到数据，或者 temp 回到最后一个指针，则 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");
...

代码解释

与上一个删除函数一样，检查是否没有元素。如果为真，则无法删除任何元素。
分配特定的位置给指针以定位要删除的元素。
指针一个接一个地前进。（prev 在 temp 后面）
过程继续，直到找到元素，或者下一个元素追溯到最后一个指针。

    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）指向的“下一个”地址。
因此，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 循环不执行。
如果有多于一个节点，则 temp 打印所有项直到最后一个元素。
一旦到达最后一个元素，循环就会终止，并且函数将调用返回到 main 函数。

循环链表的应用

在系统进程中实现轮循调度和在高速图形中实现循环调度。
计算机网络中的令牌环调度。
它用于显示单元，如需要数据连续遍历的店面广告牌。

什么是循环链表？

循环链表中的基本操作

插入操作

相关文章

删除操作

循环链表的遍历

循环链表的优点

循环链表的缺点

单链表作为循环链表

循环链表的应用

订阅新闻通讯