循环链表

循环链表是一种链表，其中第一个和最后一个节点也相互连接以形成一个圆。

循环链表主要有两种类型

1. 循环单链表

在这里，最后一个节点的地址包含第一个节点的地址。

Circular Linked List Representation — 循环链表表示

2. 循环双链表

在这里，除了最后一个节点存储第一个节点的地址外，第一个节点还将存储最后一个节点的地址。

Circular Doubly Linked List Representation — 循环双链表表示

注意：我们将使用单向循环链表来表示循环链表的工作方式。

循环链表表示

让我们看看如何在算法/代码中表示循环链表。假设我们有一个链表

这里，单个节点表示为

struct Node {
    int data;
    struct Node * next;
};

每个结构节点都有一个数据项和一个指向下一个结构节点的指针。

现在我们将创建一个简单的包含三个项的循环链表来理解它是如何工作的。

/* Initialize nodes */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;

/* Save address of third node in last */
last = three;

在上面的代码中，one、two 和 three 是数据项为 1、2 和 3 的节点。

对于节点 one

next 存储 two 的地址（它前面没有节点）

对于节点 two

next 存储 three 的地址

对于节点 three

next 存储 NULL（它后面没有节点）
next 指向节点 one

循环链表的插入

我们可以在循环链表的 3 个不同位置插入元素

假设我们有一个包含元素 1、2 和 3 的循环链表。

让我们在上面创建的循环链表的不同位置添加一个值为 6 的节点。第一步是创建一个新节点。

为 newNode 分配内存
为 newNode 分配数据

1. 在开头插入

将当前第一个节点的地址存储在 newNode 中（即将 newNode 指向当前第一个节点）
将最后一个节点指向 newNode（即将 newNode 作为头节点）

2. 在两个节点之间插入

让我们在第一个节点之后插入 newNode。

遍历到给定的节点（设该节点为 p）
将 newNode 的 next 指向 p 之后的节点
将 newNode 的地址存储在 p 的 next 中

3. 在末尾插入

将头节点的地址存储到 newNode 的 next 中（使 newNode 成为最后一个节点）
将当前最后一个节点指向 newNode
将 newNode 设置为最后一个节点

循环链表的删除

假设我们有一个包含元素 1、2 和 3 的双向链表。

1. 如果要删除的节点是唯一节点

释放节点占用的内存
将 last 存储为 NULL

2. 如果要删除最后一个节点

找到最后一个节点之前的节点（设为 temp）
将最后一个节点之后的节点的地址存储在 temp 中
释放 last 的内存
将 temp 设置为最后一个节点

3. 如果要删除其他节点

遍历到要删除的节点（此处删除节点 2）
设节点 2 前面的节点为 temp
将节点 2 之后的节点的地址存储在 temp 中
释放节点 2 的内存

Python、Java、C 和 C++ 中的循环链表代码

Python

Java

C++

# Python code to perform circular linked list operations

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.last = None

    def addToEmpty(self, data):

        if self.last != None:
            return self.last

        # allocate memory to the new node and add data to the node
        newNode = Node(data)

        # assign last to newNode
        self.last = newNode

        # create link to iteself
        self.last.next = self.last
        return self.last

    # add node to the front
    def addFront(self, data):

        # check if the list is empty
        if self.last == None:
            return self.addToEmpty(data)

        # allocate memory to the new node and add data to the node
        newNode = Node(data)

        # store the address of the current first node in the newNode
        newNode.next = self.last.next

        # make newNode as last
        self.last.next = newNode

        return self.last

    # add node to the end
    def addEnd(self, data):
        # check if the node is empty
        if self.last == None:
            return self.addToEmpty(data)

        # allocate memory to the new node and add data to the node
        newNode = Node(data)

        # store the address of the last node to next of newNode
        newNode.next = self.last.next

        # point the current last node to the newNode
        self.last.next = newNode

        # make newNode as the last node
        self.last = newNode

        return self.last

    # insert node after a specific node
    def addAfter(self, data, item):

        # check if the list is empty
        if self.last == None:
            return None

        newNode = Node(data)
        p = self.last.next
        while p:

            # if the item is found, place newNode after it
            if p.data == item:

                # make the next of the current node as the next of newNode
                newNode.next = p.next

                # put newNode to the next of p
                p.next = newNode

                if p == self.last:
                    self.last = newNode
                    return self.last
                else:
                    return self.last
            p = p.next
            if p == self.last.next:
                print(item, "The given node is not present in the list")
                break

    # delete a node
    def deleteNode(self, last, key):

        # If linked list is empty
        if last == None:
            return

        # If the list contains only a single node
        if (last).data == key and (last).next == last:

            last = None

        temp = last
        d = None

        # if last node is to be deleted
        if (last).data == key:

            # find the node before the last node
            while temp.next != last:
                temp = temp.next

            # point temp node to the next of last i.e. first node
            temp.next = (last).next
            last = temp.next

        # travel to the node to be deleted
        while temp.next != last and temp.next.data != key:
            temp = temp.next

        # if node to be deleted was found
        if temp.next.data == key:
            d = temp.next
            temp.next = d.next

        return last

    def traverse(self):
        if self.last == None:
            print("The list is empty")
            return

        newNode = self.last.next
        while newNode:
            print(newNode.data, end=" ")
            newNode = newNode.next
            if newNode == self.last.next:
                break


