【数据结构初阶】一篇文章带你超深度理解【单链表】

🕗 发布于 2024-07-24 23:54 数据结构 链表 开发语言

hi ！

前言：

1、链表的概念和结构

2、单链表（Single List，简写SList）的实现

———————————————— 《你的名字》 ————————————————

正文开始——

前言：

前面我们学习了顺序表，实现了对数组内容增删查改等操作，但是顺序表仍然存在一些缺陷。

中间/头部的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间，这是不小的消耗；
增容一般是成2倍的增长，大概率会有一些空间的浪费。

那我们该如何解决上面的问题呢？下面我们来学习一下链表。

1、链表的概念和结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现。

2、单链表（Single List，简写SList）的实现

上面我们了解了链表的概念和结构，链表又分为很多种，今天我们先学习链表之一单链表。

2.1 定义链表（结点）的结构

//定义链表（结点）的结构

typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;  
struct SListNode* next;
}SLTNode;

2.2 创建一个链表

这里申请空间使用 malloc，在链表里面不存在增容的操作，想插入数据直接申请一个新的结点即可！用 calloc 也可以，calloc会让申请空间的内容初始化为0。

【代码】

test.c

//创建一个链表
void creatSList()
{
//链表是由一个一个的结点组成的

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;

}

2.3 打印链表

【思路图解】

【代码】

//链表的打印

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

2.4 尾插

【思路图解】

【代码】

SList.c

//申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc file!");
exit(1);
}
node->data = x;
node->next = NULL;

return node;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申请一个新结点
SLTNode* newnode = SLTBuyNode(x);

if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* pcur = *pphead;

//找尾结点
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
    //plist为指向第一个结点的指针
SLTPushBack(&plist,100);
SLTPrint(plist);
}

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

【验证】

【注意】

在 test.c 里面尾插时传的是&plist ，而不是 plist。我们希望形参的改变影响实参，所以我们取实参的地址。plist 作为参数传的是一个指针变量而不是一个地址，只有 &plist （有&）才算是真正的取地址使得形参的改变影响实参。用二级指针来接收。
找尾结点。循环的条件是 pcur->next，而不是 pcur。因为 pcur->next 为NULL跳出循环时，说明 pcur 为尾结点，当 pcur 为空跳出循环时，说明 pcur 是尾结点的下一个节点，而不是尾结点。
pphead==&plist；*pphead==plist（指向第一个结点的指针）。
assert (pphead)；传过来的地址不能为空。

2.5 头插

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);

//申请一个新结点
SLTNode* newnode = SLTBuyNode(x);

newnode->next = *pphead;
*pphead = newnode;
}

test.c


void SListTest01()
{
    //验证尾插
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);
    
    //验证头插
SLTPushFront(&plist, 200);
SLTPrint(plist);
}

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

【验证】

2.6 尾删

各结点的地址应为0x0012FF...，在此纠正下面的错误。谅解哈~~~

【思路图解】

当链表内不止一个结点时

当链表内只有一个结点时

【代码】

SList.c


//尾删
void SLTPopBack(SLTNode** pphead)
{
//链表为空，不可删除
assert(pphead && *pphead);

//处理只有一个结点的情况，要删除的就是头结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找 ptail 和 prev
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}

test.c


void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

SLTPopBack(&plist);
SLTPrint(plist);
}

int main()
{
/*createSList();*/
SListTest01();
return 0;
}

【验证】

2.7 头删

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头删
void SLTPopFront(SLTNode** pphead)
{
//链表不为空
assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

SLTPopFront(&plist);
SLTPrint(plist);

}

int main()
{
/*createSList();*/
SListTest01();
return 0;
}

【验证】

2.8 查找

各结点的地址应为0x0012FF...，在此纠正下面的错误。

思路简单，直接上代码：

SList.c

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}

【注意】SLTNode* pcur = phead，重新定义一个指针变量 pcur 指向第一个结点，让 pcur 来遍历链表，防止头结点丢失。

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

SLTPopFront(&plist);
SLTPrint(plist);

SLTNode* find = SLTFind(plist, 2);
if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
}
}

【验证】

2.9 在指定位置之前插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c


//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);

if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//申请一个新的结点
SLTNode* newnode = SLTBuyNode(x);

//找pos的前一个结点prev
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

//SLTPopFront(&plist);
//SLTPrint(plist);

//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/

SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);

}

【验证】

2.10 在指定位置之后插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

//SLTPopFront(&plist);
//SLTPrint(plist);

//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/

/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/

SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist); 

}

【验证】

2.11 删除pos结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
assert(pphead && *pphead);
    //这里对pos进行限制，链表中必须有pos这个结点，在查找中若没有pos结点则返回NULL
assert(pos);

if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
//找到prev：pos的前结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

//SLTPopFront(&plist);
//SLTPrint(plist);

