单向链表基础：结构定义、创建节点、遍历与查找

链表这东西，说实话，是我当年从「只会写数组」到「开始理解动态内存」的一道分水岭。我记得第一次在项目里用链表，是为了做一个动态的任务队列——任务数量不确定，用数组要么浪费空间，要么不够用。链表正好解决了这个问题。

今天咱们就从头捋一遍单向链表最核心的几个操作。你想想看，链表说白了就是一堆节点串起来，每个节点知道自己下一个兄弟在哪。就这么简单。

单向链表的结构定义

先看结构体定义。每个节点包含两部分：数据域和指针域。数据域存实际数据，指针域指向下一个节点。

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

这里有个细节我当年踩过坑：struct Node *next 这个声明里，struct Node 必须完整写出来，不能写成 Node *next，因为此时 typedef 还没生效。嗯，C语言的语法就是这么「严谨」。

核心要点：

  • 数据域：可以是任意类型，int、char、结构体都行
  • 指针域：存放下一个节点的地址，最后一个节点指向 NULL
  • 头指针：指向第一个节点，是整个链表的入口

创建节点

创建节点就是向堆区申请一块内存，填上数据，把 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 返回值检查成了我的肌肉记忆。

个人习惯：创建节点后，我习惯先置 next 为 NULL，再赋值 data。顺序无所谓，但养成固定习惯能减少低级错误。

遍历链表

遍历链表，说白了就是从头节点开始，顺着 next 指针一路走到 NULL。代码很简单，但这里有个坑——千万不要修改头指针的值。

void traverseList(Node *head) {
    Node *current = head;   // 用临时指针，别动 head
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

你想想看，如果直接用 head 去遍历，遍历完 head 就变成 NULL 了，整个链表就丢了。所以我每次都用临时指针 current。

避坑指南：我曾经见过一个同事，在遍历时直接用 head = head->next，结果遍历完链表就找不到了。记住：头指针是链表的命根子，永远不要动它。

查找节点

查找节点和遍历很像，只不过多了个判断条件。找到就返回节点指针，找不到就返回 NULL。

Node* findNode(Node *head, int target) {
    Node *current = head;
    while (current != NULL) {
        if (current->data == target) {
            return current;   // 找到了
        }
        current = current->next;
    }
    return NULL;  // 没找到
}

这个函数的时间复杂度是 O(n)，因为最坏情况下要遍历整个链表。如果你需要频繁查找，可以考虑用哈希表或者跳表——不过那是后话了。

实际项目中的应用：我在一个传感器数据采集项目里，用链表存储历史数据，查找函数用来定位某个时间戳的数据。因为数据量不大（几百个节点），O(n) 完全够用。

知识体系结构图

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

单向链表核心操作 结构定义 typedef struct Node 创建节点 malloc + 初始化 遍历链表 while循环输出 查找节点 遍历 + 条件判断 核心原则：头指针不动，临时指针遍历 时间复杂度：创建 O(1) | 遍历 O(n) | 查找 O(n)

完整示例代码

把上面几个函数拼起来，就是一个完整的单向链表基础操作示例：

#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) return NULL;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

Node* findNode(Node *head, int target) {
    Node *current = head;
    while (current != NULL) {
        if (current->data == target)
            return current;
        current = current->next;
    }
    return NULL;
}

int main() {
    // 创建三个节点
    Node *head = createNode(10);
    Node *second = createNode(20);
    Node *third = createNode(30);
    
    // 链接起来
    head->next = second;
    second->next = third;
    
    // 遍历
    printf("链表内容：");
    traverseList(head);
    
    // 查找
    Node *found = findNode(head, 20);
    if (found != NULL)
        printf("找到节点：%d\n", found->data);
    else
        printf("未找到\n");
    
    // 释放内存（实际项目一定要做）
    free(head);
    free(second);
    free(third);
    
    return 0;
}

关于内存释放：示例里直接 free 了三个节点，实际项目中建议写一个 destroyList 函数，循环释放所有节点。我曾经因为忘记释放链表，导致程序跑几天后内存耗尽——嵌入式设备的内存可经不起这么折腾。

单向链表的基础操作就这些。结构定义是骨架，创建节点是血肉，遍历和查找是灵魂。把这四个操作吃透，后面的插入、删除、反转就水到渠成了。

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

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