Acwing827. 双链表：深入解析与高效实现指南

一、双链表基础概念解析

双链表（Doubly Linked List）是一种线性数据结构，由一组节点通过指针连接而成。与单链表相比，双链表的每个节点不仅包含指向下一个节点的指针（next），还包含指向前一个节点的指针（prev）。这种双向连接特性使得双链表在插入、删除操作时具有更高的灵活性。

1.1 节点结构定义

双链表的核心是节点（Node）的定义。每个节点通常包含三个部分：

数据域（data）：存储节点的实际数据。
前驱指针（prev）：指向当前节点的前一个节点。
后继指针（next）：指向当前节点的后一个节点。

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

1.2 双链表与单链表的对比

特性	单链表	双链表
指针数量	1个（next）	2个（prev, next）
访问前驱节点	需从头遍历	直接通过prev指针访问
插入/删除	需维护next指针	需同时维护prev和next指针
空间开销	较小	较大（多一个指针）
适用场景	只需单向遍历的场景	需要双向遍历或频繁插入删除

二、Acwing827题目核心要求

Acwing827题目要求实现一个双链表，并支持以下操作：

在链表头部插入节点（L.addFirst(x)）
在链表尾部插入节点（L.addLast(x)）
在指定节点后插入新节点（L.insert(p, x)）
删除指定节点（L.erase(p)）
查找第k个节点（L.getK(k)）
查找前驱节点（L.getPrev(p)）
查找后继节点（L.getNext(p)）

三、双链表核心操作实现详解

3.1 初始化双链表

初始化时需创建头节点（head）和尾节点（tail），并设置它们的指针关系。

DNode *initList() {
    DNode *head = (DNode *)malloc(sizeof(DNode));
    DNode *tail = (DNode *)malloc(sizeof(DNode));
    head->next = tail;
    tail->prev = head;
    head->prev = NULL;
    tail->next = NULL;
    return head;
}

3.2 头部插入节点

在头部插入节点需修改头节点的next指针和新节点的prev指针。

void addFirst(DNode *head, int x) {
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

3.3 尾部插入节点

尾部插入需修改尾节点的前驱指针和新节点的next指针。

void addLast(DNode *head, int x) {
    DNode *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->prev = tail;
    node->next = NULL;
    tail->next = node;
}

优化：可维护一个尾指针（tail），避免每次遍历到链表尾部。

3.4 指定节点后插入

在节点p后插入新节点需修改p的next指针、新节点的prev和next指针，以及p后继节点的prev指针。

void insertAfter(DNode *p, int x) {
    if (p == NULL) return;
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->next = p->next;
    node->prev = p;
    if (p->next != NULL) {
        p->next->prev = node;
    }
    p->next = node;
}

3.5 删除指定节点

删除节点p需修改p前驱节点的next指针和p后继节点的prev指针。

void erase(DNode *head, DNode *p) {
    if (p == NULL || p == head) return;
    p->prev->next = p->next;
    if (p->next != NULL) {
        p->next->prev = p->prev;
    }
    free(p);
}

四、双链表应用场景与优化技巧

4.1 典型应用场景

LRU缓存：双链表可高效实现最近最少使用算法，头部为最新访问节点，尾部为最久未访问节点。
文本编辑器：支持光标前后移动和插入删除操作。
图算法：如拓扑排序中维护入度为0的节点。

4.2 性能优化技巧

虚拟头尾节点：避免处理空链表或边界条件的特殊逻辑。
迭代器模式：封装节点指针，提供安全的遍历接口。
内存池：预分配节点内存，减少频繁malloc/free的开销。

五、Acwing827题目实现示例

#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;
DNode *initList() {
    DNode *head = (DNode *)malloc(sizeof(DNode));
    DNode *tail = (DNode *)malloc(sizeof(DNode));
    head->next = tail;
    tail->prev = head;
    head->prev = NULL;
    tail->next = NULL;
    return head;
}
void addFirst(DNode *head, int x) {
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}
void addLast(DNode *head, int x) {
    DNode *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->prev = tail;
    node->next = NULL;
    tail->next = node;
}
void insertAfter(DNode *p, int x) {
    if (p == NULL) return;
    DNode *node = (DNode *)malloc(sizeof(DNode));
    node->data = x;
    node->next = p->next;
    node->prev = p;
    if (p->next != NULL) {
        p->next->prev = node;
    }
    p->next = node;
}
void erase(DNode *head, DNode *p) {
    if (p == NULL || p == head) return;
    p->prev->next = p->next;
    if (p->next != NULL) {
        p->next->prev = p->prev;
    }
    free(p);
}
int main() {
    DNode *L = initList();
    addFirst(L, 1);
    addFirst(L, 2);
    addLast(L, 3);
    DNode *p = L->next; // 第一个节点（2）
    insertAfter(p, 4);  // 在2后插入4
    erase(L, p);        // 删除节点2
    // 遍历链表
    DNode *cur = L->next;
    while (cur->next != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    return 0;
}

六、总结与建议

双链表通过维护双向指针，在插入、删除操作上比单链表更高效，但需付出额外的空间开销。在实际开发中，建议：

优先使用虚拟头尾节点简化边界条件处理。
对于频繁插入删除的场景，双链表是更优选择。
结合具体业务场景，选择是否需要实现完整的双链表功能。

通过掌握Acwing827题目中的双链表实现，开发者能够深入理解双向链表的核心机制，为解决更复杂的算法问题打下坚实基础。