# Driver Code
if __name__ == "__main__":

    cll = CircularLinkedList()

    last = cll.addToEmpty(6)
    last = cll.addEnd(8)
    last = cll.addFront(2)
    last = cll.addAfter(10, 2)

    cll.traverse()

    last = cll.deleteNode(last, 8)
    print()
    cll.traverse()

// Java code to perform circular linked list operations

class CircularLinkedList {

  static class Node {
    int data;
    Node next;
  };

  static Node addToEmpty(Node last, int data) {
    if (last != null)
      return last;

    // allocate memory to the new node
    Node newNode = new Node();

    // assign data to the new node
    newNode.data = data;

    // assign last to newNode
    last = newNode;

    // create link to iteself
    newNode.next = last;

    return last;
  }

  // add node to the front
  static Node addFront(Node last, int data) {
    if (last == null)
      return addToEmpty(last, data);

    // allocate memory to the new node
    Node newNode = new Node();

    // add data to the node
    newNode.data = data;

    // store the address of the current first node in the newNode
    newNode.next = last.next;

    // make newNode as head
    last.next = newNode;

    return last;
  }

  // add node to the end
  static Node addEnd(Node last, int data) {
    if (last == null)
      return addToEmpty(last, data);

    // allocate memory to the new node
    Node newNode = new Node();

    // add data to the node
    newNode.data = data;

    // store the address of the head node to next of newNode
    newNode.next = last.next;

    // point the current last node to the newNode
    last.next = newNode;

    // make newNode as the last node
    last = newNode;

    return last;
  }

  static Node addAfter(Node last, int data, int item) {
    if (last == null)
      return null;

    Node newNode, p;
    p = last.next;
    do {
      // if the item is found, place newNode after it
      if (p.data == item) {
        // allocate memory to the new node
        newNode = new Node();

        // add data to the node
        newNode.data = data;

        // make the next of the current node as the next of newNode
        newNode.next = p.next;

        // put newNode to the next of p
        p.next = newNode;

        // if p is the last node, make newNode as the last node
        if (p == last)
          last = newNode;
        return last;
      }
      p = p.next;
    } while (p != last.next);

    System.out.println(item + "The given node is not present in the list");
    return last;

  }

	// delete a node
  static Node deleteNode(Node last, int key) {
    // if linked list is empty
    if (last == null)
      return null;

    // if the list contains only a single node
    if (last.data == key && last.next == last) {
      last = null;
      return last;
    }

    Node temp = last, d = new Node();

    // if last is to be deleted
    if (last.data == key) {
      // find the node before the last node
      while (temp.next != last) {
        temp = temp.next;
      }

      // point temp node to the next of last i.e. first node
      temp.next = last.next;
      last = temp.next;
    }

    // travel to the node to be deleted
    while (temp.next != last && temp.next.data != key) {
      temp = temp.next;
    }

    // if node to be deleted was found
    if (temp.next.data == key) {
      d = temp.next;
      temp.next = d.next;
    }
    return last;
  }

