循环链表

原文：https://www.studytonight.com/data-structures/circular-linked-list

循环链表是稍微复杂一点的链接数据结构。在循环链表中，我们可以在链表的任何地方插入元素，而在数组中，我们不能在链表的任何地方插入元素，因为它在连续的内存中。在循环链表中，前一个元素存储下一个元素的地址，最后一个元素存储起始元素的地址。这些元素以环形方式相互指向，形成一条环形链。循环链表具有动态大小，这意味着当需要时可以分配内存。

循环链表的应用

• 使用循环链表的真实应用程序是我们的个人计算机，其中运行着多个应用程序。所有正在运行的应用程序都保存在一个循环链表中，操作系统给所有应用程序一个固定的运行时间。操作系统继续迭代链表，直到所有应用程序都完成。
• 另一个例子可以是多人游戏。所有玩家都被保存在一个循环链表中，当玩家的机会结束时，指针继续向前移动。
• 循环链表也可以用来创建循环队列。在队列中，我们必须始终在内存中保留两个指针，前端和后端，而在循环链表中，只需要一个指针。

实现循环链表

实现循环链表非常容易，几乎与线性链表实现相似，唯一的区别是，在循环链表中，最后一个节点将使其下一个指向链表的头。在线性链表中，最后一个节点只是在它的下一个指针中保留空值。

这将是我们的节点类，正如我们在本课中已经学习过的，它将用于形成列表。

 class **Node** {
  public:
  int data;
  *//pointer to the next node*
  node* next;

  **node**() {
    data = 0;
    next = NULL;
  }

  **node**(int x) {
    data = x;
    next = NULL;
  }
}

循环链表

循环链表类将与我们上一课学习的链表类几乎相同，只是在类方法的实现上有一些不同。

 class **CircularLinkedList** {
  public:
  node *head;
  *//declaring the functions*

  *//function to add Node at front*
  int addAtFront(node *n);
  *//function to check whether Linked list is empty*
  int isEmpty();
  *//function to add Node at the End of list*
  int addAtEnd(node *n);
  *//function to search a value*
  node* search(int k);
  *//function to delete any Node*
  node* deleteNode(int x);

  **CircularLinkedList**() {
    head = NULL;
  }
}

在开头插入

在开头插入节点的步骤:

1. 第一个节点是任何链表的头部。
2. 当一个新的链表被实例化时，它只有头，为空。
3. 否则，头部持有指向列表第一个节点的指针。
4. 当我们想在前面添加任何节点时，我们必须使头部指向它。
5. 新添加节点的下一个指针必须指向前一个头，无论它是空的(在新列表的情况下)还是指向列表第一个节点的指针。
6. 前一个头节点现在是链表的第二个节点，因为新节点被添加在前面。

 int CircularLinkedList :: **addAtFront**(node *n) {
  int i = 0;
  */* If the list is empty */*
  if(head == NULL) {
    n**->**next = head;
    *//making the new Node as Head*
    head = n;
    i++;
  }
  else {
    n->next = head;
    *//get the Last Node and make its next point to new Node*
    Node* last = **getLastNode**();
    last->next = n;
    *//also make the head point to the new first Node*
    head = n;
    i++;
  }
  *//returning the position where Node is added*
  return i;
}

结尾插入

在末尾插入节点的步骤:

1. 如果链表是空的，那么我们只需添加新的节点作为链表的头。
2. 如果链表不是空的，那么我们找到最后一个节点，并使它紧挨着新节点，并使新添加节点的下一个指向链表的头部。

 int CircularLinkedList :: **addAtEnd**(node *n) {
  *//If list is empty*
  if(head == NULL) {
    *//making the new Node as Head*
    head = n;
    *//making the next pointer of the new Node as Null*
    n**->**next = NULL;
  }
  else {
    *//getting the last node*
    node *last = **getLastNode**();
    last**->**next = n;
    *//making the next pointer of new node point to head*
    n**->**next = head;
  } 
}

在列表中搜索元素

在搜索中，我们不需要做太多，我们只需要像获取最后一个节点一样遍历，在这种情况下，我们还将比较节点的数据。如果我们得到具有相同数据的节点，我们将返回它，否则我们将使我们的指针指向下一个节点，以此类推。

 node* CircularLinkedList :: **search**(int x) {
  node *ptr = head;
  while(ptr != NULL && ptr**->**data != x) {
    *//until we reach the end or we find a Node with data x, we keep moving*
    ptr = ptr**->**next;
  }
  return ptr;
}

从列表中删除节点

删除一个节点可以有很多种方式，比如我们先用数据搜索想要删除的节点，然后再删除。在我们的方法中，我们将定义一种方法，该方法将以要删除的数据作为参数，将使用搜索方法来定位它，然后将节点从列表中移除。

要从列表中删除任何节点，我们需要执行以下操作:

• 如果要删除的节点是第一个节点，那么只需将 Head 的 Next 指针设置为指向要删除的节点的下一个元素。并更新最后一个节点的下一个指针。
• 如果节点在中间的某个地方，那么找到它前面的节点，并使它前面的节点指向它旁边的节点。
• 如果节点在末尾，则将其移除，并使新的最后一个节点指向头部。

 node* CircularLinkedList :: **deleteNode**(int x) {
  *//searching the Node with data x*
  node *n = **search**(x);
  node *ptr = head;
  **if**(ptr == NULL) {
    cout << "List is empty";
    return NULL;
  }
  **else if**(ptr == n) {
    ptr**->**next = n**->**next;
    return n;
  }
  **else** {
    while(ptr**->**next != n) {
      ptr = ptr**->**next;
    }
    ptr**->**next = n**->**next;
    return n;
  }
}