GESP C++ 五级：双链表精讲

核心目标：理解双链表的逻辑结构与内存模型，掌握节点的定义、创建、遍历、插入、删除等基本操作，重点掌握指针操作的顺序与边界处理，能分析操作的时间复杂度，能解决双链表相关选择题与编程题。
双链表每个节点有两个指针——prev指向前驱，next指向后继；插入和删除时四条指针都要改，顺序不能乱；已知节点指针时插入删除 O(1)，代价是多一个指针的内存开销。

一、考纲定位

GESP 五级官方考纲第3条明确要求：“掌握链表的创建、插入、删除、遍历和反转操作，理解单链表、双链表、循环链表的区别”。

双链表在五级考试中的考查分布：

考点	重要程度	典型考法
节点结构体定义	★★★★★	代码填空、选择题
双链表与单链表/循环链表的区别		选择题高频
插入节点（四个指针的更新顺序）		代码填空、选择题
删除节点（非头尾节点的正确操作）		选择题高频
尾部追加节点	★★★★☆	代码填空
带哨兵节点的双链表初始化		选择题
双向遍历	★★★☆☆	编程题
复杂度分析	★★★★☆	判断题、选择题

二、双链表基本概念

1. 什么是双链表

双链表（Doubly Linked List）是一种链式数据结构，每个节点包含三个部分：

• 数据域（data） ：存放数据
• 前驱指针（prev） ：指向前一个节点
• 后继指针（next） ：指向下一个节点

相对于单链表，双链表的核心优势是支持双向遍历，在已知节点指针的情况下，插入和删除效率更高；代价是每个节点需要额外的空间存储 prev 指针。

2. 双链表 vs 单链表 vs 循环链表

对比项	单链表	双链表	循环链表
指针数量	1个（next）	2个（prev、next）	单/双链表首尾相连
遍历方向	只能从头到尾	双向遍历	环形遍历
删除已知节点	O(n)（需找前驱）	O(1)（直接通过prev）	取决于单/双
内存开销	最小	较大（多一个指针）	视具体实现
尾节点指针	nullptr		指向头节点

高频易错辨析：

在单链表中，若已知任意结点的指针，删除该结点通常需要知道其前驱结点，找前驱需要从头遍历，时间复杂度为 O(n)；而在双链表中，通过 prev 指针可以直接找到前驱，删除已知节点的时间复杂度为 O(1)。

循环双链表的尾节点的 next 指向头结点，而不是 nullptr，这是与普通双链表的关键区别。

3. 节点定义

struct DNode {
    int data;         // 数据域
    DNode* prev;      // 指向前一个节点
    DNode* next;      // 指向下一个节点

