链表基础
链表是线性表的一种,表中的数据不必按顺序存储,而是在每一个节点里面存储下一个节点指针的数据结构。即物理位置非连续,逻辑位置连续。

由于物理位置非连续,无法通过寻常指针由第一个值直接到达第二个值,所以在单向链表的定义中,需要一个数据值和指针值,将一个个元素串起来。

本文介绍单向链表的基础概念与 C 语言实现。涵盖节点定义、链表创建与销毁、尾部/中间/头部插入、节点查找及遍历打印。重点解析指针操作细节,如插入时后继节点的保存顺序、销毁时的内存释放流程,以及避免野指针的关键点。最后提供双向链表与循环链表的概念扩展及完整可运行代码示例。
链表是线性表的一种,表中的数据不必按顺序存储,而是在每一个节点里面存储下一个节点指针的数据结构。即物理位置非连续,逻辑位置连续。

由于物理位置非连续,无法通过寻常指针由第一个值直接到达第二个值,所以在单向链表的定义中,需要一个数据值和指针值,将一个个元素串起来。


确定完节点类型之后就可以定义单向链表了。
为什么要使用 typedef?
如果不用 typedef,后续定义这个结构体的变量时,必须写完整的 struct Mynode:
// 不用 typedef 的写法(繁琐)
struct Mynode node1;
用了 typedef + NODE 之后,代码可以简化:
// 用 typedef 后的写法(简洁)
NODE node1;
对于链表的基本操作,我们需要明确以下几点:


先明确:这段代码的目标是彻底销毁链表。 需要做两件事:
NODE);LL类型的变量),并将其置空。代码里的 (*pList)->pHead 是链表的头节点指针,while 循环的逻辑是逐个释放节点:
while ((*pList)->pHead) // 只要头节点不为空,就继续销毁 {
pTemp = (*pList)->pHead; // 1. 先用 pTemp 保存'当前头节点'
(*pList)->pHead = (*pList)->pHead->pNext; // 2. 把'头节点指针'往后移
free(pTemp); // 3. 释放刚才保存的'原头节点'
}
free 再移动头指针),会导致'释放后再访问节点的 pNext',触发野指针错误;free(*pList); // 释放链表的管理结构体(LL 类型)
*pList = NULL; // 把链表指针置空,避免野指针
pTemp和'当前节点'指向的是同一块内存,所以 free(pTemp) 本质是释放'这块内存'。
用'门牌号'的类比讲透:
(*pList)->pHead、pTemp),相当于'房子的门牌号',存的是房子的地址;pTemp = (*pList)->pHead 时,相当于'把当前头节点(房子)的门牌号,复制了一份给 pTemp'——此时 pTemp 和 (*pList)->pHead 拿着同一个门牌号(指向同一块内存)。而 free(指针) 的逻辑是:根据指针里存的'门牌号',找到对应的'房子',把房子拆掉(释放内存)。所以不管用哪个指针(pTemp 还是 (*pList)->pHead)调用 free,只要它存的是'当前节点的地址',都会释放这个节点对应的内存。
至于这里的二阶指针 LL** pList,它的作用是让函数能修改外部传入的链表指针(比如最后 *pList = NULL),和'释放节点'本身没有关系。


有下标的插入:




