链表(一)：链表的概念、单向链表的创建、遍历链表、插入节点

说实话，很多初学者学数据结构时，第一个被卡住的地方就是链表。数组多简单啊，连续内存、下标访问，为什么非要搞个链表出来？

我当年也有这个疑问。直到我在一个嵌入式项目里，需要在中间频繁插入数据，数组的 memmove 把我整得欲哭无泪。嗯，从那以后，我才真正理解了链表的价值。

1. 链表到底是什么？

链表，说白了就是一组节点，每个节点里存着数据，还存着下一个节点的地址。它们不一定是连续存放的，靠指针串在一起。

你想想看，数组就像一列固定座位的火车，每个座位挨着。链表呢？就像一群人手拉手站成一排，每个人只知道自己后面是谁。

单向链表是最简单的一种。每个节点只有一个 next 指针，只能从头往后走，不能回头。

2. 单向链表的节点结构

在 C 语言里，我们通常用结构体来定义节点。我个人习惯这样写：

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

这里有个细节：struct Node *next 必须写成 struct Node，因为 typedef 还没生效。嗯，这是 C 语言的老规矩了。

3. 创建链表——从无到有

创建链表，其实就是创建一个个节点，然后把它们串起来。我建议用头插法或尾插法，两种方式各有适用场景。

3.1 头插法

每次新节点都插在头部。这样最后得到的链表，顺序和插入顺序是相反的。

Node* createByHead(int arr[], int n) {
    Node *head = NULL;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点指向原来的头
        head = newNode;        // 更新头指针
    }
    return head;
}

3.2 尾插法

每次新节点插在尾部，保持原有顺序。需要维护一个尾指针 tail。

Node* createByTail(int arr[], int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

4. 遍历链表——怎么把数据拿出来？

遍历链表很简单，从头节点开始，沿着 next 指针一路走到 NULL 为止。

void traverse(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

这里有个坑：千万不要直接用 head 去遍历。如果你把 head 移动了，链表头就丢了。我建议用一个临时指针 p 来走。

5. 插入节点——链表的灵魂操作

插入节点是链表最核心的操作。相比数组，链表插入不需要移动大量数据，只需要改几个指针。

5.1 在头部插入

Node* insertAtHead(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = head;
    return newNode;  // 新节点成为头
}

5.2 在尾部插入

Node* insertAtTail(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    
    if (head == NULL) return newNode;
    
    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
    return head;
}

5.3 在指定位置插入

假设我们要在第 pos 个节点后面插入（pos 从 0 开始计数）：

Node* insertAtPos(Node *head, int pos, int value) {
    if (pos < 0) return head;
    
    if (pos == 0) {
        return insertAtHead(head, value);
    }
    
    Node *p = head;
    for (int i = 0; i < pos - 1 && p != NULL; i++) {
        p = p->next;
    }
    
    if (p == NULL) {
        printf("位置无效\n");
        return head;
    }
    
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = p->next;
    p->next = newNode;
    
    return head;
}

6. 知识体系图

下面这张图帮你理清本章的核心脉络：

7. 避坑指南

我做了这么多年 C 语言开发，链表相关的坑踩了不少。给你总结几个最常见的：

• 忘记分配内存：直接用 Node *p 就赋值，这是未定义行为。一定要 malloc。
• 忘记检查 NULL：遍历或插入时，如果链表为空，直接访问 head->data 会崩溃。
• 指针顺序搞反：插入时先连后断，删除时先保存后释放。顺序错了，链表就断了。
• 内存泄漏：删除节点后没有 free，或者程序退出前没有释放整个链表。

8. 总结一下

链表的核心就三件事：创建节点、连接节点、遍历节点。插入操作是链表的精髓，理解了「先连后断」这个原则，后面学双向链表、循环链表都会轻松很多。

嗯，这一章的内容就到这里。链表的概念和基本操作，你动手写一遍代码，比看十遍都管用。

---