📌 前言

在前面的文章中，我们学习了顺序表，它虽然支持随机访问，但在头部和中间插入删除时需要移动大量元素，效率较低。那么有没有一种数据结构可以解决这个问题呢？

链表（Linked List） 应运而生！它通过“指针”将零散的内存块串联起来，插入删除不需要移动元素，只需修改指针指向即可。

本文将带你从零实现一个单链表（Singly Linked List），包含：

  • ✅ 结点的定义与创建

  • ✅ 头插、头删、尾插、尾删

  • ✅ 任意位置插入/删除（前插/后插）

  • ✅ 查找、打印、销毁

  • ✅ 完整测试代码与运行结果

学完你将掌握：
 链表的底层存储结构
 二级指针的使用场景
 链表的增删改查操作
 顺序表与链表的差异与适用场景

一、单链表的基本概念

1.1 什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素之间的逻辑关系通过指针链接来实现。

通俗理解：
顺序表像一排连在一起的火车车厢（连续内存）；
链表像用绳子串起来的珠子（分散的内存，通过“绳子”即指针连接）。

1.2 单链表的结构

每个结点（Node）包含两部分：

  • 数据域：存储实际数据

  • 指针域：存储下一个结点的地址

typedef struct SListNode {
    SLTDataType data;          // 数据域
    struct SListNode* next;    // 指针域，指向下一个结点
} SLTNode;

结构示意图：

[data|next] -> [data|next] -> [data|next] -> NULL
  头结点                              尾结点

  • 头指针：指向第一个结点（链表入口）

  • 尾结点：指针域为 NULL

二、代码实现（逐模块讲解）

2.1 头文件 SList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义数据类型（方便切换）
typedef int SLTDataType;

// 定义结点结构
typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
} SLTNode;

// 接口函数声明
void SLTPrint(SLTNode* phead);                    // 打印链表
void SLTPushBack(SLTNode** pphead, SLTDataType x);  // 尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x); // 头插
void SLTPopBack(SLTNode** pphead);                  // 尾删
void SLTPopFront(SLTNode** pphead);                 // 头删

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);    // 查找

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);      // 在pos之前插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);                   // 在pos之后插入
void SLTErase(SLTNode** pphead, SLTNode* pos);                      // 删除pos结点
void SLTEraseAfter(SLTNode* pos);                                   // 删除pos之后的结点

void SListDestroy(SLTNode** pphead);                 // 销毁链表

⚠️ 为什么很多函数需要二级指针？
因为头插、尾删等操作可能修改头指针本身（比如链表为空时插入第一个结点，或者删除头结点）。
传递二级指针(SLTNode**)才能在函数内部修改外部的头指针。

本人也曾在此踩过坑，希望大家以此为戒。

三、核心函数实现

3.1 创建新结点（辅助函数）

SLTNode* SLTBuyNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

📌 malloc 失败时要检查返回值，并给出错误提示。

3.2 打印链表

void SLTPrint(SLTNode* phead) {
    SLTNode* pcur = phead;
    while (pcur) {
        printf("%d -> ", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

输出示例：1 -> 2 -> 3 -> 4 -> NULL

3.3 尾插（在链表末尾插入）

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);  // 确保二级指针不为空
    SLTNode* newnode = SLTBuyNode(x);
    
    // 情况1：链表为空，新结点直接成为头结点
    if (*pphead == NULL) {
        *pphead = newnode;
    } 
    // 情况2：链表非空，找到尾结点
    else {
        SLTNode* pcur = *pphead;
        while (pcur->next) {   // 找到最后一个结点
            pcur = pcur->next;
        }
        pcur->next = newnode;
    }
}

时间复杂度：O(n)（需要遍历找到尾结点）

3.4 头插（在链表头部插入）

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;   // 新结点指向原头结点
    *pphead = newnode;         // 头指针指向新结点
}

图解：

原链表：head -> [1] -> [2] -> NULL
头插0后：head -> [0] -> [1] -> [2] -> NULL

时间复杂度：O(1) ✅

3.5 尾删（删除最后一个结点）

void SLTPopBack(SLTNode** pphead) {
    assert(pphead && *pphead);  // 链表不能为空
    
    // 情况1：只有一个结点
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } 
    // 情况2：有多个结点
    else {
        SLTNode* prev = NULL;
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        prev->next = NULL;
        free(ptail);
    }
}

