链表

← 返回 MOC | ← 主页

---

链表的核心思想是：结点在内存里不要求连续，每个结点除了存自己的数据，还要保存“下一个结点是谁”。

所以链表和数组最大的区别是：

• 数组依赖连续内存，支持按下标快速访问
• 链表不要求连续内存，更擅长在已知位置附近做插入和删除

单链表和双向链表

单链表的每个结点通常只有一个后继指针：

• data
• next

双向链表的每个结点通常有两个方向的指针：

• data
• next
• prev

双向链表的好处是：

• 不止能往后找，也能往前找
• 删除当前结点时，拿到结点本身就更容易把它摘下来

链表最关心的几件事

头结点

链表往往需要一个“入口”，也就是头指针或头结点，用来找到整条链。

插入

链表插入的本质不是搬家，而是改指针。

例如在两个结点中间插入一个新结点，核心就是：

• 新结点先指向后面那个结点
• 前面那个结点再改成指向新结点

删除

链表删除的本质也不是清空内存，而是把当前结点从指针关系里摘掉。

双向链表删除时，常见动作是：

• 前驱的 next 指向当前的后继
• 后继的 prev 指向当前的前驱

单链表代码示范

先看一个最基础的单链表示例。
这里不追求复杂功能，只演示链表最核心的几件事：

• 结点怎么定义
• 头插怎么做
• 尾插怎么做
• 遍历怎么做
• 删除怎么做

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node *next;
} Node;
 
Node *create_node(int value) {
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) {
        return NULL;
    }
 
    node->data = value;
    node->next = NULL;
    return node;
}
 
void push_front(Node **head, int value) {
    Node *node = create_node(value);
    if (node == NULL) {
        return;
    }
 
    node->next = *head;
    *head = node;
}
 
void push_back(Node **head, int value) {
    Node *node = create_node(value);
    if (node == NULL) {
        return;
    }
 
    if (*head == NULL) {
        *head = node;
        return;
    }
 
    Node *cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = node;
}
 
void print_list(const Node *head) {
    const Node *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
 
void delete_value(Node **head, int value) {
    Node *cur = *head;
    Node *prev = NULL;
 
    while (cur != NULL) {
        if (cur->data == value) {
            if (prev == NULL) {
                *head = cur->next;
            } else {
                prev->next = cur->next;
            }
            free(cur);
            return;
        }
        prev = cur;
        cur = cur->next;
    }
}
 
void free_list(Node **head) {
    Node *cur = *head;
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
    *head = NULL;
}
 
int main(void) {
    Node *head = NULL;
 
    push_front(&head, 2);
    push_front(&head, 1);
    push_back(&head, 3);
    push_back(&head, 4);
 
    print_list(head);   // 1 -> 2 -> 3 -> 4 -> NULL
 
    delete_value(&head, 3);
    print_list(head);   // 1 -> 2 -> 4 -> NULL
 
    free_list(&head);
    return 0;
}

这个例子里最值得看懂的点

结点定义

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

这里的意思是：

• data 用来存当前结点的数据
• next 用来存下一个结点的地址

头插

node->next = *head;
*head = node;

头插的本质是：

• 新结点先连上原来的头
• 再让头指针改为指向新结点

尾插

尾插要先一路找到最后一个结点，然后把它的 next 指向新结点。

所以单链表尾插的代价通常比头插大，因为要遍历。

删除

删除时要特别区分两种情况：

• 删除的是头结点
• 删除的是中间结点

所以代码里才需要 prev 和 cur 两个指针一起走。