双向链表
入门双向链表用额外指针换来更灵活的局部修改能力。
// 算法讲解
双向链表
这组示例会演示遍历、插入以及双向断链删除。
待机
速度 中
待机 ⌨1struct Node {
2 int value;
3 Node* prev;
4 Node* next;
5 Node(int v) : value(v), prev(nullptr), next(nullptr) {}
6};
7
8void remove(Node* node) {
9 if (node == nullptr) return;
10 if (node->prev) node->prev->next = node->next;
11 if (node->next) node->next->prev = node->prev;
12}
复杂度分析
时间 访问 O(n) / 已知节点删除 O(1)
空间 O(n)
最优 局部改链 O(1)
最坏 按位访问 O(n)
算法讲解
双向链表在单链表基础上增加 prev 指针，因此节点可以向前也可以向后移动。
当你已经拿到某个节点指针时，删除它只需要改动前后两个邻居，不必重新寻找前驱节点。
代价是每个节点要多存一个指针，代码里也必须同时维护两侧连接，漏改任一边都容易出错。
它常作为 LRU 缓存、编辑器历史记录和任务调度链表的基础容器。