Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/5.循环链表.md

5. 循环链表

概念

循环链表（Circular Linked List）是对单链表 / 双链表的改进：把表中最后一个结点的 next 指针从 NULL 改为指向头结点（或指向第一个结点），从而形成一个环。

两种主要形式

• 循环单链表：最后一个结点 next 指向头结点，形成单向环。p->next == L 表示到达表尾（遍历终止条件从「判 NULL」变为「判是否回到头结点」）。
• 循环双链表：在双链表基础上，表尾的 next 指向头结点、头结点的 prior 指向表尾，形成双向环。L->prior 就是表尾，可 O(1) 得到尾结点。

特点与优势

• 从任意结点出发都能遍历整个表（单链表做不到）。
• 若用尾指针 tail 表示循环单链表，则访问表头（tail->next->next）和表尾（tail）都是 O(1)，特别适合「队头插入 + 队尾插入」的场景。
• 循环链表的判空：L->next == L（只有头结点自身成环）。
• 循环链表的遍历终止条件：p != L（而非 p != NULL）。

本章采用带头结点的循环单链表实现，概念中说明循环双链表（表尾 next 回头、头结点 prior 指尾）。

核心操作

操作	说明
初始化	创建头结点，令 L->next = L（自环，即空表）
判空	L->next == L（头结点指向自己）
按位查找	从第一个结点开始计数，回到头结点仍未找到则失败
按值查找	遍历整个环，回到头结点表示查完
按位插入	找到第 i-1 个结点后插
删除	找到第 i-1 个结点，绕过第 i 个并释放
遍历打印	从 L->next 开始，直到 p == L 终止

遍历终止条件变化：非循环链表用 p != NULL；循环链表用 p != L。这正是循环链表判空/遍历的核心差异点。

复杂度分析

操作	时间复杂度	空间复杂度	原因
初始化	O(1)	O(1)	只创建头结点并让其自环
判空	O(1)	O(1)	比较 L->next == L
按位查找	O(n)	O(1)	仍需从头遍历，只是终止条件变化
按值查找	O(n)	O(1)	遍历整个环
按位插入 / 删除	O(n)	O(1)	找位置 O(n)，指针操作 O(1)
尾指针时访问表头/表尾	O(1)	O(1)	tail->next 与 tail 直接可得
遍历打印	O(n)	O(1)	绕环一圈

循环链表的复杂度与单链表基本一致，本质收益在于：结构成环后可 O(1) 从尾到头衔接，且能从任意结点遍历全表。用尾指针实现时，首尾操作都变为 O(1)。

语言实现

C

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

typedef struct CNode {
    int data;
    struct CNode *next;
} CNode, *CLinkList;

// 初始化：创建头结点，令其自环（空表）
CLinkList initList(void) {
    CLinkList L = (CNode *)malloc(sizeof(CNode));
    if (L == NULL) exit(1);
    L->next = L;      // 关键：自环表示空表
    return L;
}

// 判空：头结点是否指向自己
int isEmpty(CLinkList L) {
    return L->next == L;
}

// 按位查找：返回第 i 个结点（i 从 1 开始），回到头结点仍未找到则失败
CNode *getNode(CLinkList L, int i) {
    if (i < 1) return NULL;
    CNode *p = L->next;
    int j = 1;
    while (p != L && j < i) {   // 注意终止条件 p != L
        p = p->next;
        j++;
    }
    if (p == L) return NULL;    // 遍历完整个环都没到第 i 个
    return p;
}

// 按值查找：遍历整个环查找 x
CNode *locateNode(CLinkList L, int x) {
    CNode *p = L->next;
    while (p != L && p->data != x)  // 回到头结点代表查完
        p = p->next;
    if (p == L) return NULL;        // 没找到
    return p;
}

// 按位插入：在第 i 个位置插入 x（找第 i-1 个结点后插）
int insertList(CLinkList L, int i, int x) {
    if (i < 1) return 0;
    CNode *pre = L;
    int j = 0;
    // 找第 i-1 个结点；最多绕环一圈（j 从 0 到 i-1，i 合法时 pre 不会回到头结点）
    while (j < i - 1) {
        pre = pre->next;
        if (pre == L) return 0;     // 位置非法：越过了表尾
        j++;
    }
    CNode *s = (CNode *)malloc(sizeof(CNode));
    if (s == NULL) exit(1);
    s->data = x;
    s->next = pre->next;
    pre->next = s;
    return 1;
}

