你有没有遇到过这种尴尬:往数组中间插一个元素,后面的元素全部要往后挪一格,删一个又要整体前移,数据一多程序肉眼可见地变卡。链表(linked list)就是为解决这个问题而生的——它让每个数据节点带着一个"指向下一个的指针",像项链一样把节点串起来,插入删除只需要改一两个指针,和节点个数无关。这篇文章我们从零开始,用 C 语言手写单链表和双向链表,把创建、插入、删除、遍历、释放内存全部跑通。

1. 数组的痛点与链表的设计思路

数组在内存里是一块连续空间,所以它天生有两个毛病:一是大小固定,想扩容只能重新申请一块更大的内存再整体拷贝;二是中间插入或删除元素时,后续元素必须整体移动,时间复杂度是 O(n)。链表完全不同:每个节点可以散落在内存的任意位置,节点之间靠指针联系。因为不需要移动数据,只要定位到目标位置,插入和删除就是 O(1)。

链表的基本单元叫节点(Node),它由两部分组成:一个存数据的字段,一个指向下一个节点的指针。最后一个节点的指针指向 NULL,表示"链子到头了"。动手之前先想清楚:C 语言里没有"对象",节点只能靠 malloc 在堆上申请,所以"用完要 free"这件事必须刻在脑子里——链表是内存泄漏的重灾区。

2. 节点的定义与创建

先定义节点结构体,再写一个创建节点的辅助函数。注意 next 指针的类型必须写成 struct Node *,因为 typedef 起的别名 Node 要等结构体定义结束才生效,在结构体内部还不能直接用。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;            /* 数据域 */
    struct Node *next;   /* 指针域:指向下一个节点 */
} Node;

Node *create_node(int value) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->next = NULL;
    return p;
}

两个关键点:第一,malloc 的返回值一定要检查,申请失败返回 NULL 时直接报错退出,比带着空指针继续跑安全得多;第二,新节点出生后要立刻把 next 置为 NULL,否则它是个悬空的野指针,后面遍历会读到垃圾地址。

3. 头插法与尾插法

链表最常用的两种添加方式:头插法把新节点插到最前面,新节点成为新的头;尾插法需要先走到链表末尾再接上去。因为头指针会变化,两个函数都返回新的头指针,调用时记得重新赋值。

Node *insert_head(Node *head, int value) {
    Node *p = create_node(value);
    p->next = head;      /* 新节点指向旧的头 */
    return p;            /* 新节点成为头 */
}

Node *insert_tail(Node *head, int value) {
    Node *p = create_node(value);
    if (head == NULL) {
        return p;        /* 空链表:新节点就是头 */
    }
    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next; /* 一路走到最后一个节点 */
    }
    cur->next = p;
    return head;
}

头插法的时间复杂度是 O(1),尾插法因为要遍历,是 O(n)——如果你经常在尾部追加,更专业的做法是额外维护一个 tail 指针,这就是后面双向链表和循环链表的雏形。注意 insert_head 里先让新节点指向旧头再更新头指针,顺序不能反。

4. 遍历、删除与内存释放

遍历就是"从头出发,顺着 next 一个个走",删除则要记住被删节点的前一个节点,把它的 next 跨过被删节点直接指向后面。释放整条链表时,先保存下一个节点再 free 当前节点,顺序错了就会丢链。

void print_list(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d -> ", cur->data);
    }
    printf("NULL\n");
}

Node *delete_value(Node *head, int value) {
    Node *prev = NULL;
    Node *cur = head;
    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) {
        return head;          /* 没找到,原样返回 */
    }
    if (prev == NULL) {
        head = cur->next;     /* 删除的是头节点 */
    } else {
        prev->next = cur->next;
    }
    free(cur);
    return head;
}

