C 语言链表

链表（linked list）是用指针实现动态数据结构最典型的例子，它像一个能随时长大缩小、还能在中间插队的数组。理解它需要指针、动态内存分配、结构体三样基本功，这几篇都铺垫好了。

链表 vs 数组

先把账算清。链表的优点：

• 可以从中间插入或删除元素，数组只能挪一大片。
• 不用提前定义大小，边吃边长。

链表的缺点：

• 没有随机访问，想拿第 n 个元素，必须从头一个一个数过去。
• 要动态分配内存、玩指针，代码复杂，内存泄漏和段错误的风险更高。
• 每个节点还要额外存一个指针，内存开销比数组大。

链表长什么样

链表是一串动态分配的节点：每个节点装一个值（DATA）和一个指针（NEXT），NEXT 永远指向列表里的下一个节点。最后一个节点的指针是 NULL。整个链表由一个头指针拿着，头指针也是 NULL 就代表空链表。

定义节点

注意节点里要指回自己这个类型，所以必须用 struct node 这种自我引用的写法：

typedef struct node {
    int val;             /* 节点存的值 */
    struct node * next;  /* 指向下一个节点 */
} node_t;

造第一个节点

node_t * head = NULL;                  /* 头指针，先空着 */
head = (node_t *)malloc(sizeof(node_t)); /* 开一块能装一个节点的内存 */
if (head == NULL) {                     /* 判空是规矩 */
    return 1;
}
head->val = 1;       /* 存值 */
head->next = NULL;   /* 后面还没节点 */

养成两个习惯：malloc 之后判 NULL，节点用完 free。

遍历打印：跟着 next 走

用一个 current 指针从 head 出发，一路顺着 next 走，走到 NULL 为止：

void print_list(node_t * head) {
    node_t * current = head;
    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;   /* 前进 */
    }
}

往尾部追加节点

先把 current 走到最后一个节点（next 是 NULL 那个），再接一个新的：

void push(node_t * head, int val) {
    node_t * current = head;
    while (current->next != NULL) {
        current = current->next;   /* 走到尾巴 */
    }
    current->next = (node_t *)malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

这段假设链表非空；空链表得先处理 head 本身。

往头部插入：改头指针，得用二级指针

往最前面插节点要改 head 本身，所以函数得拿 指向头指针的指针（二级指针），否则 head 在函数里改了也是白改：

void push_head(node_t ** head, int val) {
    node_t * new_node = (node_t *)malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = *head;   /* 新节点指向旧头 */
    *head = new_node;         /* 头指针指向新节点 */
}

三步走：开新节点 → 新节点的 next 指向旧头 → 头指针改成新节点。调用时传地址：push_head(&head, 0);

弹出头部：pop

反着来：记下第二个节点，free 掉头，再让 head 指向第二个：

int pop(node_t ** head) {
    if (*head == NULL) {
        return -1;             /* 空表没得弹 */
    }
    node_t * next_node = (*head)->next;
    int retval = (*head)->val;
    free(*head);
    *head = next_node;
    return retval;
}

删除指定位置的节点

核心思路：找到待删节点的前一个，让它跳过待删节点直连后一个。因为删节点要改前驱的 next，所以要往前看两个：

int remove_by_index(node_t ** head, int n) {
    if (n == 0) {
        return pop(head);          /* 删头就是 pop */
    }
    node_t * current = *head;
    for (int i = 0; i < n - 1; i++) {
        if (current->next == NULL) {
            return -1;             /* 越界 */
        }
        current = current->next;   /* 走到待删节点的前一个 */
    }
    if (current->next == NULL) {
        return -1;
    }
    node_t * temp = current->next;    /* 记住要删的 */
    int retval = temp->val;
    current->next = temp->next;       /* 前驱直接连后一个 */
    free(temp);                       /* 释放 */
    return retval;
}

算法四步：走到前驱 → 暂存待删节点 → 前驱的 next 指向待删节点的 next → 用暂存指针 free。边界情况（空表、越界、删头）都要照顾到。

链表最适合的场景

栈和队列是链表的主场，栈顶/队头操作天然就是"头部插入/弹出"。学到这里，试着写一个 remove_by_value：按值删除链表中第一个匹配的节点，记得用二级指针、判空、并处理好删的是头这种情况。