想理解链表中间插入时节点连接的顺序问题,以及节点之间的变迁逻辑,这是链表操作的核心难点。我们先明确关键角色,再通过'错误顺序的坑'和'正确顺序的变迁'两步讲清楚,最后用形象比喻辅助理解。
在中间插入场景中,有 3 个关键节点(先固定它们的定义,避免混淆):
temp2:前驱节点(插入位置的前一个节点,已经在链表中存在)temp:新节点(我们要插入的节点,刚创建好,还未加入链表)后继节点:temp2->pnext(插入位置的后一个节点,原本跟在 temp2 后面,是链表的一部分)初始状态(插入前)的节点关系:temp2 → 后继节点(temp 独立在链表外)。我们的目标:temp2 → temp → 后继节点(形成完整链路,不丢失任何节点)。
如果先执行 temp2->pnext = temp,再执行 temp->pnext = temp2->pnext,会直接破坏链路,形成环。
temp2->pnext = temptemp2 的'下一个节点'从'原本的后继节点'改成 temp。temp2→后继节点 的链路被切断;② 现在 temp2→temp;③ 关键问题:原本的'后继节点'彻底丢失了!因为没有任何指针指向它了,我们再也找不到这个节点的位置。temp->pnext = temp2->pnexttemp 的'下一个节点'赋值为 temp2->pnext(此时 temp2->pnext 已经是 temp)。temp→temp(temp 的 next 指向它自己),形成闭环(链表成环)。最终结果:链表链路变成 temp2→temp→temp→temp... 无限循环,原本的后继节点丢失,链表结构彻底损坏。
正确顺序是:先执行 temp->pnext = temp2->pnext,再执行 temp2->pnext = temp,核心目的是'先保存后继节点,再修改前驱节点的指向'。
temp->pnext = temp2->pnexttemp 的'下一个节点',设置为 temp2 原本的'后继节点'。temp2→后继节点 的原始链路保持不变;② temp→后继节点(新节点先和'后面的节点'挂好钩)。temp2->pnext = temptemp2 的'下一个节点',从'原本的后继节点'改成 temp。temp2→后继节点 的原始链路被切断(但此时 temp 已经和后继节点挂钩,不怕丢失);② temp2→temp;③ 最终形成完整链路:temp2→temp→后继节点,插入完成。把链表节点比作火车车厢:
temp2:火车的第 N 节车厢(前驱)temp:要插入的新车厢(第 N+1 节)后继节点:火车的第 N+1 节车厢(原本的,插入后变成第 N+2 节)要完成'头插',必须保证 2 件事:
temp->pnext = p->head?p->head 是原链表的头节点,这一步的作用是:让新节点 temp 的'下一个节点'指向原链表的头节点——相当于把新节点'挂'到原链表的最前面,保证原链表的所有节点不会因为插入新节点而丢失。

LL* temp = p 是指针浅拷贝,temp 和 p 指向同一块链表结构体内存,修改 temp->head 本质上就是修改 p->head;p->head 会被移动到第 ip 个节点,原头节点永久丢失,后续打印、插入都会错乱;NODE* 遍历节点,而非 LL* 操作链表结构体)。NODE* 类型临时指针遍历节点,不触碰链表结构体的 head。核心在于它们指向的对象不同,修改的是不同层级的内容——LL* temp 修改的是「链表结构体本身」,而 NODE* tempNode 修改的是「临时指针的指向」,不会触动原链表的核心结构。
LL* temp = p 为什么会修改原链表LL* temp = p 是「指针浅拷贝」p 是 LL* 类型,指向一块链表结构体内存(里面存着 head、end、length 三个成员);LL* temp = p 执行后,temp 和 p 是「两个不同的指针变量,但存储了同一个内存地址」(相当于两把钥匙,都能打开同一间房子);temp 和 p 指向同一个链表结构体,修改 temp 的成员,就是修改 p 的成员。temp->head = temp->head->pnext 是「修改链表结构体的核心成员」temp->head 访问的是「链表结构体」中的 head 成员;temp->head 赋值,本质上是修改了这块链表结构体内存中 head 成员的值;temp 和 p 指向同一个结构体,所以 p->head(原链表的头指针)也会被同步修改。NODE* tempNode = p->head 为什么不会修改原链表NODE* tempNode = p->head 是「复制节点的地址」p->head 是链表结构体中的成员,存储的是「头节点的内存地址」;NODE* tempNode = p->head 执行后,tempNode 存储了「头节点的地址」,它指向的是「节点内存」,而不是「链表结构体内存」。tempNode = tempNode->pnext 是「修改临时指针自身的指向」tempNode 这个指针变量本身存储的地址;p->head 仍然存储着原来的头节点地址)。| 写法 | 指向的对象 | 操作的本质 | 是否修改原链表 |
|---|---|---|---|
LL* temp = p; temp->head = ... | 原链表结构体(LL 类型) | 修改链表结构体的 head 成员 | 是(破坏原链表) |
NODE* tempNode = p->head; tempNode = ... | 链表节点(NODE 类型) | 仅修改临时指针自身的指向 | 否(保护原链表) |