  static void traverse(Node last) {
    Node p;

    if (last == null) {
      System.out.println("List is empty.");
      return;
    }

    p = last.next;

    do {
      System.out.print(p.data + " ");
      p = p.next;

    }
    while (p != last.next);

  }

  public static void main(String[] args) {
    Node last = null;

    last = addToEmpty(last, 6);
    last = addEnd(last, 8);
    last = addFront(last, 2);

    last = addAfter(last, 10, 2);

    traverse(last);

    deleteNode(last, 8);
    traverse(last);
  }
}

// C code to perform circular linked list operations

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

struct Node {
  int data;
  struct Node* next;
};

struct Node* addToEmpty(struct Node* last, int data) {
  if (last != NULL) return last;

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to the new node
  newNode->data = data;

  // assign last to newNode
  last = newNode;

  // create link to iteself
  last->next = last;

  return last;
}

// add node to the front
struct Node* addFront(struct Node* last, int data) {
  // check if the list is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the current first node in the newNode
  newNode->next = last->next;

  // make newNode as head
  last->next = newNode;

  return last;
}

// add node to the end
struct Node* addEnd(struct Node* last, int data) {
  // check if the node is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the head node to next of newNode
  newNode->next = last->next;

  // point the current last node to the newNode
  last->next = newNode;

  // make newNode as the last node
  last = newNode;

  return last;
}

// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
  // check if the list is empty
  if (last == NULL) return NULL;

  struct Node *newNode, *p;

  p = last->next;
  do {
  // if the item is found, place newNode after it
  if (p->data == item) {
    // allocate memory to the new node
    newNode = (struct Node*)malloc(sizeof(struct Node));

    // add data to the node
    newNode->data = data;

    // make the next of the current node as the next of newNode
    newNode->next = p->next;

    // put newNode to the next of p
    p->next = newNode;

    // if p is the last node, make newNode as the last node
    if (p == last) last = newNode;
    return last;
  }

  p = p->next;
  } while (p != last->next);

  printf("\nThe given node is not present in the list");
  return last;
}

// delete a node
void deleteNode(struct Node** last, int key) {
  // if linked list is empty
  if (*last == NULL) return;

  // if the list contains only a single node
  if ((*last)->data == key && (*last)->next == *last) {
  free(*last);
  *last = NULL;
  return;
  }

  struct Node *temp = *last, *d;

  // if last is to be deleted
  if ((*last)->data == key) {
  // find the node before the last node
  while (temp->next != *last) temp = temp->next;

  // point temp node to the next of last i.e. first node
  temp->next = (*last)->next;
  free(*last);
  *last = temp;
  }

  // travel to the node to be deleted
  while (temp->next != *last && temp->next->data != key) {
  temp = temp->next;
  }

  // if node to be deleted was found
  if (temp->next->data == key) {
  d = temp->next;
  temp->next = d->next;
  free(d);
  }
}

void traverse(struct Node* last) {
  struct Node* p;

  if (last == NULL) {
  printf("The list is empty");
  return;
  }

  p = last->next;

  do {
  printf("%d ", p->data);
  p = p->next;

  } while (p != last->next);
}

int main() {
  struct Node* last = NULL;

  last = addToEmpty(last, 6);
  last = addEnd(last, 8);
  last = addFront(last, 2);

  last = addAfter(last, 10, 2);

  traverse(last);

  deleteNode(&last, 8);

  printf("\n");

  traverse(last);

  return 0;
}

// C++ code to perform circular linked list operations

#include <iostream>

using namespace std;

struct Node {
  int data;
  struct Node* next;
};

struct Node* addToEmpty(struct Node* last, int data) {
  if (last != NULL) return last;

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to the new node
  newNode->data = data;

  // assign last to newNode
  last = newNode;

  // create link to iteself
  last->next = last;

  return last;
}

// add node to the front
struct Node* addFront(struct Node* last, int data) {
  // check if the list is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the current first node in the newNode
  newNode->next = last->next;

  // make newNode as head
  last->next = newNode;

  return last;
}

