链表（上）：单向链表的定义、创建、遍历、插入与删除节点

各位同学，今天我们来聊聊链表。说实话，链表这东西，我当年刚学C语言的时候也觉得挺绕的。但后来在工作中，尤其是做嵌入式系统开发时，才发现它真的是个宝贝。数组虽然简单，但你要在中间插个数据，那叫一个麻烦——得把后面的元素全往后挪。链表就不一样了，它像一串手拉手的小朋友，想插队？改一下前后两个人的手就行了。

单向链表的结构定义

先看最基础的东西。单向链表，每个节点包含两部分：数据域和指针域。指针域指向下一个节点，最后一个节点指向NULL。

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

这里有个细节我提醒一下：struct Node *next 不能写成 Node *next，因为typedef还没生效呢。嗯，这个坑我踩过。

创建节点与链表

创建节点说白了就是malloc一块内存，填上数据，把next置NULL。我习惯写一个辅助函数：

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
注意：malloc之后一定要检查返回值！嵌入式环境内存有限，我曾经在一个项目中因为没检查malloc返回值，导致野指针问题，查了两天才定位到。别学我。

创建链表通常有两种方式：头插法和尾插法。头插法新节点总是插在头部，尾插法则保持原有顺序。我个人更常用尾插法，因为更符合直觉。

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

遍历链表

遍历很简单，从头节点开始，一路next到底。你想想看，这不就是顺着绳子摸瓜吗？

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

这里有个小技巧：遍历时不要直接用head指针移动，否则你就找不到链表头了。用个临时指针current来跑。

插入节点

插入分三种情况：头部插入、尾部插入、中间插入。中间插入最考验基本功，因为要处理前后两个指针。

// 在指定位置之后插入
int insertAfter(Node *prev, int data) {
    if (prev == NULL) return -1;
    Node *newNode = createNode(data);
    if (newNode == NULL) return -1;
    newNode->next = prev->next;
    prev->next = newNode;
    return 0;
}
我的习惯：插入操作一定要先连后断。先让新节点指向后面的节点，再让前面的节点指向新节点。顺序反了，后面的节点就丢了。

删除节点

删除比插入稍微麻烦一点，因为你要找到待删节点的前一个节点。单向链表只能往前走，不能回头，所以得用一个prev指针跟着。

int deleteNode(Node **head, int target) {
    if (*head == NULL) return -1;
    Node *current = *head;
    Node *prev = NULL;
    
    // 如果头节点就是要删除的
    if (current->data == target) {
        *head = current->next;
        free(current);
        return 0;
    }
    
    // 查找目标节点
    while (current != NULL && current->data != target) {
        prev = current;
        current = current->next;
    }
    
    if (current == NULL) return -1;  // 没找到
    
    prev->next = current->next;
    free(current);
    return 0;
}
重要：删除节点后一定要free释放内存！嵌入式系统内存宝贵，我曾经见过一个同事写了个循环删除，忘了free，跑了一周后系统内存耗尽直接死机。血的教训。

知识体系总览

下面这张图把单向链表的操作串起来了，你可以对照着看：

单向链表操作知识体系 单向链表 结构定义 创建链表 遍历链表 插入与删除 数据域 + 指针域 头插法 / 尾插法 while循环 + next指针 先连后断 / 释放内存 核心要点： 指针操作要谨慎 · 内存管理不能忘 · 边界条件多检查

常见错误与避坑指南

我总结几个新手最容易犯的错误，你写代码的时候多留个心眼：

  • 忘记初始化next指针——malloc出来的内存是脏的，不置NULL的话，遍历时会越界。
  • 插入时指针顺序搞反——先让新节点指后面，再让前面节点指新节点。顺序错了，后面的节点就找不到了。
  • 删除头节点时没更新head——如果你删的是头节点，记得把head指向下一个节点。
  • free之后继续使用——释放后记得把指针置NULL，否则就是野指针。

我的经验之谈：写链表操作时，我习惯先在纸上画图。把每个节点画成方框，箭头标清楚，再动手写代码。这样逻辑清晰，不容易出错。你试试看，真的管用。

好了，单向链表的基础操作就这些。说白了就是：定义结构、创建节点、遍历访问、插入删除。每个操作都不复杂，但组合起来就能解决很多实际问题。下一节我们会继续深入，看看双向链表和循环链表怎么玩。

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

← 上一章 📖 返回目录 下一章 →