// 删除第 i 个结点，用 e 带回其值
int deleteList(CLinkList L, int i, int *e) {
    if (i < 1) return 0;
    CNode *pre = L;
    int j = 0;
    while (j < i - 1) {
        pre = pre->next;
        if (pre == L) return 0;     // 位置非法
        j++;
    }
    if (pre->next == L) return 0;   // 第 i 个结点不存在
    CNode *q = pre->next;
    *e = q->data;
    pre->next = q->next;
    free(q);
    return 1;
}

// 遍历打印：从第一个结点到回到头结点为止
void printList(CLinkList L) {
    if (isEmpty(L)) {
        printf("空链表\n");
        return;
    }
    CNode *p = L->next;
    while (p != L) {                // 终止条件 p != L
        printf("%d", p->data);
        if (p->next != L) printf(" -> ");
        p = p->next;
    }
    printf(" -> (回到头结点)\n");
}

int main(void) {
    CLinkList L = initList();
    printf("初始状态: ");
    printList(L);
    printf("判空=%d\n", isEmpty(L));

    // 尾插建立 10 20 30（每次插在表尾，即 pre 走到表尾）
    insertList(L, 1, 10);
    insertList(L, 2, 20);
    insertList(L, 3, 30);
    insertList(L, 2, 15);           // 按位插入：第 2 位
    printList(L);

    CNode *p = getNode(L, 3);       // 按位查找
    printf("第3个结点=%s", p ? "存在" : "不存在");
    if (p) printf(", 值=%d", p->data);
    printf("\n");

    p = locateNode(L, 25);          // 按值查找
    printf("值为25的结点=%s\n", p ? "存在" : "不存在");

    int e;
    if (deleteList(L, 2, &e))       // 删除第 2 个
        printf("删除元素=%d\n", e);
    printList(L);

    // 释放：绕环一圈释放所有结点，最后释放头结点
    CNode *q = L->next;
    while (q != L) {
        CNode *t = q->next;
        free(q);
        q = t;
    }
    free(L);
    return 0;
}

C++

#include <iostream>
using namespace std;

struct CNode {
    int data;
    CNode *next;
    CNode(int d) : data(d), next(nullptr) {}
};

class CLinkList {
private:
    CNode *head;   // 头结点

public:
    // 初始化：头结点自环
    CLinkList() {
        head = new CNode(0);
        head->next = head;
    }

    ~CLinkList() {   // 释放整个环
        CNode *p = head->next;
        while (p != head) {
            CNode *t = p->next;
            delete p;
            p = t;
        }
        delete head;
    }

    bool isEmpty() const { return head->next == head; }

    CNode *getNode(int i) const {
        if (i < 1) return nullptr;
        CNode *p = head->next;
        int j = 1;
        while (p != head && j < i) { p = p->next; j++; }
        if (p == head) return nullptr;
        return p;
    }

    CNode *locateNode(int x) const {
        CNode *p = head->next;
        while (p != head && p->data != x) p = p->next;
        if (p == head) return nullptr;
        return p;
    }

    bool insertList(int i, int x) {
        if (i < 1) return false;
        CNode *pre = head;
        int j = 0;
        while (j < i - 1) {
            pre = pre->next;
            if (pre == head) return false;  // 越界
            j++;
        }
        CNode *s = new CNode(x);
        s->next = pre->next;
        pre->next = s;
        return true;
    }

    bool deleteList(int i, int &e) {
        if (i < 1) return false;
        CNode *pre = head;
        int j = 0;
        while (j < i - 1) {
            pre = pre->next;
            if (pre == head) return false;
            j++;
        }
        if (pre->next == head) return false;
        CNode *q = pre->next;
        e = q->data;
        pre->next = q->next;
        delete q;
        return true;
    }

    void print() const {
        if (isEmpty()) { cout << "空链表" << endl; return; }
        CNode *p = head->next;
        while (p != head) {
            cout << p->data;
            if (p->next != head) cout << " -> ";
            p = p->next;
        }
        cout << " -> (回到头结点)" << endl;
    }
};

int main() {
    CLinkList L;
    cout << "初始状态: ";
    L.print();
    cout << "判空=" << L.isEmpty() << endl;

    L.insertList(1, 10);
    L.insertList(2, 20);
    L.insertList(3, 30);
    L.insertList(2, 15);      // 按位插入
    L.print();

    CNode *p = L.getNode(3);
    cout << "第3个结点=" << (p ? "存在" : "不存在");
    if (p) cout << ", 值=" << p->data;
    cout << endl;

    cout << "值为25的结点=" << (L.locateNode(25) ? "存在" : "不存在") << endl;

    int e;
    if (L.deleteList(2, e))
        cout << "删除元素=" << e << endl;
    L.print();
    return 0;
}

Java

public class CLinkListDemo {
    // 循环单链表结点
    static class CNode {
        int data;
        CNode next;
        CNode(int d) { data = d; }
    }