//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/

/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/

/*SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist); */

SLTNode* find = SLTFind(plist, 2);
SLTErase(&plist, find);//这里的find由pos接收，SLTFind若没找到存储2这个结点则返回NULL
SLTPrint(plist); 

}

【验证】

2.12 删除pos之后的结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}

test.c

void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);

/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/

/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/

//SLTPopFront(&plist);
//SLTPrint(plist);

//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/

/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/

/*SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist); */

//SLTNode* find = SLTFind(plist, 2);
//SLTErase(&plist, find);
//SLTPrint(plist); 

SLTNode* find = SLTFind(plist, 2);
SLTEraseAfter(find);
SLTPrint(plist); 

}

【验证】

2.13 销毁链表

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

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

SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
    //*pphead=plist，链表为空，也要把*pphead置为空
*pphead = NULL;
}

【验证】

今天单链表的深度学习就结束啦，拜拜~~~

完——

———————————————— 《你的名字》 ————————————————

重要的人，不能忘记的人，不想忘记的人，你，是谁？

不管在哪里，不管过多久，不管是要跨过高山，还是跨过湖海，我一定会去见你一面。

スパークル_RADWIMPS_高音质在线试听_スパークル歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由RADWIMPS演唱的高清音质无损スパークルmp3在线听,听スパークル,只来酷狗音乐!https://t4.kugou.com/song.html?id=avhoFadCPV2

至此结束——

再见——

原文地址：https://blog.csdn.net/lrq13965748542/article/details/140621731

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：spring 中对象创建之 BeanWrapperImpl 的初始化
下一篇：java 开发学习总结

MYSQL常用基本操作总结
SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having >select
阅读更多2024-09-19
JAVA并发编程系列之Semaphore信号量剖析
候选人，心中万马奔腾！！！吐了一口82年老血，当场砸电脑回家！原因是：腾讯T2面试，现场限时3分钟+限最多20行代码，模拟地铁口安检进站。其中安检入口10个，当前排队人数是100个，每个人安检进站耗时
阅读更多2024-09-19
24年蓝桥杯及攻防世界赛题-MISC-2
24年蓝桥杯及攻防世界赛题-MISC-2
阅读更多2024-09-19
干货-并发编程提高——重谈 RUNNABLE-上篇（十四）
直接看它的 Javadoc 中的说明：一个在 JVM 中执行的线程处于这一状态中。（A threadexecuting而传统的进（线）程状态一般划分如下：注：这里的进程指早期的单线程进程，这里所谓进程
阅读更多2024-09-19
phpstudy 建站使用 php8版本打开 phpMyAdmin后台出现网页提示致命错误：（phpMyAdmin这是版本问题导致的）
将网站根目录phpMyAdmin4.8.5里面的文件换成官网下载的5.2.1版本即可。重启网站，打开phpMyAdmin后台即可（若打不开更改 mysql密码即可）解决方法：官网下载phpmyadm
阅读更多2024-09-19
零工市场小程序：保障灵活就业
截止2024年高校毕业生达到1179万，在今年的经济情况下，就业市场就面临着比较大的压力，许多毕业生面临一时之间难以找到合适的工作的问题，那么求职者就会需要一份临时的工作来得到报酬，面对传统的找零工方
阅读更多2024-09-19
Linux中权限和指令
mv指令是move的缩写，用来，经常用来备份文件或目录。
阅读更多2024-09-19
Redis 底层揭秘：事务与 Lua 脚本的工作原理
定义Lua 是一种轻量级的脚本语言，它可以在 Redis 中被执行，用于实现复杂的逻辑操作。优势与事务相比，Lua 脚本具有更高的性能和更好的灵活性。Lua 脚本可以在 Redis 服务器端一次性执行
阅读更多2024-09-19
Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
【代码】Vue3使用shapefile读取矢量数据，以数组形式返回坐标点。
阅读更多2024-09-19
WEB 编程：使用富文本编辑器 Quill 配合 WebBroker 后端
评估了好几个，最后选择这个开源的。把前端代码，存储为一个单独的文本文件，方便随便哪个页面需要的时候可以使用。相当于封装为一个独立的对象，方便代码重用。
阅读更多2024-09-19

【数据结构初阶】一篇文章带你超深度理解【单链表】

前言：

1、链表的概念和结构

2、单链表（Single List，简写SList）的实现

2.1 定义链表（结点）的结构

2.2 创建一个链表

2.3 打印链表

2.4 尾插

2.5 头插

2.6 尾删

2.7 头删

2.8 查找

2.9 在指定位置之前插入数据

2.10 在指定位置之后插入数据

2.11 删除pos结点

2.12 删除pos之后的结点

2.13 销毁链表

———————————————— 《 你的名字 》 ————————————————

相关文章

———————————————— 《你的名字》 ————————————————