    // 构造函数（可选，方便初始化）
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

注意：双链表的节点比单链表多一个 prev 指针，定义时不能遗漏。

三、双链表的创建与遍历

1. 创建双链表（尾插法）

DNode* createDList(const vector<int>& vals) {
    DNode* head = nullptr;
    DNode* tail = nullptr;

    for (int val : vals) {
        DNode* newNode = new DNode(val);
        if (!head) {
            head = tail = newNode;    // 第一个节点
        } else {
            tail->next = newNode;      // 旧尾节点的next指向新节点
            newNode->prev = tail;      // 新节点的prev指向旧尾节点
            tail = newNode;            // 更新尾指针
        }
    }
    return head;
}

要点：创建过程中有两个关键操作——tail->next = newNode 和 newNode->prev = tail，两个都要写，缺一不可。

2. 双向遍历

// 正向遍历：从头到尾
void printForward(DNode* head) {
    DNode* p = head;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 反向遍历：从尾到头
void printBackward(DNode* tail) {
    DNode* p = tail;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->prev;
    }
    cout << endl;
}

双链表最核心的优势：可以从任意节点出发，向前或向后遍历。

四、双链表的插入操作（重点）

1. 在节点 p 之后插入节点 s

void insertAfter(DNode* p, DNode* s) {
    s->next = p->next;        // ① 新节点的next指向p的原后继
    if (p->next != nullptr) {
        p->next->prev = s;    // ② 原后继的prev指向新节点
    }
    s->prev = p;              // ③ 新节点的prev指向p
    p->next = s;              // ④ p的next指向新节点
}

四步操作：

步骤	操作	目的
①	s->next = p->next	新节点的后继指向p的原后继
②	p->next->prev = s	p的原后继的前驱指向新节点
③	s->prev = p	新节点的前驱指向p
④	p->next = s	p的后继指向新节点

2. 在节点 p 之前插入节点 s

void insertBefore(DNode* p, DNode* s) {
    s->next = p;              // ① 新节点的next指向p
    s->prev = p->prev;        // ② 新节点的prev指向p的原前驱
    if (p->prev != nullptr) {
        p->prev->next = s;    // ③ p的原前驱的next指向新节点
    }
    p->prev = s;              // ④ p的prev指向新节点
}

真题示例（2026年3月） ：

双向循环链表中要在结点p之前插入新结点s（均非空），以下指针操作正确的是（ ）。
A. s->next = p; p->prev = s; p->next = s; s->prev = p;
B. s->prev = p; s->next = p->next; p->next->prev = s; p->next = s;
C. s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
D. s->next = p; s->prev = nullptr; p->prev = s;
答案：C

解析：在双链表中结点p之前插入结点s，需要修改四个指针的方向且不能丢失原有的前驱结点引用。首先处理新结点s的两端：s->next = p; 以及 s->prev = p->prev;。接着修改原链表中的指针，必须先修改p的原前驱结点的后继：p->prev->next = s;，最后修改p的前驱指向新结点：p->prev = s;。

3. 在尾部追加节点

void append(int data) {
    DNode* newNode = new DNode(data);
    if (is_empty()) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    ++size;
}

真题示例（2025年6月） ：

填入相应代码完善 append()，用于在双向链表尾部增加新节点，横线上应填写（ ）。
A. tail->next = newNode;
B. newNode->prev = tail; tail = newNode;
C. tail = newNode; newNode->prev = tail; tail->next = newNode;
D. tail->next = newNode; newNode->prev = tail; tail = newNode;
答案：D

解析：D选项表示新节点的前指针指向尾节点，尾节点后指针指向新节点，新节点成为新的尾节点。

五、双链表的删除操作（重点）

1. 删除非头尾节点 p

void deleteNode(DNode* p) {
    p->prev->next = p->next;    // ① 前驱的后继指向p的后继
    p->next->prev = p->prev;    // ② 后继的前驱指向p的前驱
    delete p;                    // ③ 释放p
}

三步操作：

步骤	操作	目的
①	p->prev->next = p->next	前驱节点越过p，指向p的后继
②	p->next->prev = p->prev	后继节点越过p，指向p的前驱
③	delete p	释放p的内存

真题示例（2025年3月） ：

双向链表中每个结点有两个指针域 prev 和 next，设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点p，则下述语句中错误的是（ ）。

解析：双链表中删除非头尾结点p，需要将p的前驱结点和p的后继结点相连后释放p结点。p的前驱节点的next需要指向p的后继结点，p的后继结点的prev需要指向p的前驱结点。错误的选项通常是因为指针操作顺序导致信息丢失——先执行了 p->next->prev = p->prev;，之后再用 p->next 时它已经不是原来的值了。

2. 删除时的边界处理

void deleteNode(DNode* p) {
    if (p->prev != nullptr) {
        p->prev->next = p->next;    // 不是头节点
    } else {
        head = p->next;              // 删除的是头节点，更新头指针
    }
    if (p->next != nullptr) {
        p->next->prev = p->prev;    // 不是尾节点
    } else {
        tail = p->prev;              // 删除的是尾节点，更新尾指针
    }
    delete p;
}

六、带哨兵节点的双链表

1. 什么是哨兵节点

哨兵节点（哑结点）是不存储实际数据的虚拟节点，附加在链表头部或尾部，用于统一插入和删除的边界处理，避免对头节点和尾节点的特殊判断。

struct DLinkList {
    DNode* head;    // 头哨兵
    DNode* tail;    // 尾哨兵
    int size;