⚠️ 注意：需要记录尾结点的前一个结点，将其 next 置为 NULL。

3.6 头删（删除第一个结点）

void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

时间复杂度：O(1) ✅

3.7 查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x) {
            return pcur;   // 返回结点指针
        }
        pcur = pcur->next;
    }
    return NULL;   // 未找到返回NULL
}

3.8 在指定结点之前插入 

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    
    // 情况1：pos就是头结点 → 调用头插
    if (*pphead == pos) {
        SLTPushFront(pphead, x);
    } 
    // 情况2：pos不是头结点
    else {
        SLTNode* newnode = SLTBuyNode(x);
        SLTNode* prev = *pphead;
        while (prev->next != pos) {   // 找到pos的前驱
            prev = prev->next;
        }
        prev->next = newnode;
        newnode->next = pos;
    }
}

时间复杂度：O(n)（需要找到前驱结点）

3.9 在指定结点之后插入 

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

时间复杂度：O(1) ✅
优势：不需要遍历，效率高！

3.10 删除指定结点 

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos);
    
    // 情况1：pos是头结点 → 调用头删
    if (*pphead == pos) {
        SLTPopFront(pphead);
    } 
    // 情况2：pos不是头结点
    else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {   // 找到pos的前驱
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

3.11 删除指定结点之后的结点

c

void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->next);   // 确保pos和pos->next存在
    
    SLTNode* del = pos->next;
    pos->next = pos->next->next;
    free(del);
}

时间复杂度：O(1) ✅

3.12 销毁链表

c

void SListDestroy(SLTNode** pphead) {
    assert(pphead);
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;  // 先保存下一个结点
        free(pcur);                   // 释放当前结点
        pcur = next;                  // 移动到下一个
    }
    *pphead = NULL;   // 最后头指针置空
}

⚠️ 注意：一定要按顺序释放，避免丢失后续结点的地址。

四、完整测试代码及运行结果

4.1 测试程序（test.c）

#include "SList.h"

void test_tail_insert() {
    printf("====== 测试尾插 ======\n");
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);  // 1 -> 2 -> 3 -> 4 -> NULL
}

void test_front_insert() {
    printf("====== 测试头插 ======\n");
    SLTNode* plist = NULL;
    SLTPushFront(&plist, 1);
    SLTPushFront(&plist, 2);
    SLTPushFront(&plist, 3);
    SLTPushFront(&plist, 4);
    SLTPrint(plist);  // 4 -> 3 -> 2 -> 1 -> NULL
}

void test_tail_delete() {
    printf("====== 测试尾删 ======\n");
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);
    
    SLTPopBack(&plist); SLTPrint(plist);  // 1 -> 2 -> 3 -> NULL
    SLTPopBack(&plist); SLTPrint(plist);  // 1 -> 2 -> NULL
    SLTPopBack(&plist); SLTPrint(plist);  // 1 -> NULL
    SLTPopBack(&plist); SLTPrint(plist);  // NULL
}

void test_insert_before() {
    printf("====== 测试在结点之前插入 ======\n");
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);
    
    SLTNode* find = SLTFind(plist, 2);
    SLTInsert(&plist, find, 100);
    SLTPrint(plist);  // 1 -> 100 -> 2 -> 3 -> 4 -> NULL
}

void test_insert_after() {
    printf("====== 测试在结点之后插入 ======\n");
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);
    
    SLTNode* find = SLTFind(plist, 2);
    SLTInsertAfter(find, 100);
    SLTPrint(plist);  // 1 -> 2 -> 100 -> 3 -> 4 -> NULL
}

int main() {
    test_tail_insert();
    test_front_insert();
    test_tail_delete();
    test_insert_before();
    test_insert_after();
    return 0;
}

4.2 运行结果

====== 测试尾插 ======
1 -> 2 -> 3 -> 4 -> NULL

====== 测试头插 ======
4 -> 3 -> 2 -> 1 -> NULL

====== 测试尾删 ======
1 -> 2 -> 3 -> 4 -> NULL
1 -> 2 -> 3 -> NULL
1 -> 2 -> NULL
1 -> NULL
NULL

====== 测试在结点之前插入 ======
1 -> 2 -> 3 -> 4 -> NULL
1 -> 100 -> 2 -> 3 -> 4 -> NULL

