CC++ & Algorithm

双向链表与循环链表

极难4
语言版本：通用
概述：双向链表让节点可以前后走，循环链表让首尾相连，两种链表扩展了基本链表的能力。

双向链表和循环链表：让链表更灵活、更好玩

你有没有玩过“传话游戏”？大家排成一列，只能往后传话。如果传话只能朝一个方向，万一中间有个人想往前传，就得从头开始。在编程中，单向链表就是这样：每个节点只有指向下一个节点的指针，不能回头。但如果我们给每个节点再装一个指向前一个节点的指针，它就变成了 双向链表——可以前后自由移动。如果再让最后一个节点的指针指向第一个节点，就变成了 循环链表——好像大家手拉手围成一个圈，永远没有终点。

这两种“升级版”链表在实际编程中非常有用。比如操作系统轮流执行任务时，就用循环链表让每个程序轮流获得CPU时间；再比如实现“撤销/重做”功能时，双向链表可以帮你轻松前后翻页。下面就让我们从生活例子出发，彻底搞懂它们！

生活中的例子：排队和丢手绢

  • 单向链表：像幼儿园小朋友站成一列，每个人都只拉着前面人的衣服，老师喊“向后转”，大家只能一个个转头，很麻烦。
  • 双向链表：每个小朋友都同时拉着前面和后面小朋友的衣服。你现在可以向前走，也可以向后走。比如你想从队尾走到队头，只需要不断往前找“前面的人”就行。
  • 循环链表：最后一个小朋友的手搭在第一个小朋友的肩膀上，大家围成一个圈。这样无论从谁开始，都能转圈走。这就像“丢手绢”游戏，大家围坐一圈，手绢沿着圈传递。

这些生活中的场景，就是链表结构的基本思想。

一、双向链表：前后都有路

1. 概念与图示

双向链表的每个节点有 两个指针：prev（指向上一个节点）和 next（指向下一个节点）。头节点的prev是空（NULL），尾节点的next是空。

 NULL <-- prev | 10 | next --> <-- prev | 20 | next --> <-- prev | 30 | next --> NULL
          head                                              tail

你可以从head出发，一路用next向尾部走；也可以从尾部出发，一路用prev向头部走。

2. 为什么需要双向链表？

  • 双向遍历：反向遍历不需要重新从头开始，直接找尾节点就行。
  • 快速删除任意节点：在单向链表中要删除一个节点，必须先找到它的前驱；而双向链表中有prev指针，可以直接拿到前驱，时间复杂度从O(n)降为O(1)（前提是已知节点地址）。
  • 缺点：每个节点多占一个指针的内存（在32位系统多4字节，64位多8字节）。

3. 常见错误（新手必看！）

  • 忘记更新前驱指针：插入或删除时，只改了next，没改prev，导致链表断裂。
  • 访问空指针的prev或next：比如在循环里cur = cur->next后，没有判断cur是否为NULL，就访问cur->prev。
  • 头节点删除后没更新head：删除头节点时，需要把head指向下一个节点，否则链表就丢了。

4. 完整代码（C++ 与 Python，带中文注释）

下面代码实现了双向链表的头插、尾插、删除、正向和反向打印。每行变量定义都加了注释，方便理解。

#include <iostream>
using namespace std;

// 定义双向链表节点结构体
struct Node {
    int data;          // 数据域
    Node* prev;        // 指向前一个节点的指针
    Node* next;        // 指向后一个节点的指针
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}  // 构造函数
};

// 在链表头部插入新节点
void insertFront(Node* &head, int val) {
    Node* newNode = new Node(val);  // 创建新节点
    if (head != nullptr) {         // 如果链表非空
        head->prev = newNode;      // 原头节点的prev指向新节点
        newNode->next = head;      // 新节点的next指向原头节点
    }
    head = newNode;                // 更新头指针为新节点
}

