数据结构入门：单链表详解（从原理到实战，新手必看）

在学习 C 语言数据结构时单链表是绕不开的基础核心。它弥补了数组在插入、删除操作时需要移动大量元素的缺陷是动态内存管理的经典实现。今天我们就从定义、结构到核心操作一步步拆解单链表。一、什么是单链表单链表是一种线性表的链式存储结构它通过指针将多个独立的节点串联起来每个节点包含数据域存储具体数据指针域存储下一个节点的地址和数组相比单链表的优势在于无需预先分配固定大小的内存可动态扩容插入 / 删除操作仅需修改指针时间复杂度为 O (1)已知位置时不需要连续的内存空间内存利用率更高二、单链表的节点结构定义在 C 语言中我们用结构体来定义单链表的节点同时用typedef简化类型名称方便后续操作// 单链表节点结构定义 typedef struct Node{ int data; // 数据域存储节点的数据 struct Node* next; // 指针域指向后继节点 }Node, *List; // Node等价于struct NodeList等价于Node*链表头指针类型三、单链表的核心操作下面我们实现单链表最常用的几个基础操作初始化、头插法创建、尾插法创建、遍历、插入、删除、查找。1. 初始化链表初始化一个空链表即让头指针指向NULL// 初始化链表 void InitList(List* L) { *L NULL; // 空链表头指针指向空 }2. 头插法创建链表将新节点插入到链表头部适合快速构建逆序链表// 头插法在链表头部插入新节点 List HeadInsert(List L, int val) { Node* newNode (Node*)malloc(sizeof(Node)); // 分配新节点内存 newNode-data val; newNode-next L; // 新节点指向原头节点 L newNode; // 头指针更新为新节点 return L; }3. 尾插法创建链表将新节点插入到链表尾部适合构建顺序链表// 尾插法在链表尾部插入新节点 List TailInsert(List L, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; if (L NULL) { // 空链表时新节点就是头节点 return newNode; } Node* p L; while (p-next ! NULL) { // 遍历到最后一个节点 p p-next; } p-next newNode; // 尾节点指向新节点 return L; }4. 遍历链表遍历并打印链表所有节点数据// 遍历链表 void TraverseList(List L) { Node* p L; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }5. 按位置插入节点在第pos个位置从 1 开始插入新节点// 在第pos个位置插入节点pos从1开始 List InsertByPos(List L, int pos, int val) { if (pos 1) { printf(插入位置非法\n); return L; } Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; if (pos 1) { // 插入到头部 newNode-next L; return newNode; } Node* p L; int i 1; while (p ! NULL i pos - 1) { // 找到第pos-1个节点 p p-next; i; } if (p NULL) { printf(插入位置超出链表长度\n); free(newNode); return L; } newNode-next p-next; p-next newNode; return L; }6. 按值删除节点删除第一个值为val的节点// 删除第一个值为val的节点 List DeleteByVal(List L, int val) { if (L NULL) { printf(链表为空无法删除\n); return NULL; } Node* p L; Node* pre NULL; // 找到要删除的节点 while (p ! NULL p-data ! val) { pre p; p p-next; } if (p NULL) { printf(未找到值为%d的节点\n, val); return L; } if (pre NULL) { // 删除的是头节点 L L-next; } else { // 删除的是中间或尾节点 pre-next p-next; } free(p); // 释放节点内存 return L; }7. 按值查找节点查找第一个值为val的节点返回其位置从 1 开始// 查找值为val的节点位置找不到返回0 int SearchByVal(List L, int val) { Node* p L; int pos 1; while (p ! NULL) { if (p-data val) { return pos; } p p-next; pos; } return 0; }四、单链表的优缺点总结优点缺点动态内存分配无需预先指定大小无法随机访问只能从头遍历查找时间复杂度 O (n)插入 / 删除操作仅需修改指针效率高每个节点需要额外存储指针内存开销略大不要求连续内存空间避免内存碎片实现比数组复杂需要手动管理内存