【数据结构】单链表

🕗 发布于 2024-10-17 10:15 数据结构 算法 c语言

🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

🐼前言
🐼链表
🐼动态申请一个节点
🐼 单链表尾插
🐼 单链表打印
🐼单链表的头插
🐼单链表的尾删
🐼单链表头删
🐼 单链表查找
🐼单链表删除pos位置之后的值
🐼单链表在pos位置之后插入x
🐼在pos的前面插入x
🐼 删除pos位置
🐼销毁链表
🐼全部源码
🐼文末

🐼前言

在上一节我们实现了顺序表并介绍了线性表，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 顺序表，这一节要学习第二个线性表:链表

🐼链表

✨链表的概念:链表是⼀种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在逻辑上是连续的，因此同样也是线性表。

🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

✨链表就像一节节火车 ,每一节车厢都是一个结点，每一个结点都是独立的；它们一节一节链接起来，少一节，多一节都不影响整个车厢。

✨与顺序表不同的是，链表中每节车厢都是动态申请下来的独立空间，(一般是在堆上申请的)，每一节车厢我们称为节点，每一个节点中有自已要保存的数据和保存下一个节点的地址。
✨由于每一个结点都是独立的内存空间，我们需要用指针变量来保存下一个节点的地址，才能从当前节点找到下一个节点的位置。
✨因为既要有自已要保存的数据又要有下一个节点的地址。> 我们用一个结构体来维护链表，成员变量有两个，单链表定义如下:

//单链表
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;

✨我们用data来保存数据，next来指向下一个节点的地址，这样就能从当前节点找到下一个节点，链表就能很好的串起来了。
下面我们基于单链表的定义，给出常见单链表的一些实现方法：

🐼动态申请一个节点

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("SListPushBack()::fail");
exit(-1);
}
newnode->next = NULL;
newnode->data = x;
return newnode;
}

🌻代码解析

💫由于我们的单链表的每一个节点都是向动态内存申请的，为了以下方法实现方便，比如插入节点，就要申请节点。因此这里封装了一个申请节点的方法。将申请的节点下一个节点置为空，更新保存的申请节点的数据。最后将申请后的节点返回。
时间复杂度为O(1),代码执行常数次，空间复杂度为O(1),只创建有效个变量

🐼 单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
//不带头结点，分情况
if (*pphead == NULL)
{
//空链表
*pphead = newnode;
}
else
{
//找尾
//非空链表
SListNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
//找到尾
pcur->next = newnode;
}
}

🌻代码解析

💫链表尾插首先是要插入节点，所以先申请一个新节点调用 BuySListNode()方法。尾插，即要在尾部插入新节点，所以我们要找尾节点，那么就要遍历原链表，原本尾节点指向空，现在更新尾结点的指向，让尾结点指向新节点。
尾插如图:
不过还有一种情况没有考虑，如果该链表是空链表，那么pcur->next对空指针解引用就有问题，所以，单独处理尾插是空链表的情况，直接让新节点覆盖头结点.
时间复杂度为O(N),遍历一次链表，空间复杂度为O(1),只创建有效个变量

🍀尾插测试结果:
在这里插入图片描述

注意：为什么这里形参用**pphead，因为我创建了一个SListNode* 类型的指针,因为形参是实参的一份历史拷贝，改变形参不会影响实参，为了影响实参(plist),这里传址调用，因此用二级指针接受一级指针的地址，
如图:

🐼 单链表打印

// 单链表打印
void SListPrint(SListNode* phead)
{
SListNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}

🌻代码解析
💫为了更直观的展示链表，我们通过pcur->next为空作为循环终止条件，一一打印出链表中的有效数据，最后为了打印最后一个节点的指针为空，做了处理。
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量
头插如图：

🍀 尾插测试结果:
在这里插入图片描述

🐼单链表的头插

// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}

🌻代码解析

💫插入操作首先都要申请新节点，让新节点的指针指向头结点，让原来的头结点更新到新插入的节点，即新插入的节点作为头结点。考虑边界情况：如果是空链表，上述代码仍然可以解决。
时间复杂度为O(1),代码执行常数次，空间复杂度为O(1),只创建有效个变量
头插如图:

