数据结构：单链表(1)
目录
前言
最近学校事务较多，我又正巧经历社团换届，所以耽误了几天时间，但好在所有投入都有了温暖的回应，留任成功了（虽然是小社团哈），接下来，我将继续更新博客，与大家分享知识。
本篇文章将讲解单链表的知识，包括：单链表的概念，单链表的结构、实现单链表、链表的分类、单链表算法题知识的相关内容，为5大模块，其中为本章节知识的内容。
一.单链表的概念
介绍
在之前我们学习了逻辑结构和物理结构都是线性的顺序表，但是我们会发现顺序表有以下3个比较明显的缺陷：中间/头部的插入删除，时间复杂度为O(N)。增容需要申请新空间，拷贝数据，释放旧空间，有不小的消耗。增容一般呈两倍的增长，会有一定的空间浪费。
而链表可以很好的解决该问题：
首先，先介绍一下链表的基础知识：
链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，即：逻辑顺序通过指针链接 的线性数据结构它由多个节点组成，每个节点包含 数据域（存储具体值）和 指针域（存储下一个节点的地址），通过指针域建立节点间的逻辑关系，形成线性序列（如 A→B→C→NULL）。
例：
每个节点包含 数据域（存储具体值）和 指针域（存储下一个节点的地址）形象化来看：数据域方面用数字来表示，指针域方面用next，表示：
图中指针变量list保存的是第⼀个结点的地址，我们称list此时“指向”第⼀个结点，如果我们希望 list“指向”第⼆个结点时，只需要修改plist保存的内容为next即可，链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
结构上非连续，非顺序，但它的逻辑结构还是线性的。我们可以把链表想象成火车的一节节车厢链接在一起，只不过不是通过下标来访问节点了，是通过每个节点的地址来访问下一个节点。
所以，回到上文，链表刚好可以使头部插入与删除的时间复杂度为O(1)，不需要增容也不存在空间的浪费。提高使用的效率。
二.单链表的结构
介绍
简单来说：
单链表，链表是由一个一个节点组成的，它的节点由两个组成部分数据域：保存的数据。指针域：指针，存放的是下一个结点的地址。
根据前面的知识，我们可以得出链表的结构：
#include<stdio.h> typedef int type; typedef struct SListNode { type data; struct SListNode* next; } SListNode; 当然，数据域的内容并不唯一，你也可以写其他或很多的成员的。当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。 当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。
具体使用例子：
#include<stdio.h> #include<stdlib.h> typedef int type; typedef struct SListNode { type data; struct SListNode* next; } SListNode; int main() { SListNode* node1=(SListNode*)malloc(sizeof(SListNode)); SListNode* node2=(SListNode*)malloc(sizeof(SListNode)); SListNode* node3=(SListNode*)malloc(sizeof(SListNode)); SListNode* node4=(SListNode*)malloc(sizeof(SListNode)); node1->data=1; node1->next=node2; node2->data=2; node2->next=node3; node3->data=3; node3->next=node4; node4->data=4; node4->next=NULL; } 对于该链表，如果想打印的话，则需要先讲解一下链表的打印，而每一个链表的节点均为malloc所得的结果，需要将申请的空间释放掉：所以接下来也会讲解一下链表的销毁函数。
链表的打印
单链表的打印是遍历链表并输出节点数据的基础操作，函数原形为：
void SLTPrint(SListNode* h);
代码实现为：
void SLTPrint(SListNode* h) { if (h == NULL) { printf("链表为空,无值\n"); return; } SListNode* p = h; while (p) { printf("%d ", p->data); p = p->next; } }讲解：
核心逻辑解析
1. 空链表判断与处理作用：检查链表是否为空（头指针h为NULL时，链表无节点）。处理逻辑：若为空链表，打印提示信息链表为空,无值，并通过return终止函数（避免后续无效操作）。为什么要return？
若不终止，会继续执行后续的p = h和while (p)循环，但此时p为NULL，循环不会执行，虽无语法错误，但逻辑冗余，提前返回更高效。
2. 非空链表：遍历打印数据遍历逻辑：临时指针p：用于遍历链表，避免直接修改头指针h（保护原始链表结构）。循环条件while (p)：当p不为NULL时，持续访问节点（p指向NULL表示已到链表尾部）。打印数据：通过p->data获取当前节点的值，用空格分隔（%d）。
3.执行流程图解
开始
↓
判断 h 是否为 NULL？
├─ 是 → 打印"链表为空,无值" → 结束函数
└─ 否 → 定义 p = h
↓
while (p != NULL)：
├─ 打印 p->data
├─ p = p->next（移动到下一个节点）
└─ 重复循环，直到 p 为 NULL
↓
结束
。
链表的销毁
单链表销毁的核心目标是 释放所有节点占用的堆内存，避免内存泄漏。
函数原形为：
void SListDestroy(SListNode** h);
参数为二级指针的原因：
我们知道，函数调用过程中，简单来说，实参的值会被拷贝给形参，形参与实参本质上是两个独立的变量，函数内对形参的修改不会影响实参。
若要通过函数修改外部变量的值，必须传递该变量的 地址。对于指针变量 head，其地址就是 二级指针：
代码实现为：
void SListDestroy(SListNode** h) { if (*h == NULL) { printf("链表为空\n"); return; } SListNode* p = *h; while(p) { SListNode* q = p; p = p->next; free(q); } }讲解 核心知识：
变量p和q的分工：p：遍历指针，从*h（头节点）开始，逐步移动到NULL（链表尾）。q：临时指针，用于暂存当前要释放的节点（q = p），避免p移动后丢失当前节点地址。循环条件while (p)：当p不为NULL时，继续遍历（即还有节点未释放）。释放顺序：必须先通过p = p->next保存下一个节点地址，再free(q)，否则释放q后，p->next会变为无效地址（断链）。
根据上方的代码：
我们可以打印与销毁了
SLTPrint(node1); SListDestroy(&node1);结果：
三、实现单链表
接下来，我将对实现单链表的代码进行实现：
1.单链表的尾插
我们学习过顺序表的知识了，也清楚，尾插入的逻辑，只不过单链表的尾插，并没有扩容两倍的需要，基本都是随插随申请值。
我们链表使用是要通过头结点对后面节点进行访问的，你看图，可以明确得知有几个节点，节点的地址、值，但我们写代码时是看不到的，这是链表的“抽象性”与“内存不可见性” 问题——代码中无法直接“看到”链表的物理结构（如节点地址、实际节点数），只能通过头指针间接操作。
函数形式：
void SLTPushBack(SListNode** h, type x);
由参数可知，在实现单链表的尾插之前，我们要先申请新节点，而后续头插等接口的实现也会用上，所以将其写为函数。
结点的创建
函数形式：
SListNode* SLTBuyNode(type x)
实现代码为：
SListNode* SLTBuyNode(type x) { SListNode* p = (SListNode*)malloc(sizeof(SListNode)); if (p) { p->data = x; p->next = NULL; return p; } else { perror("malloc failed"); return NULL; } }该函数用于动态创建单链表节点，分配内存并初始化数据域和指针域。
接下来，我们来实现下链表的尾插入：
void SLTPushBack(SListNode** h, type x) { SListNode* p = SLTBuyNode(x); if (*h == NULL) { *h = p; } else { SListNode* pr = *h; while (pr->next) { pr = pr->next; } pr->next = p; } }注：参数1：SListNode** h（头节点指针的地址）必须传递二级指针：因为若链表为空（*h == NULL），需要修改头指针本身（而非头指针指向的内容），此时一级指针无法实现（值传递特性）。参数2：type x
函数中为什么用*h？因为h是二级指针，*h才是头指针本身。直接修改*h会改变原链表的头指针地址。
else的逻辑：pr从头部出发，通过pr = pr->next移动，直到pr->next == NULL（此时pr即为尾节点）。
以下图为例，链表的尾部插入，需要先遍历一遍已有的值，在pr->next == NULL为尾时停止遍历，
尾部之后插入新的值，时间复杂度O(N)。
2.单链表的头插
即为头部插入，与顺序表的整体向后移动一位不同，链表的实现较为简单，效率也高。
函数形式：
void SLTPushFront(SListNode** h, type x)
在单链表的头部插入新节点，新节点成为新的头节点，原链表（若存在）则链接到新节点之后。
实现
void SLTPushFront(SListNode** h, type x) { SListNode* newnode = SLTBuyNode(x); if (*h == NULL) { *h = newnode; } else { newnode->next = *h; *h = newnode; } }例：（*h不为空）情况：
创建新节点newnode（data=0，next=NULL）。newnode->next = *h：新节点的next指向原头节点，此时newnode -> 1 -> 2 -> 3-> 4 -> NULL。*h = newnode：头指针更新为newnode，链表变为0 -> 1 -> 2 -> 3 ->4 -> NULL。
属于直接操作，时间复杂度为O（1）；
3.单链表的尾删
删除单链表的最后一个节点，并释放其内存，需处理链表为空、一个节点、多个节点的不同场景。
函数：
void SLTPopBack(SListNode** h)
void SLTPopBack(SListNode** h) { if (*h == NULL) { return; } if ((*h)->next == NULL) { free(*h); *h = NULL; } else { SListNode* p = *h; SListNode* pr = *h; while (p->next) { pr = p; p = p->next; } free(p->next); pr->next = NULL; } }| 场景 | 处理流程 |
|---|---|
| 链表为空 | 直接返回，无操作。 |
| 单节点链表 | 释放头节点，*h = NULL（头指针置空）。 |
| 多节点链表 | 遍历找到尾节点 p 和前节点 pr，释放 p，pr->next = NULL。 |
首先是断言，链表不可以为空特别判断只有一个节点的情况，如果只有一个节点的话直接释放掉就好了找尾节点的同时找到尾节点的前一个节点，每次尾节点向前走之前，先让pr指向其原来的位置最后直接让pr->next=NULL，释放掉p就好了。
4.单链表的头删
单链表的头删是指删除链表的第一个节点，核心目标是 释放头节点内存 + 更新头指针，需处理空链表、单节点链表等边界情况。
void SLTPopFront(SListNode** h)
void SLTPopFront(SListNode** h) { if (*h == NULL) { return; } SListNode* p = (*h)->next; free(*h); *h = p; }讲解：
这里主要就是先定义一个中间变量记录头的下一个节点，再直接free掉头节点。最后让中间变量成为新的头节点就可以了。
接下来我将列出练习的代码，和示例：
代码
代码我分三个文件写的分别是 1.h 1.cpp main.cpp
1.h
#include<stdio.h> #include<stdlib.h> typedef int type; typedef struct SListNode { type data; struct SListNode* next; }SListNode; void SLTPrint(SListNode* h); void SListDestroy(SListNode** h); void SLTPushBack(SListNode** h, type x); void SLTPushFront(SListNode** h, type x); void SLTPopBack(SListNode** h); void SLTPopFront(SListNode** h); SListNode* SLTBuyNode(type x);1.cpp
#include"1.h" void SLTPrint(SListNode* h) { if (h == NULL) { printf("链表为空,无值\n"); return; } SListNode* p = h; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } void SListDestroy(SListNode** h) { if (*h == NULL) { printf("链表为空\n"); return; } SListNode* p = *h; while(p) { SListNode* q = p; p = p->next; free(q); } } SListNode* SLTBuyNode(type x) { SListNode* p = (SListNode*)malloc(sizeof(SListNode)); if (p) { p->data = x; p->next = NULL; return p; } else { perror("malloc failed"); return NULL; } } void SLTPushBack(SListNode** h, type x) { SListNode* p = SLTBuyNode(x); if (*h == NULL) { *h = p; } else { SListNode* pr = *h; while (pr->next) { pr = pr->next; } pr->next = p; } } void SLTPushFront(SListNode** h, type x) { SListNode* newnode = SLTBuyNode(x); if (*h == NULL) { *h = newnode; } else { newnode->next = *h; *h = newnode; } } void SLTPopBack(SListNode** h) { if (*h == NULL) { return; } if ((*h)->next == NULL) { free(*h); *h = NULL; } else { SListNode* p = *h; SListNode* pr = *h; while (p->next) { pr = p; p = p->next; } free(p); pr->next = NULL; } } void SLTPopFront(SListNode** h) { if (*h == NULL) { return; } SListNode* p = (*h)->next; free(*h); *h = p; } main.cpp
#include"1.h" void test() { SListNode* node1 = (SListNode*)malloc(sizeof(SListNode)); SListNode* node2 = (SListNode*)malloc(sizeof(SListNode)); SListNode* node3 = (SListNode*)malloc(sizeof(SListNode)); SListNode* node4 = (SListNode*)malloc(sizeof(SListNode)); node1->data = 1; node1->next = node2; node2->data = 2; node2->next = node3; node3->data = 3; node3->next = node4; node4->data = 4; node4->next = NULL; SLTPrint(node1); SListDestroy(&node1); } void test2() { SListNode* h=NULL; SLTPushBack(&h, 10); SLTPushBack(&h, 20); SLTPrint(h); SLTPushFront(&h, 30); SLTPushFront(&h, 40); SLTPrint(h); SLTPopBack(&h); SLTPrint(h); SLTPopFront(&h); SLTPrint(h); SListDestroy(&h); } int main() { test2(); } 结果为：
即
总结
以上就是今天要讲的内容，本篇文章涉及的知识点为：单链表的概念，单链表的结构、实现单链表等知识的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，接下来的内容我会很快更新。
