一、单链表：最基础也最灵活的数据结构

说实话，我做了这么多年嵌入式开发，单链表是我用得最多的数据结构之一。为什么？因为它够轻量、够灵活。你想想看，在资源受限的MCU上，数组动不动就要预分配一大块连续内存，而链表呢？用多少就申请多少，不浪费。

今天我们就来彻底搞懂单链表。我会从定义开始，一步步带你实现头插法、尾插法、遍历、插入和删除。这些都是我当年踩过坑、流过泪才总结出来的经验。

1.1 单链表的定义

单链表，说白了就是一组节点串在一起。每个节点里存两样东西：数据和指向下一个节点的指针。最后一个节点指向NULL，表示链表结束。

来看这个结构体定义：

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

这里我习惯用 LinkedList 来表示整个链表，其实它就是一个指向头节点的指针。嗯，这里要注意：头节点不是第一个数据节点。头节点是哨兵，它不存数据，只用来简化插入和删除操作。

核心概念：头节点（Head Node）是链表的入口，它本身不存储有效数据。第一个存储数据的节点叫首元节点。

我曾经在一个项目里，因为搞混了头节点和首元节点，导致整个链表的遍历逻辑全错了。调试了整整一个下午才找到问题。从那以后，我每次定义链表都会在注释里写清楚：head->next 才是第一个数据节点。

1.2 头插法与尾插法

创建链表有两种基本方法：头插法和尾插法。这两种方法各有各的适用场景，我分别说说。

头插法

头插法，就是把新节点插在头节点后面，成为新的第一个数据节点。说白了就是「后来者居上」——后插入的节点反而在前面。

void insertAtHead(LinkedList head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = data;
    newNode->next = head->next;  // 新节点指向原来的第一个节点
    head->next = newNode;        // 头节点指向新节点
}

你看，头插法的代码非常简洁，时间复杂度是O(1)。但有个问题：插入顺序和实际顺序是相反的。比如你依次插入1、2、3，遍历出来是3、2、1。

我的经验：头插法常用于需要逆序输出的场景。比如你要反转一个链表，用头插法重新构建一遍就行了，省时省力。

尾插法

尾插法就老实多了，新节点永远加在链表末尾。这样插入顺序和遍历顺序一致。

void insertAtTail(LinkedList head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;
    
    // 找到最后一个节点
    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

尾插法的时间复杂度是O(n)，因为每次都要遍历到末尾。如果频繁在尾部插入，我建议维护一个尾指针，这样就能降到O(1)。

避坑指南：我曾经在尾插法里忘记将新节点的next置为NULL，结果遍历时一直访问到非法内存，程序直接崩溃。记住：malloc出来的内存不会自动清零，一定要手动初始化！

1.3 单链表的遍历

遍历链表是最基本的操作。说白了就是从头节点开始，沿着next指针一路走到NULL。

void traverse(LinkedList head) {
    Node *p = head->next;  // 跳过头节点
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

这里有个细节：遍历时不要修改头指针。我见过有人直接用head去遍历，结果遍历完head指向了NULL，整个链表就丢了。正确的做法是用一个临时指针p来移动。

为什么会有人犯这种错？因为刚学的时候总觉得「指针嘛，不就是地址吗，用哪个不一样」。嗯，等你丢过一次数据就记住了。

1.4 单链表的插入与删除

插入和删除是链表的核心操作。相比数组，链表的插入和删除不需要移动大量元素，只需要修改指针指向就行。

指定位置插入

int insertAtIndex(LinkedList head, int index, int data) {
    Node *p = head;
    int i = 0;
    
    // 找到第 index-1 个节点
    while (p != NULL && i < index) {
        p = p->next;
        i++;
    }
    
    if (p == NULL || i != index) {
        printf("插入位置无效\n");
        return -1;
    }
    
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) return -1;
    
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return 0;
}

注意看：插入的关键是先连后断。先把新节点的next指向p的下一个节点，再把p的next指向新节点。顺序不能反，否则会丢失后续节点。

删除指定节点

int deleteAtIndex(LinkedList head, int index) {
    Node *p = head;
    int i = 0;
    
    // 找到第 index-1 个节点
    while (p->next != NULL && i < index) {
        p = p->next;
        i++;
    }
    
    if (p->next == NULL || i != index) {
        printf("删除位置无效\n");
        return -1;
    }
    
    Node *temp = p->next;    // 要删除的节点
    p->next = temp->next;    // 跳过该节点
    free(temp);              // 释放内存
    return 0;
}
重要提醒：删除节点后一定要free掉内存！我见过太多人只修改指针不释放内存，结果内存泄漏到系统崩溃。嵌入式环境内存本来就紧张，这种错误绝对不能犯。

1.5 知识体系总览

下面这张图总结了单链表的完整知识结构，你可以把它当作学习路线图：

单链表知识体系 单链表 结构体定义 头插法 / 尾插法 遍历操作 插入 / 删除 数据域 + 指针域 头节点 vs 首元节点 头插法：O(1) 尾插法：O(n) 临时指针移动 判空条件 先连后断原则 释放内存 核心：灵活的内存管理 + 指针操作

1.6 完整示例代码

最后，我把上面所有操作整合成一个完整的示例。你可以直接复制到你的开发环境里跑一下：

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

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

// 初始化链表（创建头节点）
LinkedList initList() {
    LinkedList head = (Node *)malloc(sizeof(Node));
    if (head == NULL) return NULL;
    head->next = NULL;
    return head;
}

// 头插法
void insertAtHead(LinkedList head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) return;
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

// 尾插法
void insertAtTail(LinkedList head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) return;
    newNode->data = data;
    newNode->next = NULL;
    
    Node *p = head;
    while (p->next != NULL) p = p->next;
    p->next = newNode;
}

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

// 指定位置插入
int insertAtIndex(LinkedList head, int index, int data) {
    Node *p = head;
    int i = 0;
    while (p != NULL && i < index) {
        p = p->next;
        i++;
    }
    if (p == NULL || i != index) return -1;
    
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) return -1;
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return 0;
}

// 删除指定位置
int deleteAtIndex(LinkedList head, int index) {
    Node *p = head;
    int i = 0;
    while (p->next != NULL && i < index) {
        p = p->next;
        i++;
    }
    if (p->next == NULL || i != index) return -1;
    
    Node *temp = p->next;
    p->next = temp->next;
    free(temp);
    return 0;
}

// 释放整个链表
void freeList(LinkedList head) {
    Node *p = head;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }
}

int main() {
    LinkedList list = initList();
    
    // 测试头插法
    insertAtHead(list, 10);
    insertAtHead(list, 20);
    insertAtHead(list, 30);
    printf("头插法结果：");
    traverse(list);  // 输出：30 20 10
    
    // 测试尾插法
    insertAtTail(list, 40);
    insertAtTail(list, 50);
    printf("尾插法后：");
    traverse(list);  // 输出：30 20 10 40 50
    
    // 测试插入
    insertAtIndex(list, 2, 99);
    printf("插入后：");
    traverse(list);  // 输出：30 20 99 10 40 50
    
    // 测试删除
    deleteAtIndex(list, 3);
    printf("删除后：");
    traverse(list);  // 输出：30 20 99 40 50
    
    // 释放内存
    freeList(list);
    return 0;
}
最后说一句：单链表是所有链表的基础。你把它搞透了，后面学双向链表、循环链表、甚至内核链表都会轻松很多。我当年就是先把单链表手写了十几遍，写到闭着眼睛都能写出来，后面学什么链表都不怕了。
公众号:蓝海资料掘金营，微信deep3321
← 上一章 📖 返回目录 下一章 →