循环链表：优点和缺点

由： 陈莎拉 陈莎拉
Hours 更新

什么是循环链表？

循环链表是一系列节点，每个节点都可以回溯到自身。这里的“节点”是一个自引用元素，带有指向其附近一个或两个节点的指针。

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

循环链表

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

注意：最简单的循环链表是一个只能追溯到自身的节点，如图所示

循环链表

基础版 Opera循环链接列表中

循环链表的基本操作包括：

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

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

插入 OperaTION

首先，您需要创建一个指向自身的节点，如下图所示。如果没有此节点，插入将创建第一个节点。

插入 OperaTION

接下来就有两种可能：

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

对于在循环链表的开头/结尾处插入，即在第一个节点被添加的位置，

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

注意：作为令牌主节点或圆的起点/终点的指针可以改变。它仍将在遍历中返回到相同的节点，前面将对此进行讨论。

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

插入 OperaTION

（现有节点）

插入 OperaTION

步骤1） 打破现有链接

插入 OperaTION

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

插入 OperaTION

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

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

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

  • 您必须打破第一个和第二个节点之间的线，并将带有“VALUE2”的节点放在它们之间。
  • 第一个节点的下一个指针必须链接到这个节点，而这个节点的下一个指针必须链接到更早的第二个节点。
  • 其余安排保持不变。所有节点均可追溯到自身。

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

如下所示：

插入 OperaTION

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

插入 OperaTION

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

插入 OperaTION

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

插入 OperaTION

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

相关文章

缺失 OperaTION

假设有一个 3 节点循环链表。删除的情况如下：

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

在开始/结尾处删除：

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

缺失 OperaTION

（现有设置）

缺失 OperaTION

步骤1）删除循环链接

缺失 OperaTION

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

缺失 OperaTION

步骤3） 释放/解除分配第一个节点

删除某个节点后：

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

缺失 OperaTION

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

缺失 OperaTION

步骤2） 删除前一个节点与当前节点之间的链接。将其前一个节点与当前节点（用VALUE1）指向的下一个节点链接起来。

缺失 OperaTION

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

循环链表的遍历

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

循环链表的遍历

循环链表的优点

循环链表的一些优点是：

  1. 代码中无需分配 NULL。循环列表永远不会指向 NULL 指针，除非完全释放。
  2. 循环链表有利于结束操作，因为开始和结束是重合的。 Algorithms 例如循环调度可以巧妙地消除以循环方式排队的进程，而不会遇到悬空指针或 NULL 引用指针。
  3. 循环链表也执行单链表的所有常规功能。事实上，循环 双向链表 下面讨论的甚至可以消除全长遍历来定位元素的需要。该元素最多只是与开头完全相反，仅完成链表的一半。

循环链表的缺点

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

  1. 循环列表相比于 单链表.
  2. Rev与单链表或双链表相比，循环链表更为复杂。
  3. 如果处理不当，代码可能会陷入无限循环。
  4. 更难找到列表的末尾和循环控制。
  5. 在开始处插入，我们必须遍历整个列表才能找到最后一个节点。（实施角度）

单链表作为循环链表

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

#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. 有不同的函数原型：
    1. 向空链表添加元素
    2. 插入 目前指向 循环链表的位置。
    3. 在特定 索引 链接列表中的值。
    4. 删除/移除特定 索引 链接列表中的值。
    5. 删除循环链表当前指向的位置
  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)

单链表

代码说明：

  1. 对于 addEmpty 代码，使用 malloc 函数分配一个空节点。
  2. 对于此节点，将数据放置到临时变量中。
  3. 将唯一变量分配并链接到临时变量
  4. 将最后一个元素返回给 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;
…

单链表

代码解释

  1. 如果没有要插入的元素，那么您应该确保将其添加到空列表并返回控制。
  2. 创建一个临时元素放置在当前元素之后。
  3. 按照图示链接指针。
  4. 像前一个函数一样返回最后一个指针。
...
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");
...

单链表

代码说明：

  1. 如果列表中没有元素，则忽略数据，将当前项添加为列表中的最后一项并返回控制权
  2. 对于 do-while 循环中的每次迭代，确保有一个前一个指针保存最后遍历的结果。
  3. 只有这样才能进行下一次遍历。
  4. 如果找到了数据，或者 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)
...

单链表

代码说明：

  1. 如果遍历了整个列表但仍未找到该项目，则显示“未找到项目”消息，然后将控制权返回给调用者。
  2. 如果找到一个节点，并且/或者该节点还不是最后一个节点，则创建一个新节点。
  3. 链接 将前一个节点与新节点关联起来。将当前节点与 temp（遍历变量）关联起来。
  4. 这确保元素被放置在循环链表中的特定节点之后。返回给调用者。
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)

单链表

代码解释

  1. 要仅删除最后一个（当前）节点，请检查此列表是否为空。如果是空的，则不能删除任何元素。
  2. temp 变量仅向前遍历一个链接。
  3. 将最后一个指针链接到第一个指针之后的指针。
  4. 释放临时指针。它将释放未链接的最后一个指针。
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");
...

单链表

代码解释

  1. 与上一个删除函数一样，检查是否没有元素。如果为真，则不能删除任何元素。
  2. Pointers 被分配特定位置来定位要删除的元素。
  3. 指针一个接一个地前进。（prev behind temp）
  4. 该过程持续进行，直到找到一个元素，或者下一个元素回到最后一个指针。
    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;

单链表

节目说明

  1. 如果遍历整个链表后仍找到该元素，则会显示一条错误消息，指出未找到该项目。
  2. 否则，元素将在步骤 3 和 4 中解除链接并释放。
  3. Previous 指针链接到要删除的元素 (temp) 指向的“next”地址。
  4. 因此，临时指针被释放并释放。
...
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;
    }
}

单链表

代码解释

  1. 如果需要的节点为零，则无法进行查看或遍历。用户需要分配或插入一个节点。
  2. 如果只有一个节点，则不需要遍历，打印该节点的内容即可，while循环不执行。
  3. 如果有多个节点，则临时文件会打印所有项目直到最后一个元素。
  4. 一旦到达最后一个元素，循环就会终止，并且函数将返回对主函数的调用。

循环链表的应用

  • 实现系统进程的循环调度和高速图形的循环调度。
  • 计算机网络中的令牌环调度。
  • 它用于需要连续遍历数据的显示单元（如车间面板）。

每日Guru99新闻简报

通过立即获取最新、最重要的人工智能新闻报道来开始您的一天。