C 语言链表

链表（linked list）是在指针、结构体与动态内存基础上构建的典型动态数据结构：元素分散在堆上的节点中，通过指针串联，长度可在运行时增长或缩短。

链表与数组的比较

链表的特点：

• 在已知前驱的前提下，可在中间插入或删除节点，不必移动其后全部元素。
• 节点按需分配，不必在编译期确定最大长度。

链表的代价：

• 不支持按下标随机访问，定位第 n 个元素通常需从头遍历。
• 需管理指针与 malloc/free，实现与调试复杂度高于数组。
• 每个节点除数据外还需存储指针，存在额外空间开销。

链表的结构

单向链表由若干节点组成：每个节点包含数据域与指向下一个节点的指针；最后一个节点的 next 为 NULL。空链表用头指针 head == NULL 表示。

节点类型定义

节点需包含指向同类型节点的指针，因此采用自引用结构体：

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;

动态分配后应检查返回值；不再使用的节点须 free。

遍历

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

在尾部追加节点

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。

在头部插入

修改头指针本身时，形参需使用指向指针的指针（参见按地址传参），否则函数内对局部副本的修改无法传回调用方：

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;
}

调用示例：push_head(&head, 0);

删除头节点

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);
    }
    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;
}

实现时须处理空表、下标越界以及删除头节点等边界情况。

典型应用

链表常用于实现栈、队列等抽象数据类型，其中在表头插入与删除的操作较为自然。可在此基础上练习按值删除第一个匹配节点，并注意头指针的更新与内存释放。

下一节介绍二叉树，在“每个节点多个分支”的结构上进一步使用指针与递归。