其实就是在有 next 的基础上多加一个 front,万变不离其宗,后面对应的函数封装自己可以根据需要来加 front,原则上只要保证链表的连接性完整就可以。
head=end,这边不多做赘述。
利用 while 循环和 next 原理对链表中的数据进行打印:

以下是完整代码示例:
#include<stdio.h>
#include<stdlib.h>
typedef struct Mynode {
int data;
struct Mynode* pnext;
} NODE;
// 链表节点的创建,一个值,一个用于连接节点的指针
typedef struct mylist {
NODE* head;
NODE* end;
int length;
} LL;
// 这是我规定的一个单向链表,里面有头有尾,有长度
LL* create() {
LL* p = (LL*)malloc(sizeof(LL));
if (p == NULL) {
printf("创建链表失败");
return NULL;
}
p->head = NULL;
p->end = NULL;
p->length = 0;
return p;
}
// 创建一个为空的链表
NODE* createnode(int data) {
NODE* PN = (NODE*)malloc(sizeof(NODE));
if (PN == NULL) {
printf("为链表节点申请内存失败");
return NULL;
}
PN->data = data;
PN->pnext = NULL;
return PN;
}
void destory(LL** p) {
if (p == NULL) {
printf("链表本身不存在,无需销毁");
}
NODE* temp = NULL;
while ((*p)->head) {
temp = (*p)->head;
(*p)->head = (*p)->head->pnext;
free(temp);
}
free(*p);
*p = NULL;
}
void putlast(LL* p, int target) {
if (NULL == p) {
printf("链表不存在,无法添加");
return;
}
NODE* temp = createnode(target);
if (temp == NULL) {
printf("为数值创建节点失败");
return;
}
if (NULL == p->head) {
p->head = p->end = temp;
} else {
p->end->pnext = temp;
p->end = temp;
}
p->length++;
}
void putmid(LL* p, int ip, int target) {
if (NULL == p) {
printf("链表不存在,无法添加");
return;
}
NODE* temp = createnode(target);
NODE* temp2 = p->head;
if (temp == NULL) {
printf("为数值创建节点失败");
return;
}
if (ip <= 0 || p->length == 0) {
temp->pnext = p->head;
p->head = temp;
if (p->length == 0) {
p->end = temp;
}
} else if (ip >= p->length) {
p->end->pnext = temp;
p->end = temp;
} else {
for (int i = 0; i < ip - 1; i++) {
temp2 = temp2->pnext;
}
temp->pnext = temp2->pnext;
temp2->pnext = temp;
}
p->length++;
}
NODE* found(LL* p, int ip) {
if (NULL == p || p->length == 0) {
printf("链表无法查找\n");
return NULL;
}
if (ip < 0 || ip > p->length) {
printf("查找位置非法(超出链表长度)\n");
return NULL;
}
NODE* tempNode = p->head;
for (int i = 0; i < ip - 1; i++) {
tempNode = tempNode->pnext;
}
return tempNode;
}
void printd(LL* p) {
if (p == NULL) {
printf("链表本身不存在,无法打印");
return;
}
if (p->length == 0) {
printf("无法打印");
return;
}
NODE* temp = p->head;
while (temp != NULL) {
printf("%d", temp->data);
temp = temp->pnext;
}
}
int main() {
LL* p = create();
putmid(p, 0, 1);
putmid(p, 1, 2);
putmid(p, 2, 3);
NODE* s = found(p, 0);
putlast(p, s->data);
putmid(p, 2, s->data);
// destory(&p);
printd(p);
return 0;
}

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online