第11课：双向链表
进度 0/24
↔️
双向链表
前后都能走，双向通行更自由！
📖知识引入
🛤️双指针域
节点同时带prev和next，左手牵前驱右手牵后继
🔁双向遍历
既可从头走到尾，也能从尾走回头，单链表做不到
🎯O(1)删节点
给定位点，双向链表不用找前驱就能直接删，快人一步
⚖️代价
每个节点多存一个指针，内存开销更大，插入时要改的指针也更多
💡
C++ STL的list就是双向链表，掌握原理后再用它，知其然更知其所以然
🔍双向链表节点与插入
struct DNode {
int val;
DNode* prev; // 指向前驱
DNode* next; // 指向后继
};
// 在 p 之后插入 s（四个指针都要改）
DNode* s = new DNode{99, nullptr, nullptr};
s->next = p->next; // s 牵住后继
s->prev = p; // s 牵住前驱
if (p->next != nullptr)
p->next->prev = s; // 原后继回牵 s
p->next = s; // p 正式接上 s双向链表插入要改四个指针，画好图再动手不迷路
🎯小测验
第1题：双向链表每个节点有几个指针域？
第2题：双向链表相比单链表的优势是？
第3题：在p后插入s时，原后继节点需要执行的操作是？
📝本课知识点
- ✓双向链表=prev+next双指针
- ✓前后皆可走，删除不用找前驱
- ✓灵活的代价是更多内存
第11课完成！继续探索下一课吧 🚀