双链表的基本概念

双链表（Doubly Linked List）是一种线性数据结构，每个节点包含两个指针域，分别指向前驱节点（prev）和后继节点（next）。与单链表相比，双链表支持双向遍历，操作更灵活，但需要额外的空间存储前驱指针。

节点结构示例（C++实现）：

struct Node {
    int data;
    Node* prev;
    Node* next;
};

双链表的操作

插入操作

• 头部插入：新节点的next指向原头节点，原头节点的prev指向新节点，更新头指针。
• 尾部插入：遍历到尾节点，新节点的prev指向尾节点，尾节点的next指向新节点。
• 中间插入：在指定节点后插入，需调整前后节点的指针。

删除操作

• 若删除节点有前驱和后继，需分别更新前驱的next和后继的prev。
• 删除头节点或尾节点时需特殊处理边界条件。

代码示例（删除节点）：

void deleteNode(Node* node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    delete node;
}

双链表的优缺点

优点

• 双向遍历支持高效的前后操作，例如逆向遍历或删除特定节点。
• 某些算法（如LRU缓存）依赖双链表的快速插入/删除特性。

缺点

• 每个节点需额外存储前驱指针，空间开销较大。
• 指针维护复杂，容易引入错误。

实际应用场景

1. 浏览器历史记录：通过双链表实现前进/后退功能。
2. 文本编辑器：支持光标的双向移动和内容修改。
3. LRU缓存淘汰算法：结合哈希表实现O(1)复杂度的访问和删除。

双链表与单链表的对比

• 单链表：节省空间，但逆向操作需从头遍历。
• 双链表：空间换时间，适合频繁双向操作的场景。

性能对比表
| 操作 | 单链表 | 双链表 | |------------|--------|--------| | 插入/删除 | O(n) | O(1) | | 逆向遍历 | O(n) | O(1) | | 空间占用 | 较小 | 较大 |

实现注意事项

• 边界处理：头尾节点的操作需单独处理。
• 内存管理：动态分配节点时注意释放内存，避免泄漏。
• 循环链表：可扩展为双向循环链表，尾节点指向头节点形成闭环。

通过合理选择数据结构，双链表在需要高效双向操作的场景中具有显著优势。