🍀 头插测试结果:

🐼单链表的尾删

// 单链表的尾删
void SListPopBack(SListNode** pphead)
{
//传过来链表存在
assert(pphead);
//链表不能为空
assert(*pphead);


//链表只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//链表有多个节点

SListNode* ptail = *pphead;
SListNode* prev = NULL;
//找尾
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//pcur走到尾
//prev pcur pcur->next
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}

🌻代码解析

💫尾删操作依旧是先找尾patil，但在尾节点删除前，要改变前一个节点的next指向，用prev来保存尾结点的前一个节点，最后，修改尾结点ptail前一个节点prev的指向，释放尾结点。但是如果链表只有一个节点，当前的循环条件就会造成越界访问，所以，单独处理链表只有一个节点的情况：直接释放头结点。注意：链表不能为空。
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量
画图分析：

🍀尾删测试结果:

在这里插入图片描述

🐼单链表头删

// 单链表头删
void SListPopFront(SListNode** pphead)
{
//传过来链表存在
assert(pphead);
//链表不能为空
assert(*pphead);

//保存下一个节点
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

🌻代码解析

💫 删除链表不为空，为了删除头结点，首先要保存头结点的下一个节点next，删除头结点，更新头结点走到next.
时间复杂度为O(1),代码执行常数次，空间复杂度为O(1),只创建有效个变量
画图分析:

🍀 头删测试结果:
在这里插入图片描述

🐼 单链表查找

SListNode* SListFind(SListNode* pphead, SLTDateType x)
{
//传过来链表存在
assert(pphead);

SListNode* pcur = pphead;
while (pcur)
{
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}

🌻代码解析

💫 遍历一次链表，如果当前节点的数据是要查找的x，返回当前节点；如果遍历完还没找到，返回NULL
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量

🍀 测试结果:
在这里插入图片描述

🐼单链表删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{
//pos不能是尾结点
assert(pos && pos->next);
SListNode* del = pos->next;

//pos del del->next
pos->next = del->next;
free(del);
del = NULL;
}

🌻代码解析

💫 要满足要删除的节点不是尾结点并且pos存在。保存要删除的节点，更新pos新next的指向。
时间复杂度为O(1),代码执行常数次，空间复杂度为O(1),只创建有效个变量
画图分析:

🍀 测试结果:
在这里插入图片描述

🐼单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);

//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}

🌻代码解析

💫插入操作首先都要申请新节点，先让新节点newnode指向pos的下一个节点，再更新pos的指向。注意:顺序不能颠倒
时间复杂度为O(1),代码执行常数次，空间复杂度为O(1),只创建有效个变量
画图分析:

🍀 测试结果:
在这里插入图片描述

🐼在pos的前面插入x

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
assert(pos && pphead);


if (*pphead == pos)
{
//pos是头结点
//头插
SListPushFront(pphead, x);
}
else
{
//找pos的前一个节点
SListNode* prev = *pphead;
SListNode* newnode = BuySListNode(x);
while (prev->next != pos)
{
prev = prev->next;
}
//找到pos的前一个节点
//prev newnode pos 
newnode->next = pos;
prev->next = newnode;//注意不能调换顺序，不然prev找不到pos
}
}

🌻代码解析

插入操作首先都要申请新节点，因为是在pos之前插入，所以保存pos的前一个节点prev，循环遍历找到pos的前一个节点。修改prev newnode pos 三个节点的指向。注意:先让newnode的next保存pos，再更新prev的指向，不能调换顺序，不然prev找不到pos。考虑边界处理：如果pos是头结点，这种方法会造成越界访问，单独处理，因为是在pos的前面插入x，因为直接调用头插方法。
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量
画图分析:

🍀 测试结果:
在这里插入图片描述