// 在链表尾部插入新节点
void insertBack(Node* &head, int val) {
    Node* newNode = new Node(val); // 创建新节点
    if (head == nullptr) {        // 如果链表为空
        head = newNode;           // 新节点即为头节点
        return;
    }
    Node* cur = head;             // 临时指针cur从head开始
    while (cur->next != nullptr)  // 找到最后一个节点（next为nullptr）
        cur = cur->next;
    cur->next = newNode;          // 最后一个节点的next指向新节点
    newNode->prev = cur;          // 新节点的prev指向原来的最后一个节点
}

// 删除第一个值为val的节点
void deleteValue(Node* &head, int val) {
    Node* cur = head;             // 从head开始查找
    while (cur != nullptr && cur->data != val) 
        cur = cur->next;          // 找到目标节点或遍历结束
    if (cur == nullptr) return;   // 没找到，直接返回

    // 处理前驱指针
    if (cur->prev != nullptr) {   // 如果目标不是头节点
        cur->prev->next = cur->next;  // 前驱的next跳过当前节点
    } else {
        head = cur->next;         // 目标为头节点，更新head
    }
    // 处理后驱指针
    if (cur->next != nullptr) {   // 如果目标不是尾节点
        cur->next->prev = cur->prev;  // 后驱的prev跳过当前节点
    }
    delete cur;                   // 释放内存
}

// 正向打印：从头到尾
void printForward(Node* head) {
    Node* cur = head;
    while (cur != nullptr) {
        cout << cur->data << " <-> ";
        cur = cur->next;
    }
    cout << "NULL" << endl;
}

