1. 链表的概念

链表（Linked List）是一种通过“指针”将多个节点连接起来的线性数据结构。

数据结构： 存放多个数据

每个节点通常包含：

• 数据域（data）
• 指针域（next），指向下一个节点

数组的节点：

• 数据域
• 下标

arr[0] = 10

链表不要求内存连续，节点可根据需要动态分配。

[ data | next ] → [ data | next ] → [ data | next ] → NULL

链表适用于频繁插入、删除的场景。

2. 单链表（Singly Linked List）

2.1 节点结构定义

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

2.2 头指针

链表通过一个指向首节点的“头指针”表示：

Node *head = NULL;

2.3 创建新节点

Node* create(int x) {
    Node *p = malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    return p;
}

3. 单链表基本操作

3.1 头插法（头部插入）

void push_front(Node **head, int x) {
    Node *p = create(x);
    p->next = *head;
    *head = p;
}

特点：

• 时间复杂度 O(1)
• 节点成为新的头

3.2 尾插法（尾部插入）

void push_back(Node **head, int x) {
    Node *p = create(x);
    if (*head == NULL) {
        *head = p;
        return;
    }
    Node *cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = p;
}

特点：

• 时间 O(n)（若无尾指针）

3.3 删除节点（按值删除）

void remove_value(Node **head, int x) {
    if (*head == NULL) return;

    if ((*head)->data == x) {
        Node *tmp = *head;
        *head = (*head)->next;
        free(tmp);
        return;
    }

    Node *cur = *head;
    while (cur->next && cur->next->data != x)
        cur = cur->next;

    if (cur->next) {
        Node *tmp = cur->next;
        cur->next = tmp->next;
        free(tmp);
    }
}

3.4 遍历链表

void print_list(Node *head) {
    for (Node *p = head; p; p = p->next) {
        printf("%d ", p->data);
    }
}

4. 单链表的内存模型

例如链表内容：3 → 5 → 7 → NULL

内存可能如下分布（非连续）：

地址3000: [3 | 5000]
地址5000: [5 | 9000]
地址9000: [7 | NULL]

链表通过 next 指针串联这些不连续的节点。

5. 双向链表（Doubly Linked List）

5.1 节点结构

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

5.2 优点

• 支持 O(1) 时间找到前驱节点
• 插入和删除更方便
• 可双向遍历

5.3 插入示例（在后面插入）

void insert_after(DNode *pos, int x) {
    DNode *p = malloc(sizeof(DNode));
    p->data = x;
    p->prev = pos;
    p->next = pos->next;
    if (pos->next) pos->next->prev = p;
    pos->next = p;
}

6. 循环链表（Circular Linked List）

6.1 概念

尾节点指向头节点：

[ data | next ] → [ data | next ] → [ data | next ]
       ↑                                  |
       └──────────────────────────────────┘

6.2 特点

• 任意节点可作为入口
• 常用于队列、约瑟夫环

6.3 判断循环

while (p->next != head)

7. 链表典型算法与题型

7.1 快慢指针判断链表是否有环

Node *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return 1;  // 有环
}
return 0; // 无环

7.2 反转链表（经典面试题）

Node* reverse(Node *head) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

7.3 删除倒数第 k 个节点

快慢指针法。

8. 链表的优势与劣势

优势

• 插入删除效率高（O(1)）
• 不需要连续内存
• 动态扩展方便

劣势

• 不支持随机访问
• 空间开销更大（需要指针）
• 局部性差（cache performance 较差）

9. 链表与数组对比

10. 链表常见错误与陷阱

1. 忘记更新 head 指针
2. 忘记处理空链表
3. free 后继续使用指针（悬空指针）
4. 删除节点时跳链
5. 双向链表忘记维护前驱指针

11. 综合示例：完整单链表程序

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

Node* create(int x) {
    Node *p = malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    return p;
}

void push_front(Node **head, int x) {
    Node *p = create(x);
    p->next = *head;
    *head = p;
}

void print(Node *head) {
    for (Node *cur = head; cur; cur = cur->next)
        printf("%d ", cur->data);
}

int main() {
    Node *head = NULL;
    push_front(&head, 3);
    push_front(&head, 5);
    push_front(&head, 7);

    print(head);  // 7 5 3
}