若文中出现疏漏、不足之处，还望广大读者批评指正

接下来我会持续更新C语言数据结构、Java语法、Java数据结构、MySQL、JavaEE、微服务、Redis等等内容的知识点整理。后续我也会精心制作算法解析、项目经验系列内容，内容绝对干货。相信这些文章能够成为我和大家的“葵花宝典”，喜欢的话就关注一下吧！敬请期待！
PS:下节预告——单链表经典算法OJ题目详解！

文章目录

前言：顺序表的问题及思考

  1. 中间/头部的插⼊删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
  3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？
答案就是使用另一种数据结构——链表

一、链表的概念及结构

这部分了解的话就可以直接学习代码实现模块

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

在这里插入图片描述

  • 与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点”
    节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
    图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希
    望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。

补充说明：
1、链式结构在逻辑上是连续的，在物理结构上不⼀定连续
2、节点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

二、单链表的实现

概述

单链表实现分三个文件设计，实现功能模块化与代码解耦。
SList.h 负责声明接口， SList.c 负责实现逻辑， test.c 负责验证功能，结构清晰且便于维护。
大家可以跟着注释梳理下代码结构脉络

SList.h

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

typedef int SLTDataType;//定义储存数据类型

typedef struct SListNode//定义单链表
{
	SLTDataType data;//储存数据
	struct SListNode* next;//储存下一个节点的地址
}SLTNode;


//创建节点并赋值
SLTNode* SLTBuyNode(SLTDataType x);
//打印链表
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);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表（释放动态申请的内存）
void SListDesTroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

//创建节点并赋值
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTDataType));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//申请空间后赋值，next值后续据需求更改
	newnode->data = x;
	newnode->next = NULL;
	return newnode;//把节点地址返回以便后续操作使用
}
//打印链表
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	if (pcur == NULL)//链表为空
	{
		printf("链表为空！\n");
		return;
	}
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;//每打印完一个数据就通过pcur->next访问到下一个节点
	}
	printf("NULL\n");
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead是用来访问指向节点的那个地址的指针，
				   //如果pphead都为NULL就无任何意义了
	SLTNode* newnode = SLTBuyNode(x);//创建节点，并接受其地址
	if (*pphead == NULL)//若链表为空，则直接将地址赋给头节点
	{
		*pphead = newnode;
	}
	else
	{
		//若链表不为空，则要找到尾节点
		SLTNode* ptail = *pphead;
		while (ptail->next)//ptail->next:尾节点的next值为NULL
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;//将新节点地址赋给原尾结点的next，这样两个节点就链接成功
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;//头插时即使遇到空链表也正常运行
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//删除数据时链表也不能为空
	if ((*pphead)->next==NULL)//注意：->的优先级比*高，所以*pphead要加括号
	{
		//处理只有一个节点的情况
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾节点
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;//储存尾节点的前一个节点
		while (ptail ->next)//若只有一个节点，ptail->就访问了空指针
		{
			prev = ptail;
			ptail = ptail->next;//若此时遍历到了尾节点，while再判断时就为NULL（假）
		}				      //而ptail也储存了前一个节点地址
		free(ptail);
		ptail = NULL;
		prev->next = NULL;//此时ptail是尾节点，next值应置为空
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next ;
	free(*pphead);
	*pphead = next;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);//链表不能为空
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//遍历完后还没有就返回NULL
	return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && pos);
	SLTNode* newnode = SLTBuyNode(x);
	if ((*pphead)->next == NULL)//节点只有一个
	{
		SLTPushFront(pphead, x);//直接调用头插
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos)//找到pos之前的节点
	{
		prev = prev->next;
	}
	//将节点链接起来
	prev->next = newnode;
	newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/pos不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos之前的节点
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos&&pos->next);
		SLTNode* next = pos->next->next;
		free(pos->next);
		pos->next = next;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	SLTNode* next =NULL;
	while (pcur)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

//void SListTest01()
//{
//	//链表是由一个一个的节点组成
//	//创建几个节点
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	//将四个节点连接起来
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	//调用链表的打印
//	SLTNode* plist = node1;
//	SLTPrint(plist);
//}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); // 1->2->3->4->NULL

	SLTPrint(plist);

	//测试查找
	SLTNode* find = SLTFind(plist, 1);
	//SLTInsert(&plist, find, 11);
	//SLTInsertAfter(find, 11);
	////删除pos节点
	//SLTErase(&plist, find);
	//SLTEraseAfter(find);
	//SLTPrint(plist);
	if (find == NULL)
	{
		printf("没有找到！\n");
	}
	else {
		printf("找到了！\n");
	}


	//SLTPushBack(NULL, 5);
	//
	////测试头插
	//SLTPushFront(&plist, 6);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 7);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);

	////测试头删
	//SLTPopFront(&plist);
	//SLTPrint(plist);// 2->3->4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	SListDesTroy(&plist);

}

int main()
{
	//SListTest01();
	SListTest02();
	return 0;
}

觉得文章对你有帮助的话就点个赞，收藏起来这份免费的资料吧！也欢迎大家在评论区讨论技术、经验。

# 数据结构 # c语言 # 链表
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

avatar 魔乐社区
cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模

avatar 魔乐社区