数据结构：循环链表介绍

# 1. 简介

## 1.1 什么是数据结构

数据结构是计算机科学中重要的概念之一，用于存储和组织数据的方式或方法。它定义了数据元素之间的关系，并提供了对数据进行操作和管理的方法。数据结构可以看作是数据的逻辑组织方式，是程序设计中非常基础的概念，在很多领域都有广泛的应用。

## 1.2 循环链表的定义和特点

循环链表是一种特殊的链表结构，在普通链表的基础上，将最后一个节点的"下一个节点"指针指向链表的头节点，形成一个环形结构。与普通链表相比，循环链表具有以下特点：

- 可以通过任何一个节点遍历整个链表；
- 不需要维护链表的头节点指针，操作起来更加方便；
- 可以充分利用链表内存空间，减少空间的浪费。

循环链表在某些场景下具有更高的效率和灵活性，是链表的一种扩展形式。接下来，我们将探讨循环链表的实现方法、基本操作以及与普通链表的比较等内容。

# 2. 实现循环链表

循环链表是一种特殊的链表，它的最后一个节点指向链表的头节点，形成了一个环形的数据结构。循环链表在某些场景下具有独特的优势，因此在实际开发中经常被使用。

### 单向循环链表的实现方法

单向循环链表的实现方法与普通的单向链表类似，唯一的区别在于最后一个节点的next指针指向头节点。以下是使用Python语言实现单向循环链表的示例代码：

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

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

    def insert(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        if self.head is None:
            print("Circular Linked List is empty.")
            return

        temp = self.head
        while True:
            print(temp.data, end=" ")
            temp = temp.next
            if temp == self.head:
                break

cll = CircularLinkedList()
cll.insert(1)
cll.insert(2)
cll.insert(3)
cll.insert(4)
cll.insert(5)
cll.display()

代码解析：
- 定义了Node类，用于表示循环链表的节点，每个节点包含一个数据和一个指向下一个节点的指针。
- 定义了CircularLinkedList类，用于表示循环链表。该类包含一个头节点，初始时为空。同时，该类还提供了插入节点和展示链表的方法。
- 在插入节点时，如果链表为空，直接将新节点作为头节点，且新节点的next指针指向头节点。否则，遍历链表找到最后一个节点，将其next指针指向新节点，再将新节点的next指针指向头节点。
- 在展示链表时，从头节点开始遍历链表，打印每个节点的数据，直到回到头节点。

运行以上代码，输出结果为：1 2 3 4 5

### 双向循环链表的实现方法

双向循环链表除了拥有单向循环链表的特点外，还具备双向遍历的功能。每个节点除了有一个指向下一个节点的指针外，还有一个指向前一个节点的指针。以下是使用Java语言实现双向循环链表的示例代码：

class Node {
    int data;
    Node prev;
    Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyCircularLinkedList {
    Node head;

    public void insert(int data) {
        Node new_node = new Node(data);

        if (head == null) {
            head = new_node;
            head.next = head;
            head.prev = head;
        } else {
            Node temp = head.prev;
            temp.next = new_node;
            new_node.prev = temp;
            new_node.next = head;
            head.prev = new_node;
        }
    }

    public void display() {
        if (head == null) {
            System.out.println("Doubly Circular Linked List is empty.");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyCircularLinkedList dcll = new DoublyCircularLinkedList();
        dcll.insert(1);
        dcll.insert(2);
        dcll.insert(3);
        dcll.insert(4);
        dcll.insert(5);
        dcll.display();
    }
}

代码解析：
- 定义了Node类，用于表示双向循环链表的节点，每个节点包含一个数据和两个指针，分别指向前一个节点和下一个节点。
- 定义了DoublyCircularLinkedList类，用于表示双向循环链表。该类包含一个头节点，初始时为空。同时，该类还提供了插入节点和展示链表的方法。
- 在插入节点时，如果链表为空，直接将新节点作为头节点，且新节点的prev和next指针均指向自身。否则，先将新节点的prev指针指向原来的最后一个节点，再将新节点的next指针指向头节点，同时将原来的最后一个节点的next指针指向新节点，以及头节点的prev指针指向新节点。