// add node to the end
struct Node* addEnd(struct Node* last, int data) {
  // check if the node is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the head node to next of newNode
  newNode->next = last->next;

  // point the current last node to the newNode
  last->next = newNode;

  // make newNode as the last node
  last = newNode;

  return last;
}

// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
  // check if the list is empty
  if (last == NULL) return NULL;

  struct Node *newNode, *p;

  p = last->next;
  do {
  // if the item is found, place newNode after it
  if (p->data == item) {
    // allocate memory to the new node
    newNode = (struct Node*)malloc(sizeof(struct Node));

    // add data to the node
    newNode->data = data;

    // make the next of the current node as the next of newNode
    newNode->next = p->next;

    // put newNode to the next of p
    p->next = newNode;

    // if p is the last node, make newNode as the last node
    if (p == last) last = newNode;
    return last;
  }

  p = p->next;
  } while (p != last->next);

  cout << "\nThe given node is not present in the list" << endl;
  return last;
}

// delete a node
void deleteNode(Node** last, int key) {
  // if linked list is empty
  if (*last == NULL) return;

  // if the list contains only a single node
  if ((*last)->data == key && (*last)->next == *last) {
  free(*last);
  *last = NULL;
  return;
  }

  Node *temp = *last, *d;

  // if last is to be deleted
  if ((*last)->data == key) {
  // find the node before the last node
  while (temp->next != *last) temp = temp->next;

  // point temp node to the next of last i.e. first node
  temp->next = (*last)->next;
  free(*last);
  *last = temp->next;
  }

  // travel to the node to be deleted
  while (temp->next != *last && temp->next->data != key) {
  temp = temp->next;
  }

  // if node to be deleted was found
  if (temp->next->data == key) {
  d = temp->next;
  temp->next = d->next;
  free(d);
  }
}

void traverse(struct Node* last) {
  struct Node* p;

  if (last == NULL) {
  cout << "The list is empty" << endl;
  return;
  }

  p = last->next;

  do {
  cout << p->data << " ";
  p = p->next;

  } while (p != last->next);
}

int main() {
  struct Node* last = NULL;

  last = addToEmpty(last, 6);
  last = addEnd(last, 8);
  last = addFront(last, 2);

  last = addAfter(last, 10, 2);

  traverse(last);

  deleteNode(&last, 8);
  cout << endl;

  traverse(last);

  return 0;
}

循环链表复杂度

循环链表复杂度	时间复杂度	空间复杂度
插入操作	O(1) 或 O(n)	O(1)
删除操作	O(1)	O(1)

1. 插入操作的复杂度

不需要遍历的插入操作的时间复杂度为 O(1)。
而需要遍历的插入操作的时间复杂度为 O(n)。
空间复杂度为 O(1)。

2. 删除操作的复杂度

所有删除操作的运行时间复杂度均为 O(1)。
而空间复杂度为 O(1)。

为什么需要循环链表？

不需要 NULL 赋值，因为一个节点总是指向另一个节点。
起始点可以设置为任何节点。
从第一个节点到最后一个节点的遍历很快。

循环链表应用

它用于多人游戏，让每个玩家都有机会玩游戏。
操作系统可以将多个运行的应用程序放在循环链表中。操作系统会不断地迭代这些应用程序。

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python
程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

循环链表

循环链表表示

循环链表的插入

1. 在开头插入

2. 在两个节点之间插入

3. 在末尾插入

循环链表的删除

1. 如果要删除的节点是唯一节点

2. 如果要删除最后一个节点

3. 如果要删除其他节点

Python、Java、C 和 C++ 中的循环链表代码

循环链表复杂度

为什么需要循环链表？

循环链表应用

目录

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

DSA 教程

循环链表

循环链表表示

循环链表的插入

1. 在开头插入

2. 在两个节点之间插入

3. 在末尾插入

循环链表的删除

1. 如果要删除的节点是唯一节点

2. 如果要删除最后一个节点

3. 如果要删除其他节点

Python、Java、C 和 C++ 中的循环链表代码

循环链表复杂度

为什么需要循环链表？

循环链表应用

目录

相关教程

成为一名认证的 Python
程序员。