void free_list(Node *head) {
    while (head != NULL) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

删除逻辑里最容易漏的是"删头"这个分支:头节点没有前驱,必须单独更新 head。另外删除和 free_list 之后,记得把指针置 NULL 或让它们离开作用域,否则就是悬垂指针,二次使用会崩溃。

5. 一个完整的单链表程序

把前面的函数拼在一起,就是一个完整可运行的程序。把它存成 linkedlist.c,用 gcc linkedlist.c -o list 编译后运行,观察输出是否符合预期。

#include <stdio.h>
#include <stdlib.h>

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

Node *create_node(int value) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->next = NULL;
    return p;
}

Node *insert_head(Node *head, int value) {
    Node *p = create_node(value);
    p->next = head;
    return p;
}

Node *insert_tail(Node *head, int value) {
    Node *p = create_node(value);
    if (head == NULL) return p;
    Node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = p;
    return head;
}

void print_list(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

Node *delete_value(Node *head, int value) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return head;
    if (prev == NULL) head = cur->next;
    else prev->next = cur->next;
    free(cur);
    return head;
}

void free_list(Node *head) {
    while (head != NULL) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main(void) {
    Node *list = NULL;
    list = insert_head(list, 3);
    list = insert_head(list, 2);
    list = insert_tail(list, 4);
    list = insert_tail(list, 5);
    print_list(list);              /* 2 -> 3 -> 4 -> 5 -> NULL */
    list = delete_value(list, 3);
    print_list(list);              /* 2 -> 4 -> 5 -> NULL */
    free_list(list);
    return 0;
}

运行后第一行输出 2 -> 3 -> 4 -> 5 -> NULL,注意头插的顺序是反的——先插 3 再头插 2,所以 2 在最前面。删除 3 之后链表变成 2 -> 4 -> 5,中间节点被正确跨过。最后 free_list 把堆内存全部归还,配合 valgrind 检查可以确认没有泄漏。

6. 升级:双向链表

单链表只能向前走,想删某个节点必须从头找它的前驱。双向链表给每个节点多加一个 prev 指针,有了前驱,给定节点指针就能 O(1) 删除,这正是很多操作系统内核链表采用双向结构的原因。节点定义和头插法如下:

#include <stdio.h>
#include <stdlib.h>

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

DNode *dlist_insert_head(DNode *head, int value) {
    DNode *p = (DNode *)malloc(sizeof(DNode));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->prev = NULL;
    p->next = head;
    if (head != NULL) {
        head->prev = p;   /* 别忘改旧头的 prev */
    }
    return p;
}

头插时最容易漏的一步:把新节点接到头部后,要回头把旧头节点的 prev 指向新节点,否则链表从后往前走时会断。下面这个删除函数配合上面的 DNode 定义一起使用(同样需要 stdio.h 和 stdlib.h),它利用 prev 直接改前驱的 next,不再需要遍历找前驱:

DNode *dlist_delete(DNode *head, DNode *target) {
    if (target->prev != NULL) {
        target->prev->next = target->next;
    } else {
        head = target->next;   /* 删除的是头节点 */
    }
    if (target->next != NULL) {
        target->next->prev = target->prev;
    }
    free(target);
    return head;
}

双向链表删除的核心是"两条链都要接好":前驱的 next 指向后继,后继的 prev 指向前驱。边界情况同样是头节点(没有前驱)和尾节点(没有后继),分别单独处理。代价是每个节点多花一个指针的内存,以及插入删除时要维护的指针从 1 个变成 2 个,写错一个就断链。

7. 总结与练习

链表的价值在于:插入删除不移动数据,只改指针;缺点是失去随机访问能力,查找第 k 个元素要一个个走。单链表结构简单适合入门,双向链表用空间换来了 O(1) 删除。无论哪种,记住三件事:检查 malloc 返回值、边界情况(空表/删头/删尾)单独处理、用完 free 并防止悬垂指针。

练习建议:

💡 链表调试小技巧:画图!把节点画成方框、指针画成箭头,每次操作前先画出"现在长什么样",再画出"操作后应该长什么样",代码就是这两张图之间的翻译。