====== 测试在结点之后插入 ======
1 -> 2 -> 3 -> 4 -> NULL
1 -> 2 -> 100 -> 3 -> 4 -> NULL

五、复杂度分析汇总

操作时间复杂度说明
头插O(1) ✅直接修改头指针
头删O(1) ✅直接修改头指针
尾插O(n)需要遍历找到尾结点（可优化为尾指针）
尾删O(n)需要遍历找到尾结点及其前驱
在pos之后插入O(1) ✅直接修改指针
在pos之前插入O(n)需要遍历找到pos的前驱
删除pos之后的结点O(1) ✅直接修改指针
删除pos结点O(n)需要遍历找到pos的前驱
查找O(n)可能需要遍历整个链表
销毁O(n)需要遍历释放所有结点

六、顺序表 vs 单链表

对比维度顺序表单链表
存储空间连续内存分散内存（不连续）
随机访问O(1) ✅O(n)
头插/头删O(n)O(1) ✅
中间插入/删除O(n)O(1)（如果已定位到位置）
空间利用率可能有空间浪费（扩容策略）每个结点有指针开销
缓存友好性好（连续内存）差（指针跳跃）
适用场景频繁随机访问、增删少频繁增删、随机访问少

选择建议：

  • 需要频繁随机访问 → 选顺序表

  • 需要频繁头插/头删/中间插入 → 选链表

七、常见问题与优化建议

7.1 为什么尾插效率低？

每次尾插都要遍历找到尾结点，时间复杂度 O(n)。
优化方案：增加一个尾指针，但需要维护多个指针，实现更复杂。

7.2 二级指针的困惑

很多初学者不理解为什么要有 SLTNode**：

// 错误写法（一级指针）
void wrong_push_front(SLTNode* phead, int x) {
    SLTNode* newnode = buy_node(x);
    newnode->next = phead;
    phead = newnode;  // ❌ 只修改了形参，不影响外部
}

// 正确写法（二级指针）
void right_push_front(SLTNode** pphead, int x) {
    SLTNode* newnode = buy_node(x);
    newnode->next = *pphead;
    *pphead = newnode;  // ✅ 修改了外部的头指针
}

函数传值：

传值：形参是实参的值的拷贝。

传地址：形参的改变影响实参。

记忆口诀：要修改谁，就传谁的地址。

7.3 内存泄漏问题

每次 malloc 后，最终都要 free，否则会导致内存泄漏。
我们的 SListDestroy 函数已经做了彻底清理。

八、总结

通过本文，我们学习了：

  • ✅ 单链表的结点结构（数据域 + 指针域）

  • ✅ 完整的增删改查操作（头尾插删、任意位置插删）

  • ✅ 二级指针的使用场景（需要修改头指针时）

  • ✅ 时间复杂度分析，理解链表的性能特点

  • ✅ 与顺序表的对比，知道各自适用场景

链表是后续学习双向链表、循环链表、栈、队列的基础，掌握好单链表，后面的数据结构会越学越轻松！如果你有任何疑问或改进想法，欢迎在评论区留言讨论！

最后！如果这篇博客对你有帮助，欢迎 点赞、收藏、评论 三连！后续会持续更新 链表、栈、队列、树 等数据结构教程，敬请关注～

# 数据结构 # c语言 # 开发语言 # 链表
Logo
乐奇 Rokid 开放社区

更多推荐

cover

使用Rokid AIUI做了一个童年推箱子游戏

avatar 乐奇 Rokid 开放社区

基于 AIUI 框架的眼镜端坐姿监测智能体：WorkerMonitor 设计与实现

基于AIUI框架，设计并实现眼镜端坐姿监测智能体WorkerMonitor。通过加速度传感器实时采集头部姿态数据，结合校准偏移量进行三态分类（正常/警示/异常），每秒采样一次，累计时长并低打扰提醒。每2小时调用LLM生成个性化健康建议，支持自动工作/休息切换与隐藏模式，兼顾隐私与体验。项目采用Ink单文件页面结构，实现极简交互与可持续反馈，为长期伏案者提供无感式颈椎健康管理方案。

avatar 乐奇 Rokid 开放社区

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精

avatar 乐奇 Rokid 开放社区