🐼 删除pos位置

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pos && pphead);
if (pos == (*pphead))
{
//当pos是头结点
//头删
SListPopFront(pphead);
}
else
{
//找pos的前一个节点
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

🌻代码解析

删除当前节点依旧要保存前一个节点，循环遍历找到pos的前一个节点，修改前一个节点的指向。处理边界情况，如果pos是头结点，循环条件会造成越界访问，特殊处理，即头删。注意:删除节点不能为空。
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量
画图分析:

在这里插入图片描述

🍀 测试结果:
在这里插入图片描述

🐼销毁链表

//销毁链表
void SLTDestroy(SListNode** pphead)
{
//链表不为空
assert(pphead && *pphead);

SListNode* pcur = *pphead;
while (pcur)
{
SListNode* next = pcur->next;
free(pcur);
pcur = next;
}
pcur = NULL;
//头指针置为空
*pphead = NULL;
}

🌻代码解析

让pcur保存当前节点，next保存下一个节点，删除当前节点，更新pcur的值。最后，将指向头结点的指针置为空，完成链表销毁。
画图分析:
时间复杂度为O(N),只遍历一次链表，空间复杂度为O(1),只创建有效个变量

🍀 测试结果:
在这里插入图片描述

🐼全部源码

SListNode.h

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

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pphead);
// 单链表头删
void SListPopFront(SListNode** pphead);
// 单链表查找
SListNode* SListFind(SListNode* pphead, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
//销毁链表
void SLTDestroy(SListNode** pphead);

SListNode.c

#include "SListNode.h"

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("SListPushBack()::fail");
exit(-1);
}
newnode->next = NULL;
newnode->data = x;
return newnode;
}

// 单链表打印
void SListPrint(SListNode* phead)
{
SListNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
//不带头结点，分情况
if (*pphead == NULL)
{
//空链表
*pphead = newnode;
}
else
{
//找尾
//非空链表
SListNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
//找到尾
pcur->next = newnode;
}
}

// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}


// 单链表的尾删
void SListPopBack(SListNode** pphead)
{
//传过来链表存在
assert(pphead);
//链表不能为空
assert(*pphead);


//链表只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//链表有多个节点

SListNode* ptail = *pphead;
SListNode* prev = NULL;
//找尾
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//pcur走到尾
//prev pcur pcur->next
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}

