安全初始化双向链表头节点应使用哨兵节点，即不存业务数据的固定头节点，其next和prev均初始化为自身，确保链表永不为空，避免空指针崩溃和重复判空。
如何安全初始化双向链表头节点
双向链表必须有明确的头尾标识，否则 insert、delete 会因空指针崩溃。常见错误是只声明 Node* head 却未赋初值，或误将 head = nullptr 当作“空链表”的完整状态——这会导致后续所有操作都要反复判空，极易漏掉边界。
推荐做法：用哨兵节点（sentinel node），即一个不存业务数据的固定头节点，其 next 指向第一个真实节点，prev 指向最后一个真实节点。这样链表永远非空，插入删除无需特判首尾。
struct Node {
int val;
Node* next;
Node* prev;
Node(int v) : val(v), next(this), prev(this) {} // 自环初始化
};
class DoublyLinkedList {
Node head; // 哨兵节点
public:
DoublyLinkedList() : head(new Node(0)) {}
~DoublyLinkedList() {
while (head->next != head) {
Node p = head->next;
head->next = p->next;
p->next->prev = head;
delete p;
}
delete head;
}
};
insert 时如何避免指针错位
双向链表插入的核心是「四连改」：新节点的 prev/next、前驱的 next、后继的 prev 必须全部正确指向。顺序错误（比如先改 prev 再改 next）可能让中间状态丢失连接，尤其在插入到头部/尾部时，容易把哨兵节点的 next 或 prev 指向自己。
- 插入到位置
pos（0-indexed）：先遍历到第pos个节点（即目标位置的前驱），再在其后插入 - 插入到头部：等价于在哨兵节点之后插入，即
head->next位置 - 插入到尾部：等价于在
head->prev之后插入（因为哨兵的prev永远指向尾节点）
void insert(int index, int val) {
Node* prevNode = head;
for (int i = 0; i < index && prevNode->next != head; ++i) {
prevNode = prevNode->next;
}
Node* newNode = new Node(val);
newNode->next = prevNode->next;
newNode->prev = prevNode;
prevNode->next->prev = newNode;
prevNode->next = newNode;
}delete 时为什么必须检查节点是否属于本链表
直接对传入的 Node* 调用 delete 很危险——它可能根本不在当前链表中，或已被释放过（double-free）。更隐蔽的问题是：若节点的 prev 或 next 指向非法内存，解引用时会段错误，而这个错误往往在 delete 后几行才暴露，难以定位。
立即学习“C++免费学习笔记（深入）”；
正确做法是：只根据值或索引删除，由链表内部遍历查找并校验指针关系；或者要求调用方传入「合法且归属本链表」的指针，并在 debug 模式下加断言：
assert(node != head && node->prev != nullptr && node->next != nullptr); assert(node->prev->next == node && node->next->prev == node);
生产环境建议放弃裸指针删除接口，统一用 removeAt(int index) 或 removeFirst(int val)。
find 和 update 的时间复杂度与缓存友好性
双向链表的 find 只能顺序遍历，O(n) 时间不可避免。但要注意：即使只是读操作，频繁访问也会导致 CPU 缓存失效——链表节点在堆上分散分配，next 指针跳转常引发 cache miss，实测比 vector 慢 5–10 倍。
update 本质是 find + modify，没有捷径。若需高频按值更新，应额外维护一个 std::unordered_map 做索引，但要同步处理插入/删除时的 map 更新，否则 map 中的悬垂指针会导致 crash。
真正需要双向链表的场景，几乎都集中在「频繁在任意位置增删 + 需要反向遍历」，比如 LRU 缓存的淘汰队列。如果只是偶尔删中间、多数操作在两端，用 std::deque 更稳妥；如果还要查得快，优先考虑哈希表+链表组合，而不是手写双向链表。