    static class CLinkList {
        private final CNode head;   // 头结点

        // 初始化：头结点自环
        CLinkList() {
            head = new CNode(0);
            head.next = head;
        }

        boolean isEmpty() { return head.next == head; }

        CNode getNode(int i) {
            if (i < 1) return null;
            CNode p = head.next;
            int j = 1;
            while (p != head && j < i) { p = p.next; j++; }
            if (p == head) return null;
            return p;
        }

        CNode locateNode(int x) {
            CNode p = head.next;
            while (p != head && p.data != x) p = p.next;
            if (p == head) return null;
            return p;
        }

        boolean insertList(int i, int x) {
            if (i < 1) return false;
            CNode pre = head;
            int j = 0;
            while (j < i - 1) {
                pre = pre.next;
                if (pre == head) return false;
                j++;
            }
            CNode s = new CNode(x);
            s.next = pre.next;
            pre.next = s;
            return true;
        }

        Integer deleteList(int i) {
            if (i < 1) return null;
            CNode pre = head;
            int j = 0;
            while (j < i - 1) {
                pre = pre.next;
                if (pre == head) return null;
                j++;
            }
            if (pre.next == head) return null;
            CNode q = pre.next;
            pre.next = q.next;
            return q.data;
        }

        void print() {
            if (isEmpty()) { System.out.println("空链表"); return; }
            CNode p = head.next;
            while (p != head) {
                System.out.print(p.data);
                if (p.next != head) System.out.print(" -> ");
                p = p.next;
            }
            System.out.println(" -> (回到头结点)");
        }
    }

    public static void main(String[] args) {
        CLinkList L = new CLinkList();
        System.out.print("初始状态: ");
        L.print();
        System.out.println("判空=" + L.isEmpty());

        L.insertList(1, 10);
        L.insertList(2, 20);
        L.insertList(3, 30);
        L.insertList(2, 15);      // 按位插入
        L.print();

        CNode p = L.getNode(3);
        System.out.println("第3个结点=" + (p != null ? "存在, 值=" + p.data : "不存在"));
        System.out.println("值为25的结点=" + (L.locateNode(25) != null ? "存在" : "不存在"));

        Integer e = L.deleteList(2);
        System.out.println("删除元素=" + e);
        L.print();
    }
}

Python

class CNode:
    """循环单链表结点"""

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


class CLinkList:
    """带头结点的循环单链表"""

    def __init__(self):
        # 初始化：头结点自环表示空表
        self._head = CNode(None)
        self._head.next = self._head

    def is_empty(self) -> bool:
        return self._head.next is self._head

    def get_node(self, i: int):
        """按位查找：返回第 i 个结点（i 从 1 开始）"""
        if i < 1:
            return None
        p = self._head.next
        j = 1
        while p is not self._head and j < i:
            p = p.next
            j += 1
        if p is self._head:
            return None
        return p

    def locate_node(self, x):
        """按值查找：遍历整个环"""
        p = self._head.next
        while p is not self._head and p.data != x:
            p = p.next
        if p is self._head:
            return None
        return p

    def insert_list(self, i: int, x) -> bool:
        """按位插入：在第 i 个位置插入 x"""
        if i < 1:
            return False
        pre = self._head
        j = 0
        while j < i - 1:
            pre = pre.next
            if pre is self._head:
                return False       # 越界
            j += 1
        s = CNode(x)
        s.next = pre.next
        pre.next = s
        return True

    def delete_list(self, i: int):
        """按位删除：删除第 i 个结点并返回其值"""
        if i < 1:
            return None
        pre = self._head
        j = 0
        while j < i - 1:
            pre = pre.next
            if pre is self._head:
                return None
            j += 1
        if pre.next is self._head:
            return None
        q = pre.next
        pre.next = q.next
        return q.data

    def print_list(self):
        if self.is_empty():
            print("空链表")
            return
        vals = []
        p = self._head.next
        while p is not self._head:      # 终止条件：回到头结点
            vals.append(str(p.data))
            p = p.next
        print(" -> ".join(vals), "-> (回到头结点)")


if __name__ == "__main__":
    L = CLinkList()
    print("初始状态:", end=" ")
    L.print_list()
    print("判空 =", L.is_empty())

    L.insert_list(1, 10)
    L.insert_list(2, 20)
    L.insert_list(3, 30)
    L.insert_list(2, 15)        # 按位插入
    L.print_list()

    p = L.get_node(3)
    print("第3个结点 =", "存在, 值 = " + str(p.data) if p else "不存在")
    print("值为25的结点 =", "存在" if L.locate_node(25) else "不存在")

    e = L.delete_list(2)
    print("删除元素 =", e)
    L.print_list()