深入浅出双链表

1. 为什么需要双链表？

在单链表中，每个节点只包含指向下一个节点的指针，因此我们只能单向遍历。如果我们需要访问某个节点的前驱节点，就必须从头开始重新遍历，时间复杂度为O(n)。这在某些场景下（如频繁的插入和删除操作）会带来性能瓶颈。双链表通过增加一个指向前驱节点的指针，完美解决了这个问题，使得向前、向后遍历都很容易，插入和删除操作也更加便捷。

2. 双链表的结构定义

双链表的每个节点包含三个部分：数据域（存储数据）、前驱指针域（prev）和后继指针域（next）。在C语言中，可以这样定义：

    typedef struct DNode {    int data;               // 数据域    struct DNode *prev;      // 指向前驱节点的指针    struct DNode *next;      // 指向后继节点的指针} DNode, *DLinkedList;  

3. 双链表的特点

• 双向性：可以从任一节点出发，向前或向后遍历整个链表。
• 插入/删除效率高：在已知节点位置的情况下，插入和删除操作只需修改相关指针，时间复杂度为O(1)。
• 空间开销略大：每个节点需要额外存储一个指针，比单链表多占用一些内存。

4. 双链表的基本操作（图解+代码）

4.1 初始化

通常我们创建一个头节点（不存储实际数据）来简化边界操作。初始化时，头节点的prev和next都指向自身，表示空链表。

    DLinkedList InitList() {    DNode head = (DNode)malloc(sizeof(DNode));    head->prev = head;    head->next = head;    return head;}  

4.2 插入节点（在指定节点p之后插入新节点s）

    void InsertAfter(DNode *p, int data) {    DNode s = (DNode)malloc(sizeof(DNode));    s->data = data;    s->prev = p;    s->next = p->next;    p->next->prev = s;    p->next = s;}  

4.3 删除节点（删除指定节点p的后继节点）

    void DeleteAfter(DNode *p) {    if(p->next == p) return;  // 空链表    DNode *q = p->next;    p->next = q->next;    q->next->prev = p;    free(q);}  

4.4 遍历链表

正向遍历：从head->next开始，直到回到head。反向遍历：从head->prev开始，直到回到head。

    // 正向打印void PrintList(DLinkedList L) {    DNode *p = L->next;    while(p != L) {        printf("%d ", p->data);        p = p->next;    }    printf("");}// 反向打印void PrintListReverse(DLinkedList L) {    DNode *p = L->prev;    while(p != L) {        printf("%d ", p->data);        p = p->prev;    }    printf("");}  

5. 总结

双链表是线性表的重要实现之一，它通过增加前驱指针，使得双向遍历和高效插入/删除成为可能。虽然牺牲了少量空间，但换来了操作的灵活性，在实际开发中（如LRU缓存、文本编辑器等）应用广泛。掌握双向链表是深入学习数据结构的必经之路。下一节我们将介绍循环链表，敬请期待！

（完）