// 单链表头删
void SListPopFront(SListNode** pphead)
{
//传过来链表存在
assert(pphead);
//链表不能为空
assert(*pphead);

//保存下一个节点
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

// 单链表查找
SListNode* SListFind(SListNode* pphead, SLTDateType x)
{
//传过来链表存在
assert(pphead);

SListNode* pcur = pphead;
while (pcur)
{
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);

//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
//pos不能是尾结点
assert(pos && pos->next);
SListNode* del = pos->next;

//pos del del->next
pos->next = del->next;
free(del);
del = NULL;
}

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
assert(pos && pphead);


if (*pphead == pos)
{
//pos是头结点
//头插
SListPushFront(pphead, x);
}
else
{
//找pos的前一个节点
SListNode* prev = *pphead;
SListNode* newnode = BuySListNode(x);
while (prev->next != pos)
{
prev = prev->next;
}
//找到pos的前一个节点
//prev newnode pos 
newnode->next = pos;
prev->next = newnode;//注意不能调换顺序，不然prev找不到pos
}
}

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pos && pphead);
if (pos == (*pphead))
{
//当pos是头结点
//头删
SListPopFront(pphead);
}
else
{
//找pos的前一个节点
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

//销毁链表
void SLTDestroy(SListNode** pphead)
{
//链表不为空
assert(pphead && *pphead);

SListNode* pcur = *pphead;
while (pcur)
{
SListNode* next = pcur->next;
free(pcur);
pcur = next;
}
pcur = NULL;
//头指针置为空
*pphead = NULL;
}

test.c

#include "SListNode.h"

void Test01()
{
SListNode* plist = NULL;//空链表
//测试尾插
/*SListPushBack(&plist,1);
SListPrint(plist);
SListPushBack(&plist,2);
SListPrint(plist);
SListPushBack(&plist,3);
SListPrint(plist);
SListPushBack(&plist,4);
SListPrint(plist);*/
//测试头插
SListPushFront(&plist, 1);
//SListPrint(plist);
SListPushFront(&plist, 2);
//SListPrint(plist);
SListPushFront(&plist, 3);
//SListPrint(plist);
SListPushFront(&plist, 4);
SListPrint(plist);
//测试尾删
/*SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);*/

//测试头删
/*SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);*/
//SListPopFront(&plist);
//测试查找
SListNode* ret = SListFind(plist, 1);
/*if (ret != NULL)
printf("找到了\n");
else
printf("没找到\n");*/
// 单链表在pos位置之后插入x
/*SListInsertAfter(ret, 99);
SListPrint(plist);*/
// 单链表删除pos位置之后的值
/*SListEraseAfter(ret);
SListPrint(plist);*/
 在pos的前面插入
//SLTInsert(&plist, ret, 99);//ret保存数据为4
//SLTInsert(&plist, ret, 99);//ret保存数据为1
//SListPrint(plist);

//删除pos节点
//SLTErase(&plist, ret);//pos是1
//SListPrint(plist);
//销毁顺序表
SLTDestroy(&plist);

}

int main()
{
Test01();
}

🐼文末

🌲总结：我们发现顺序表的尾部操作更简单，例如，尾插尾删，时间复杂度和空间复杂度都为O(1),而单链表恰好相反，尾插尾删，时间复杂度和空间复杂度都O(N)；
链表的头部操作更简单，头插头删时间复杂度和空间复杂度都为O(1),而顺序表恰好相反，时间复杂度和空间复杂度都为O(N)。

感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️

原文地址：https://blog.csdn.net/2401_83251330/article/details/142834417

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

上一篇：【实战项目】——Boost搜索引擎(五万字)
下一篇：简单聊聊限流算法

交通银行核心系统分布式实践
交通银行贷记卡是当年由法国服务商ATOS 源讯建设，使用IBM Z/OS 大型机 + CICS+ DB2+COBOL 为基础，该系统已上线运行十余年，在册卡量超过7000万，日均授权交易量1200万，
阅读更多2024-10-19
git 与 github 同步
出现类似提示验证成功Hi bingmengzi!$ ssh-keygen -t rsa -C "邮箱" //你自己注册GitHub的邮箱。git config --global
阅读更多2024-10-19
【基础篇】AOF日志：宕机了，Redis如何避免数据丢失？
如果有人问你：“你会把 Redis 用在什么业务场景下？”我想你大概率会说：“我会把它当作缓存使用，因为它把后端数据库中的数据存储在内存中，然后直接从内存中读取数据，响应速度会非常快。我们很容易想到的
阅读更多2024-10-19
Excel：vba实现批量修改文件名
【代码】Excel：vba实现批量修改文件名。
阅读更多2024-10-19
录微课专用提词器，不会被录进视频中的提词器，还能显示PPT中备注的内容
不坑提词器，全称：不坑隐形提词器。是一款能够在截图、录屏、直播过程中隐藏界面的提词器软件。系统要求：Win10 1024 以上（特别提醒：Win7状态下不可隐身）
阅读更多2024-10-19
用python-pptx轻松统一调整演示文档配色方案
哈喽，大家好，我是木头左！
阅读更多2024-10-19
DirectX 11 和 Direct3D 11 的关系
DirectX 11是微软的一项技术，为高性能游戏和复杂图形程序制定了标准。它是DirectX系列的一个版本，引入了多项创新功能，如硬件加速的Tessellation（细分曲面技术）、多线程渲染等，这
阅读更多2024-10-19
nginx平滑升级
nginx -V 最后的版本如果也是下载的高版本说明平滑升级完成。
阅读更多2024-10-19
Java生死簿管理小系统（简单实现）
这是一个简单的生死簿管理小系统，实现了基本的增删改查功能往期文章第一章：日常_JAVA_面试题集（含答案）第二章：日常_JAVA_面试题集（含答案）平安壹钱包JAVA面试官：请你说一下Mybatis的
阅读更多2024-10-19
基于vue框架的的大学校园社团管理系统q00q2（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。
开题报告内容。
阅读更多2024-10-19

【数据结构】单链表

目录

🐼前言

🐼链表

🐼动态申请一个节点

🐼 单链表尾插

🐼 单链表打印

🐼单链表的头插

🐼单链表的尾删

🐼单链表头删

🐼 单链表查找

🐼单链表删除pos位置之后的值

🐼单链表在pos位置之后插入x

🐼在pos的前面插入x

🐼 删除pos位置

🐼销毁链表

🐼全部源码

🐼文末

相关文章