GESP5级C++考试语法知识（七、链表（二）双链表）

《双链表王国大冒险》课程目标✅ 完全理解双链表结构✅ 熟练写插入 / 删除✅ 明白它比单链表强在哪里✅ 能应对考试和竞赛题 第一章为什么需要双链表 故事单行道 vs 双向马路 单链表单行道1 → 2 → 3 → 4 只能往前走 想回头不行 双链表双向马路1 ⇄ 2 ⇄ 3 ⇄ 4 可以前进 也可以后退 第二章双链表结构看不同 每个节点长这样struct Node { int data; Node* prev; // 指向前一个 Node* next; // 指向后一个 }; 图解NULL ← 1 ⇄ 2 ⇄ 3 → NULL 每个节点有两个“指路牌” 第三章创建双链表 手动创建Node* a new Node{1, NULL, NULL}; Node* b new Node{2, NULL, NULL}; Node* c new Node{3, NULL, NULL}; // 连接 a-next b; b-prev a; b-next c; c-prev b; Node* head a; 第四章遍历双向优势 正向遍历Node* p head; while(p ! NULL) { cout p-data ; p p-next; } 反向遍历双链表独有Node* p tail; while(p ! NULL) { cout p-data ; p p-prev; } 单链表做不到这一点➕ 第五章插入操作 1️⃣ 头插法Node* insertHead(Node* head, int x) { Node* node new Node{x, NULL, head}; if(head ! NULL) head-prev node; return node; } 2️⃣ 在某节点后插入 在 p 后插入 xvoid insertAfter(Node* p, int x) { Node* node new Node{x, p, p-next}; if(p-next ! NULL) p-next-prev node; p-next node; } 插入口诀先连新节点 → 再改周围节点❌ 第六章删除操作超级重点 删除某个节点 pvoid deleteNode(Node* head, Node* p) { if(p NULL) return; // 如果是头节点 if(p head) head p-next; if(p-prev ! NULL) p-prev-next p-next; if(p-next ! NULL) p-next-prev p-prev; delete p; } 删除口诀必背断前 → 断后 → 释放 第七章双链表反转比单链表更简单 思路 把 prev 和 next 交换Node* reverse(Node* head) { Node* p head; Node* newHead NULL; while(p) { // 交换指针 Node* tmp p-next; p-next p-prev; p-prev tmp; newHead p; p tmp; } return newHead; } 第八章带头结点哨兵节点技巧 为什么用 避免特殊情况空链表 / 头节点 结构HEAD ⇄ 1 ⇄ 2 ⇄ 3 插入更简单void insert(Node* head, int x) { Node* node new Node{x, head, head-next}; if(head-next) head-next-prev node; head-next node; }⚔️ 第九章双链表 vs 单链表对比单链表双链表指针数1个2个能否回头❌✅删除操作麻烦简单内存占用少多使用场景普通LRU缓存 第十章经典应用——LRU缓存了解 浏览器“最近访问记录” 最近用的放前面 很久没用的删掉 双链表 哈希表 高级结构结构查找效率插入/删除效率顺序维护纯哈希表O(1)O(1)❌ 无序纯双链表O(n)O(1)已知位置✅ 有序哈希表 双链表O(1)O(1)✅ 有序 核心总结非常重要 双链表三大操作本质插入 改4条指针 删除 改2~4条指针 反转 交换prev和next 最强口诀考试必背双链表有两指针前驱后继都能寻 插入节点四步走新前后要连好 删除节点要小心前后断开再释放 反转链表很简单prev next互交换 学完我们应该能做到✅ 手写双链表结构✅ 正向 反向遍历✅ 任意位置插入✅ 删除任意节点✅ 反转链表✅ 理解为什么它比单链表强《双链表5道经典训练题含LRU简化版》 目标从“会写”到“会用”再到“会做竞赛题” 第1题正向 反向遍历基础1、 故事你是列车管理员不仅要从前往后检查还要倒着检查2、 图解NULL ← 1 ⇄ 2 ⇄ 3 → NULL3、 思路✔ 正向next✔ 反向prev4、 代码void printForward(Node* head) { Node* p head; while(p) { cout p-data ; p p-next; } } void printBackward(Node* tail) { Node* p tail; while(p) { cout p-data ; p p-prev; } } 第2题在指定位置插入进阶1、 故事新乘客要插到第 k 个位置 2、 思路 找第 k 个节点 p 插入在 p 前面3、代码Node* insertAt(Node* head, int k, int x) { Node* node new Node{x, NULL, NULL}; if(k 1) { node-next head; if(head) head-prev node; return node; } Node* p head; for(int i 1; i k-1 p; i) p p-next; if(p NULL) return head; node-next p-next; node-prev p; if(p-next) p-next-prev node; p-next node; return head; } 第3题删除第k个节点1、 故事第k个乘客要下车 2、 思路 找到第k个节点 修改前后指针3、代码Node* deleteK(Node* head, int k) { if(head NULL) return head; Node* p head; for(int i 1; i k p; i) p p-next; if(p NULL) return head; if(p head) head p-next; if(p-prev) p-prev-next p-next; if(p-next) p-next-prev p-prev; delete p; return head; } 第4题判断是否回文链表经典1、 故事火车从前看和从后看是不是一样1 2 3 2 1 ✅ 1 2 3 ❌2、 思路 双指针左指针head右指针tail3、代码bool isPalindrome(Node* head) { if(head NULL) return true; Node* tail head; while(tail-next) tail tail-next; Node* l head; Node* r tail; while(l ! r l-prev ! r) { if(l-data ! r-data) return false; l l-next; r r-prev; } return true; } 第5题LRU缓存进阶了解1、 故事 浏览器最近访问记录访问1 → 2 → 3 → 4 再访问 2变成2 → 4 → 3 → 1 最常用在前面2、 核心思想 双链表负责“顺序” 最新的放前面 删除尾巴最久没用3 简化规则不使用map✔ 访问如果存在 → 移到头如果不存在 → 插入头超容量 → 删除尾4、 核心代码struct Node { int data; Node* prev; Node* next; }; class LRU { public: Node* head; Node* tail; int cap; int size; LRU(int c) { head tail NULL; cap c; size 0; } // 删除节点 void remove(Node* p) { if(p head) head p-next; if(p tail) tail p-prev; if(p-prev) p-prev-next p-next; if(p-next) p-next-prev p-prev; } // 插到头 void insertHead(Node* p) { p-prev NULL; p-next head; if(head) head-prev p; head p; if(tail NULL) tail p; } // 访问 void access(int x) { Node* p head; // 查找 while(p p-data ! x) p p-next; if(p) // 存在 { remove(p); insertHead(p); } else { Node* node new Node{x, NULL, NULL}; insertHead(node); size; if(size cap) { Node* t tail; remove(t); delete t; size--; } } } }; 总结双链表考题特点 答题技巧1️⃣ 插入 改4条指针 2️⃣ 删除 改前后指针 3️⃣ 多用 head / tail 4️⃣ 回文 双指针 5️⃣ LRU 双链表核心应用了解 终极口诀背这个就稳了双链表双方向前驱后继都要连 插入节点四步走前后关系别搞乱 删除节点要小心前后断开再释放