    DLinkList() {
        head = new DNode(0);
        tail = new DNode(0);
        head->next = tail;
        tail->prev = head;
        head->prev = nullptr;
        tail->next = nullptr;
        size = 0;
    }
};

2. 空的双向循环链表

真题示例（2025年3月） ：

假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next。下面代码实现一个空的双向循环链表，横线上应填的最佳代码是（ ）。

解析：双向循环链表中，头结点的 next 指针应指向尾结点，尾结点的 prev 指针应指向头结点。理论上，头结点的 prev 指针还要指向尾结点，尾结点的 next 指针指向头结点，以形成完整的循环。

3. 判断链表是否为空

bool is_empty() const {
    return head == nullptr;    // A选项，可填写
    // return tail == nullptr;  // B选项，可填写
    // return size == 0;        // D选项，可填写
    // return head.data == 0;   // C选项，不可填写
}

真题示例（2025年6月） ：横线处不能填写（ ）。答案：C。解析：A选项表示头节点为空指针，B选项表示尾节点为空指针，C选项表示头节点数据域为0，D选项表示链表大小为0。因此A、B、D选项都可填写，只有C选项不可填写。

七、复杂度分析

操作	单链表	双链表
遍历	O(n)
按值查找
已知节点后插入	O(1)
已知节点前插入	O(n)	O(1)
删除已知节点
尾部插入（有尾指针）	O(1)
空间复杂度	O(n)	O(n)（多一个指针域）

关键结论：双链表在已知节点指针的情况下，插入和删除都是 O(1)；单链表删除已知节点仍需 O(n) 找前驱。

八、双链表与单链表的核心区别（高频选择题）

真题示例（2026年3月） ：

关于单链表、双链表和循环链表，下列说法正确的是（ ）。
A. 在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点
B. 循环链表中一定不存在空指针
C. 在循环双链表中，尾结点的next指针一定为nullptr
D. 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身
答案：D

解析：A错误，单链表删除已知节点需要找前驱，O(n)；B错误，不带头结点的循环单链表为空时头指针即为空指针；C错误，循环双链表的尾节点 next 指向头结点，不是 nullptr；D正确。

九、易错点汇总

1. 插入时指针顺序错误：必须先处理新节点的两端，再修改原链表中的指针。如果先改 p->next，会丢失原来的后继节点引用。
2. 删除时指针顺序错误：先执行 p->next->prev = p->prev; 后，p->next 的值可能已经被改变，再用 p->next 就会出错。
3. 忘记处理头尾边界：删除头节点时要更新 head，删除尾节点时要更新 tail。
4. 插入时忘记判断 p->next != nullptr：在尾部节点之后插入时，p->next 为空，直接访问 p->next->prev 会崩溃。
5. 空链表初始化错误：带哨兵节点的双向循环链表，头哨兵的 next 指向尾哨兵，尾哨兵的 prev 指向头哨兵。
6. 混淆单双链表删除复杂度：单链表删除已知节点是 O(n)，双链表才是 O(1)。
7. 循环双链表尾节点 next 不为空：循环双链表的尾节点 next 指向头结点，不是 nullptr。
8. delete 后未置空指针：虽然考试不强制，但好习惯是 p = nullptr;。
9. 内存泄漏：删除节点后忘记 delete。
10. 遍历时忘记判空：while (p != nullptr) 不能漏。

十、速查表

需求	代码片段
节点定义	struct DNode { int data; DNode *prev, *next; };
创建（尾插）	tail->next=newNode; newNode->prev=tail; tail=newNode;
正向遍历	for (DNode* p=head; p; p=p->next)
反向遍历	for (DNode* p=tail; p; p=p->prev)
在p后插入s	s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
在p前插入s	s->next=p; s->prev=p->prev; p->prev->next=s; p->prev=s;
删除p	p->prev->next=p->next; p->next->prev=p->prev; delete p;
空双向循环链表	head->next=tail; tail->prev=head;
判断为空	return head == nullptr; 或 return size == 0;

十一、总结

双链表是 GESP 五级链表模块的核心内容，也是与单链表形成对比的重要考点。

1. 双链表每个节点有两个指针：prev 指向前驱，next 指向后继。
2. 双链表支持双向遍历，这是单链表做不到的。
3. 已知节点指针时，双链表的插入和删除都是 O(1)。
4. 插入时先处理新节点的两端，再修改原链表的指针，顺序不能乱。
5. 删除非头尾节点：p->prev->next=p->next; p->next->prev=p->prev; delete p;
6. 删除头节点要更新 head，删除尾节点要更新 tail。
7. 循环双链表的尾节点 next 指向头结点，不是 nullptr。
8. 单链表删除已知节点是 O(n)，双链表是 O(1)，这是高频选择题考点。
9. 带哨兵节点的双链表可以统一处理边界，简化插入删除。
10. 多练“在p前/后插入”“删除p”“哨兵初始化”三类代码填空题。

复习建议：先把双链表的节点定义、尾插法创建、双向遍历写熟；再重点突破插入和删除的指针操作顺序，手动画出每一步的指针变化；最后练习带哨兵节点的初始化和判断空链表的写法。考试中先看操作是在p之前还是之后插入，再看删除的是不是头尾节点，最后逐条检查四个指针是否都更新正确。