6、双向链表基础：双向链表的结构定义、创建与遍历

单向链表我们聊完了，今天来聊聊它的“升级版”——双向链表。

说实话，我刚学链表那会儿，觉得单向链表已经够用了。直到我在一个嵌入式项目里，需要频繁地反向遍历数据——用单向链表做这个操作，那叫一个痛苦。每次都得从头结点开始，一个一个往后找。后来我改成双向链表，代码量反而少了，性能也上去了。

嗯，这就是双向链表的魅力。

6.1 双向链表的结构定义

双向链表，说白了就是每个节点里多了一个指针，指向前一个节点。

单向链表只有一个 next 指针，指向后面。双向链表呢，多了一个 prev 指针，指向前面。这样一来，你既可以往前走，也可以往后走。

结构定义长这样：

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prev;     // 指向前一个节点
    struct DNode *next;     // 指向后一个节点
} DNode, *DLinkList;

你看，和单向链表比，就多了一个 prev 指针。但就是这个小小的指针，让很多操作变得简单了。

6.2 双向链表的创建

创建双向链表，我习惯用头插法。为什么？因为头插法代码写起来顺手，而且很多场景下我们需要频繁在头部插入数据。

来看代码：

DLinkList createDLinkList() {
    DLinkList head = (DLinkList)malloc(sizeof(DNode));
    if (head == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    head->prev = NULL;
    head->next = NULL;
    head->data = 0;  // 头结点数据域可以不用，这里随便给个值

    int value;
    printf("请输入节点值（输入-1结束）：");
    scanf("%d", &value);

    while (value != -1) {
        DNode *newNode = (DNode*)malloc(sizeof(DNode));
        if (newNode == NULL) {
            printf("内存分配失败\n");
            break;
        }
        newNode->data = value;

        // 头插法：新节点插入到头结点后面
        newNode->next = head->next;
        newNode->prev = head;
        if (head->next != NULL) {
            head->next->prev = newNode;
        }
        head->next = newNode;

        printf("请输入下一个值（输入-1结束）：");
        scanf("%d", &value);
    }

    return head;
}

6.3 双向链表的遍历

遍历双向链表有两种方式：正向遍历和反向遍历。

正向遍历：

void forwardTraverse(DLinkList head) {
    DNode *p = head->next;
    printf("正向遍历：");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

反向遍历：

void backwardTraverse(DLinkList head) {
    // 先找到最后一个节点
    DNode *p = head->next;
    if (p == NULL) {
        printf("链表为空\n");
        return;
    }
    while (p->next != NULL) {
        p = p->next;
    }

    printf("反向遍历：");
    while (p != head) {
        printf("%d ", p->data);
        p = p->prev;
    }
    printf("\n");
}

你看，反向遍历在单向链表里几乎不可能高效实现，但在双向链表里，就是几行代码的事。

6.4 双向链表 vs 单向链表

我整理了一个对比表，方便你直观理解：

对比项	单向链表	双向链表
节点结构	data + next	prev + data + next
内存占用	较小（每个节点少一个指针）	较大（每个节点多一个指针）
正向遍历	支持	支持
反向遍历	不支持（效率极低）	支持（高效）
删除节点	需要知道前驱节点	不需要，直接通过 prev 找到
插入节点	需要处理前驱的 next	需要处理前后两个节点的指针
代码复杂度	较低	稍高（多了一个指针要维护）

6.5 双向链表的核心逻辑图

下面这张图展示了双向链表的核心结构，以及正向、反向遍历的路径：

6.6 避坑指南

我做了这么多年嵌入式开发，用双向链表踩过的坑不少。这里分享几个典型的：

• 指针初始化：创建新节点时，一定要把 prev 和 next 都初始化为 NULL。我曾经漏掉一个，结果野指针导致系统崩溃。
• 删除节点时：记得把被删除节点的 prev 和 next 都置为 NULL，防止悬空指针。
• 头结点的处理：头结点的 prev 永远是 NULL，不要试图修改它。尾结点的 next 也永远是 NULL。
• 插入和删除的顺序：先处理新节点的指针，再处理前后节点的指针。这个顺序错了，链表就断了。

好了，双向链表的基础就聊到这里。代码你多写几遍，自然就熟了。

---