13、动态链表的实现：单链表、双链表的内存管理、节点创建与销毁

动态链表，说白了就是「用指针串起来的一堆结构体」。

我刚开始学C语言时，总觉得数组够用了。直到有一次做嵌入式项目，需要动态管理传感器节点——今天接3个，明天拆2个，后天又加5个。数组？根本没法搞。链表才是正解。

这一章，咱们就聊聊单链表和双链表的内存管理。重点放在：节点怎么创建、怎么销毁、内存怎么才不会泄漏。

13.1 单链表：最简单的动态结构

单链表长什么样？每个节点里存一个数据，再加一个指向下一个节点的指针。最后一个节点指向NULL。

13.1.1 节点结构定义

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

嗯，这里要注意：struct Node *next 不能写成 Node *next，因为typedef还没生效。我见过不少新手在这栽跟头。

13.1.2 创建节点

创建节点，说白了就是malloc一块内存，填上数据，把next置NULL。

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

13.1.3 销毁节点

销毁节点就一个原则：free之前，先把它的next指针存下来。不然链表就断了。

void destroyList(Node *head) {
    Node *current = head;
    Node *next;
    while (current != NULL) {
        next = current->next;  // 先存下一个
        free(current);          // 再释放当前
        current = next;         // 移动到下一个
    }
}

13.2 双链表：能往前走也能往后走

双链表比单链表多一个prev指针。好处是：删除节点时不用找前驱，直接就能操作。代价是：每个节点多占一个指针的内存。

13.2.1 节点结构定义

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

双链表的头节点，prev指向NULL。尾节点的next指向NULL。这是规矩。

13.2.2 创建双链表节点

DNode* createDNode(int data) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

创建过程和单链表差不多。区别在于：插入时要同时维护prev和next两个指针。

13.2.3 销毁双链表

void destroyDList(DNode *head) {
    DNode *current = head;
    while (current != NULL) {
        DNode *next = current->next;
        free(current);
        current = next;
    }
}

销毁逻辑和单链表一样。因为双链表虽然多了一个prev，但销毁时只需要沿着next走就行。

13.3 插入与删除：内存管理的核心操作

插入和删除，说白了就是「改指针 + 管内存」。我总结了一个口诀：先接后断，先存后删。

13.3.1 单链表头部插入

void insertAtHead(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

这里用了二级指针。为什么？因为要修改头指针本身。我建议你养成用二级指针的习惯，不然函数里改了头指针，外面不知道。

13.3.2 单链表删除指定节点

void deleteNode(Node **head, int target) {
    if (*head == NULL) return;

    Node *current = *head;
    Node *prev = NULL;

    // 找目标节点
    while (current != NULL && current->data != target) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) return;  // 没找到

    if (prev == NULL) {
        // 删除的是头节点
        *head = current->next;
    } else {
        prev->next = current->next;
    }

    free(current);  // 释放内存
}

13.3.3 双链表尾部插入

void insertAtTail(DNode **head, int data) {
    DNode *newNode = createDNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    DNode *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

双链表插入时，一定要把prev和next都设置好。少设一个，遍历时就可能出问题。

13.4 内存管理要点总结

操作	单链表	双链表
节点大小	data + 1个指针	data + 2个指针
插入复杂度	O(1)（头插）/ O(n)（尾插）	O(1)（头插）/ O(n)（尾插）
删除复杂度	O(n)（需找前驱）	O(1)（已知节点指针）
内存开销	较小	较大（多一个prev）
遍历方向	单向	双向

选单链表还是双链表？我的经验是：如果删除操作多，而且经常需要反向遍历，用双链表。如果只是简单存数据、顺序访问，单链表就够了。

13.5 知识体系图

下面这张图，把单链表和双链表的核心操作串起来了。你一看就明白。

好了，单链表和双链表的内存管理就聊到这儿。记住三个核心：malloc检查、free不遗漏、指针不乱指。做到这三点，链表这块基本稳了。