// 反向打印：从尾到头（先找到尾节点）
void printBackward(Node* head) {
    if (head == nullptr) return;   // 空链表直接返回
    Node* cur = head;
    while (cur->next != nullptr)   // 走到尾节点
        cur = cur->next;
    while (cur != nullptr) {       // 从尾向前遍历
        cout << cur->data << " <-> ";
        cur = cur->prev;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = nullptr;         // 初始化头指针为空

    insertBack(head, 10);         // 尾部插入10
    insertBack(head, 20);         // 尾部插入20
    insertBack(head, 30);         // 尾部插入30
    insertFront(head, 5);         // 头部插入5

    cout << "正向："; printForward(head);   // 输出：5 <-> 10 <-> 20 <-> 30 <-> NULL
    cout << "反向："; printBackward(head);  // 输出：30 <-> 20 <-> 10 <-> 5 <-> NULL

    deleteValue(head, 20);        // 删除值为20的节点
    cout << "删除20后正向："; printForward(head); // 输出：5 <-> 10 <-> 30 <-> NULL

    return 0;
}

# 定义双向链表节点类
class Node:
    def __init__(self, data):
        self.data = data    # 数据
        self.prev = None    # 前驱指针
        self.next = None    # 后继指针

# 定义双向链表类
class DoublyLinkedList:
    def __init__(self):
        self.head = None    # 头指针

    # 头部插入
    def insert_front(self, val):
        new_node = Node(val)          # 创建新节点
        if self.head:                 # 如果链表非空
            self.head.prev = new_node # 原头节点的prev指向新节点
            new_node.next = self.head # 新节点next指向原头节点
        self.head = new_node          # 更新头指针

    # 尾部插入
    def insert_back(self, val):
        new_node = Node(val)
        if not self.head:            # 空链表
            self.head = new_node
            return
        cur = self.head              # 从头开始找尾
        while cur.next:
            cur = cur.next
        cur.next = new_node          # 尾节点next指向新节点
        new_node.prev = cur          # 新节点prev指向原尾节点

    # 删除第一个值为val的节点
    def delete_value(self, val):
        cur = self.head
        while cur and cur.data != val:  # 查找
            cur = cur.next
        if not cur:                     # 没找到
            return
        if cur.prev:                    # 如果不是头节点
            cur.prev.next = cur.next
        else:
            self.head = cur.next        # 如果是头节点，更新head
        if cur.next:                    # 如果不是尾节点
            cur.next.prev = cur.prev

    # 正向打印
    def print_forward(self):
        cur = self.head
        while cur:
            print(cur.data, end=" <-> ")
            cur = cur.next
        print("None")

    # 反向打印
    def print_backward(self):
        cur = self.head
        if not cur:
            print("None")
            return
        # 先找到尾节点
        while cur.next:
            cur = cur.next
        while cur:
            print(cur.data, end=" <-> ")
            cur = cur.prev
        print("None")

# 测试代码
dll = DoublyLinkedList()
dll.insert_back(10)
dll.insert_back(20)
dll.insert_back(30)
dll.insert_front(5)
dll.print_forward()   # 输出：5 <-> 10 <-> 20 <-> 30 <-> None
dll.print_backward()  # 输出：30 <-> 20 <-> 10 <-> 5 <-> None
dll.delete_value(20)
dll.print_forward()   # 输出：5 <-> 10 <-> 30 <-> None

二、循环链表：首尾相连，无限循环

1. 概念与图示

循环链表可以是单向，也可以是双向。它的特点是：最后一个节点的next指针不再指向NULL，而是指向第一个节点（头节点）。如果是双向循环链表，头节点的prev还会指向尾节点。

单向循环链表（图示）：

       +-----------------------+
       |                       v
   head->[1]->[2]->[3]--+
                         ^
                         +------- (next of 3 指向 head)

双向循环链表（图示）：

    +----------------------------------------+
    |                                        v
  [prev | 1 | next] <-> [prev | 2 | next] <-> [prev | 3 | next]
  ^                                                              |
  +--------------------------------------------------------------+

头节点的prev指向尾节点，尾节点的next指向头节点，形成了一个闭合的环。

2. 为什么需要循环链表？

  • 适合“循环往复”的场景：比如多任务操作系统的时间片轮转，每个进程轮流占用CPU，用完时间片就排到队尾，循环链表可以轻松实现。
  • 约瑟夫问题：N个人围成一圈，从1开始报数，报到M的人出列，循环链表能自然地模拟这个“围圈”过程。
  • 不用考虑空链表？ 小心，循环链表的遍历条件不再是 cur != NULL，而是 cur != head（或者用一个计数器），否则会无限循环。

3. 常见错误（新手必看！）

  • 死循环：在遍历循环链表时，如果忘记判断是否回到起点，就会一直转下去。解决办法：先记录起始点，当再次碰到它时停止。
  • 删除所有节点后忘记处理：如果循环链表只有一个节点，删除它时要把头指针置空，并特别注意不要让指针指向自身。
  • 插入时破坏循环：在尾部插入新节点时，要同时将新节点的next指向头节点，并将原尾节点的next指向新节点（单向循环）；双向循环则更复杂，需要更新四个指针。

4. 完整代码：单向循环链表（C++）

下面实现一个简单的单向循环链表，包含插入、打印、删除（演示约瑟夫环的删除逻辑用）。注意变量定义的中文注释。

#include <iostream>
using namespace std;

struct Node {
    int data;        // 数据
    Node* next;      // 下一个节点指针
    Node(int val) : data(val), next(nullptr) {}
};

// 在循环链表尾部插入（实际上是把新节点添加到头节点之前？这里约定head指向头节点，尾节点指向head）
void insertAtEnd(Node* &head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {          // 空链表
        head = newNode;
        newNode->next = head;       // 自己指向自己，形成单节点循环
        return;
    }
    // 找到尾节点（尾节点的next是head）
    Node* cur = head;
    while (cur->next != head) {
        cur = cur->next;
    }
    cur->next = newNode;            // 原尾节点指向新节点
    newNode->next = head;           // 新节点指向头节点
}

// 打印循环链表（从头节点开始，打印一圈后停止）
void printCircular(Node* head) {
    if (head == nullptr) {
        cout << "空链表" << endl;
        return;
    }
    Node* cur = head;
    do {
        cout << cur->data << " -> ";
        cur = cur->next;
    } while (cur != head);          // 回到头节点则停止
    cout << "(回到头)" << endl;
}

// 删除第一个值为val的节点（适用于循环链表）
void deleteValueCircular(Node* &head, int val) {
    if (head == nullptr) return;
    Node* cur = head;
    Node* prev = nullptr;           // 前驱指针
    // 先从头节点开始找
    while (true) {
        if (cur->data == val) break;
        prev = cur;
        cur = cur->next;
        if (cur == head) return;    // 转了一圈没找到
    }
    // 找到待删除节点cur
    if (cur == head) {              // 删除头节点
        // 先找到尾节点
        Node* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        if (head->next == head) {   // 只有一个节点
            delete head;
            head = nullptr;
            return;
        }
        head = head->next;          // 头指针后移
        tail->next = head;          // 尾节点指向新头
        delete cur;
    } else {
        prev->next = cur->next;     // 前驱跳过cur
        delete cur;
    }
}

int main() {
    Node* head = nullptr;           // 初始化头指针为空
    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    insertAtEnd(head, 40);
    cout << "循环链表：";
    printCircular(head);            // 输出 10 -> 20 -> 30 -> 40 -> (回到头)
    deleteValueCircular(head, 20);
    cout << "删除20后：";
    printCircular(head);            // 输出 10 -> 30 -> 40 -> (回到头)
    return 0;
}

三、经典应用：约瑟夫环（Josephus Problem）

约瑟夫环的故事：古代有N个人围成一圈，从第1个人开始报数，数到M的人出局，下一个人重新从1开始，直到只剩最后一个人。这就是约瑟夫问题，用循环链表实现最自然。

核心思路（C++ 伪代码，但可运行）：

  • 构建一个单向循环链表，节点数N。
  • 设置当前指针cur指向第一个节点。
  • 当链表节点数大于1时：
    • 向前走M-1步（因为当前已经算报1）
    • 删除当前节点（出局）
    • 让cur指向被删节点的下一个
  • 最后剩下的节点就是答案。

下面是一个完整可运行的C++代码（基于上面的循环链表，但专门为约瑟夫环优化）：

#include <iostream>
using namespace std;

struct Node {
    int data;        // 存放编号（1~N）
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 构建N个人的循环链表（编号1~N），返回最后一个节点（方便后续操作）
Node* buildCircle(int N) {
    Node* head = new Node(1);    // 头节点编号1
    head->next = head;           // 先自循环
    Node* prev = head;           // 前驱指针
    for (int i = 2; i <= N; i++) {
        Node* newNode = new Node(i);
        newNode->next = head;    // 新节点指向头
        prev->next = newNode;    // 前驱指向新节点
        prev = newNode;          // 更新前驱
    }
    return prev;                 // 返回尾节点（其next指向头）
}

// 约瑟夫环：N个人，数到M出局，返回幸存者编号
int josephus(int N, int M) {
    Node* prev = buildCircle(N);        // prev指向尾节点
    Node* cur = prev->next;             // cur指向头节点（第一个人）
    while (cur->next != cur) {          // 只要不止一个节点
        // 走M-1步（当前已经算第1步）
        for (int i = 1; i < M; i++) {
            prev = cur;                 // 前驱更新
            cur = cur->next;            // 当前指针前进
        }
        // 删除cur节点（出局）
        prev->next = cur->next;
        cout << "出局：" << cur->data << endl;
        delete cur;
        cur = prev->next;               // 从出局的下一个人继续
    }
    int survivor = cur->data;
    delete cur;
    return survivor;
}

int main() {
    int N = 7, M = 3;
    cout << "约瑟夫环：N=" << N << ", M=" << M << endl;
    int winner = josephus(N, M);
    cout << "幸存者编号：" << winner << endl;
    return 0;
}

运行结果示例（N=7, M=3）：

出局：3
出局：6
出局：2
出局：7
出局：5
出局：1
幸存者编号：4

（提示：如果看不习惯这个构建方式，也可以先构建单向循环链表再操作。关键在于循环遍历和删除节点。）

对应 Python 实现（简洁版）

# 定义节点类
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def josephus(N, M):
    # 构建循环链表，返回头节点
    head = Node(1)
    head.next = head
    prev = head
    for i in range(2, N+1):
        new_node = Node(i)
        new_node.next = head
        prev.next = new_node
        prev = new_node
    # 现在prev是尾节点，cur从头开始
    cur = head
    while cur.next != cur:  # 多于一个节点
        for _ in range(M-1):
            prev = cur
            cur = cur.next
        # 删除cur
        prev.next = cur.next
        print(f"出局：{cur.data}")
        cur = cur.next
    print(f"幸存者：{cur.data}")
    return cur.data

josephus(7, 3)

四、双向链表 vs 循环链表 vs 数组：如何选择？

特性双向链表循环链表数组
内存占用每个节点多一个指针，较大同单向链表，多一个指针（如果双向）连续内存，无指针开销
随机访问需要遍历，O(n)需要遍历，O(n)O(1)
插入/删除已知位置时O(1)同单向链表O(1)可能需要移动元素O(n)
双向遍历支持支持（双向循环）支持（索引前后）
适用场景需要频繁双向移动、撤销/重做循环任务、约瑟夫环需要快速随机访问

生活类比：

  • 双向链表 → 电影播放器的进度条，可以前进后退。
  • 循环链表 → 食堂打饭的“轮转窗口”，每个人打完饭就轮到下一个，永远循环。
  • 数组 → 班级座位表，老师可以喊“第3排第4个同学”直接找到。

五、常见错误总结（再强调一遍）

  1. 指针迷路：在双向链表中插入或删除时，忘记同时更新prev和next，导致链表断了。
  2. 空指针访问：在遍历时，cur = cur->next后没有检查是否为空，就直接读cur->data，程序会崩溃。
  3. 未更新头指针：删除头节点后，忘记head = head->next；或者在头部插入后，忘记head = newNode。
  4. 循环链表的死循环：遍历条件写成了while(cur != NULL)，但循环链表永远不会有NULL，于是变成死循环。正确的写法是while(cur != head)或使用do...while。
  5. 内存泄漏：动态分配节点后，忘记delete（C++）或没有释放。Python虽然有垃圾回收，但最好显式断开引用。

六、总结与进阶指引

  • 双向链表：每个节点有前后指针，适合需要来回移动的场景，代价是内存多。
  • 循环链表：首尾相连，适合循环遍历，实现约瑟夫环、时间片轮转等。
  • 双向循环链表：同时拥有两者优点，但实现稍微复杂。
  • 学习路线：先完全掌握单向链表，再学双向，最后学循环。理解指针/引用的操作是基础。

如果你已经掌握了这些，可以继续学习：

  • 静态链表：用数组模拟链表，节省指针空间。
  • 链队列和链栈：用链表实现队列和栈，利用链表灵活扩展。
  • 跳表：一种可以快速查找的链表，类似多层索引。
  • LRU缓存：利用双向链表+哈希表实现最近最少使用淘汰策略。

数据结构的奥妙在于：选对结构，代码变简单。希望这篇文章能帮你轻松驾驭双向和循环链表！

例题精讲

1单选题

在双向链表中删除一个已知节点p（非头尾节点），需要修改几个指针指向？

A2个
B3个
C4个
D6个
2判断题

在带头节点的循环链表中，头指针head指向头节点，则判断链表为空的表达式是 head->next == head。

3填空题
以下代码实现双向链表在节点p之后插入新节点newNode，请填空：
newNode->prev = p;
newNode->next = ___;
if (p->next != NULL) {
    p->next->prev = newNode;
}
p->next = newNode;
4单选题

关于循环链表，以下说法正确的是？

A循环链表必须有一个头节点
B循环链表的尾节点next指针指向头节点
C循环链表只能实现单向遍历
D循环链表无法删除尾部节点
5判断题

在双向循环链表中，节点p满足 p->next == p->prev 时，p一定是唯一的节点（仅有一个实际数据节点）。