4. 单链表基础：从节点定义到两种插入法

链表这东西，说实话，是我当年学C语言时第一个觉得「有点意思」的数据结构。数组太死板了，你想想看，声明的时候就得定好大小，多了不行少了浪费。链表就不一样，它像一串手拉手的小朋友，随时可以加人，随时可以退出。

今天咱们就聊聊单链表最基础的东西——节点长什么样、怎么创建、怎么遍历，以及两种最常用的插入方式：头插法和尾插法。

4.1 单链表的节点定义

单链表的每个节点，说白了就两个部分：数据域和指针域。数据域存你要放的东西，指针域存下一个节点的地址。

我习惯这样定义节点：

// 单链表节点定义
typedef struct Node {
    int data;           // 数据域，这里用int举例
    struct Node *next;  // 指针域，指向下一个节点
} Node;

这里有个细节要注意——struct Node *next 前面必须加 struct 关键字，因为 typedef 还没执行完，Node 这个别名还没生效。嗯，这个坑我当年踩过，编译报错半天没反应过来。

typedef struct Node {
    int data;
    struct Node *next;
} Node, *PNode;  // PNode 就是 Node* 的别名

4.2 创建链表与遍历

创建链表的第一步，是有一个头指针。头指针不存数据，它只是指向第一个有效节点。我个人习惯把头指针叫做 head，简单明了。

先看怎么创建一个空链表：

// 初始化空链表
Node* createList() {
    return NULL;  // 空链表，头指针指向NULL
}

然后我们往里面加节点。先写一个创建单个节点的函数：

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

遍历链表就更容易了，从头指针开始，一个一个往后走，直到碰到 NULL：

// 遍历链表并打印
void traverseList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

这里我多说一句：遍历时千万不要直接移动 head 指针。head 是链表的入口，丢了就找不回来了。我见过有人写 while(head != NULL) { head = head->next; }，遍历完 head 变成 NULL，整个链表就丢了。所以一定要用临时指针 p 来走。

4.3 头插法

头插法，就是把新节点插到链表的最前面。新节点成为新的第一个节点，原来的第一个节点变成第二个。

逻辑很简单：

// 头插法：在链表头部插入新节点
Node* insertAtHead(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;  // 新节点指向原来的头节点
    head = newNode;        // 更新头指针
    return head;
}

你想想看，头插法的特点是什么？插入顺序和最终顺序是相反的。如果你依次插入 1、2、3，最终链表是 3 -> 2 -> 1 -> NULL。我在项目中用头插法做过一个「最近访问记录」的功能，每次新访问的页面插到最前面，遍历时就是最新的在最前面，非常方便。

4.4 尾插法

尾插法，就是把新节点插到链表的末尾。新节点成为最后一个节点。

尾插法需要先找到链表的尾节点，然后把新节点接上去：

// 尾插法：在链表尾部插入新节点
Node* insertAtTail(Node* head, int data) {
    Node* newNode = createNode(data);
    
    if (head == NULL) {
        // 空链表，新节点就是第一个节点
        return newNode;
    }
    
    Node* p = head;
    while (p->next != NULL) {  // 找到最后一个节点
        p = p->next;
    }
    p->next = newNode;  // 尾节点指向新节点
    return head;
}

尾插法的特点是插入顺序和最终顺序一致。依次插入 1、2、3，链表就是 1 -> 2 -> 3 -> NULL。这个很符合直觉，大部分场景下我们用的都是尾插法。

4.5 头插法与尾插法对比

4.6 完整示例

把上面这些串起来，写个完整的 demo：

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) exit(1);
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

Node* insertAtHead(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

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

int main() {
    Node* head = NULL;
    
    // 测试头插法
    printf("头插法：\n");
    head = insertAtHead(head, 1);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 3);
    traverseList(head);  // 输出: 3 -> 2 -> 1 -> NULL
    
    // 重新测试尾插法
    head = NULL;
    printf("尾插法：\n");
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    head = insertAtTail(head, 3);
    traverseList(head);  // 输出: 1 -> 2 -> 3 -> NULL
    
    return 0;
}

4.7 知识体系总览

下面这张图把单链表的核心知识点串起来了，你可以对照着看：

这张图把单链表的三个核心模块串起来了：节点定义是基础，创建与遍历是操作手段，头插法和尾插法是两种典型的插入策略。搞懂了这些，单链表你就入门了。

公众号:蓝海资料掘金营，微信deep3321