数据结构之链表（1），单链表

顺序表的中间/头部插入删除数据的时间复杂度为O(n)，而链表相同功能时间复杂度为O(1)
顺序表增容需要申请请新空间，拷贝数据，释放旧空间。会有不小的消耗。链表每次申请一个节点，不存在拷贝，释放旧空间。
顺序表增容一般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。链表不存在空间浪费

以上是链表相对与顺序表的优点，但不代表顺序表一定不如链表，顺序表在有些场景下效率还是非常高，因此选择使用什么数据结构是看场景的要求

二、链表的分类

链表的结构非常多样，有带头不带头，单向或者双向，循环不循环，这三种属性情况组合起来就有8种（2x2x2）链表结构：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表：

无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现该结构会带来很多优势，后面我们代码实现了就知道了。

本文主要讲述单链表

三、单链表

单链表的结构如下图：

单链表的结构声明：

typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//节点数据
struct SListNode* next;//指向下一节点的指针变量
}SLTNode;

以下单链表同样由3个文件组成：

SList.h：单链表的结构声明，各种函数声明
SList.c：用于函数的具体实现
test.c：用于测试单链表（自行测试）

四、单链表的实现

1.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;

//打印
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);

2.SList.c文件

1.SLTPrint函数

//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;

//循环打印
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}

printf("NULL\n");
}

解析：该函数用于打印链表数据，使用一个pcur指针，只要不为空指针，就循环遍历下一个节点

2.SLTBuyNode函数

//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{
//申请一个节点
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}

//赋值
node->data = x;
node->next = NULL;

return node;
}

解析：

该函数用于申请新节点，一个参数，其为新节点存储的数据
使用malloc函数申请，申请成功后将其数据域赋值为参数值，指针域赋值为空指针NULL
因为该函数主要为其他功能函数服务，因此只需写在 SList.c 文件中即可，无需在头文件SList.h 中声明

3.SLTPushBack函数

//尾插
//因为要修改plist本身，因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//断言pphead不能为空指针
assert(pphead);
//申请新节点
SLTNode* newnode = SLTBuyNode(x);

//如果pphead指向的第一个节点就是空指针
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾结点
SLTNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}

解析：

该函数功能为：在链表尾部插入一个数据。因此需要链表的头部指针和需要插入的数据x
为什么头节点参数是二级指针？答：因为需要修改原指针变量本身，我们知道函数传参分为传值传参和传址传参（&），想要修改原变量内容就需要传址传参，而这里原变量就是一个指向链表头节点的指针变量，因此原变量通过&传参，就需要二级指针来接收一级指针变量的地址。所以这里就是用二级指针，下面其他的函数同理。
申请完新节点，插入到链表尾部时要分2种情况，1链表为空，2链表不为空。
链表为空则直接将新节点插入链表即可，也就是将指向头结点的指针指向新节点。链表不为空就需要寻找尾结点，尾节点的特点就是next指针指向空。循环之后将尾节点的next指针修改为新节点即可。

4.SLTPushFront函数

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

//直接申请节点，然后修改新节点指向即可
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;

*pphead = newnode;
}

解析：

功能：在链表头部插入一个新节点。参数同样是一个二级指针和新节点的数据
头插比较简单，只需将新申请的节点的 next 指针指向链表头结点，然后让指向链表头结点的指针指向新节点即可。

5.SLTPopBack函数

//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);

//只有一个节点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//两个及以上节点的情况
//申请两个节点用于指向尾节点和倒数第二个节点
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;

while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}

//销毁尾结点，然后让倒数第二个节点next指向空
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}

解析：

功能：删除链表的最后一个节点，参数为一个二级指针
首先断言，不能传空指针并且链表不能为空
尾删也要分两种情况，因为如果只要一个节点，那么就不需要找倒数第二个节点。所以分为链表只有一个节点的情况和有多个节点的情况
只有一个节点，那么我们直接 free 掉该节点，然后让指向头结点的指针置空。多个节点，那么我们就需要找到最后一个节点 ptail 以及倒数第二个节点 prev，使用while循环即可，只要ptail 的下一个节点为空就跳出循环，此时 prev 为倒数第二个节点，然后释放掉最后一个节点，修改倒数第二个节点的next指针即可。

6.SLTPopFront函数

//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);

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

free(*pphead);

*pphead = next;
}

解析：

功能：删除链表的头部节点
因为参数 *pphead 就是指向链表的头结点，因此删除简单，先创建一个next指针保存头结点的下一个节点，然后释放掉头节点，更改 *pphead 的指向即可

7.SLTFind函数

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);

SLTNode* pcur = phead;

while (pcur)
{
//找到了
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}

//没找到
return NULL;
}

解析：

功能：查找数据为 x 的节点，返回该节点的地址。
因为查找操作不会影响头指针 phead，因此参数为一级指针即可
查找很简单，循环遍历链表，让 pcur 一直往后走，直到找到存储 x 的节点，返回该节点，没找到就返回空指针

8.SLTInsert函数

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

//如果指定位置是头结点
if (*pphead == pos)
{
//头插
SLTPushFront(pphead, x);
}
else
{
//新节点
SLTNode* newnode = SLTBuyNode(x);
//prev用于找到pos前一个节点
SLTNode* prev = *pphead;

while (prev->next != pos)
{
prev = prev->next;
}

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

解析：

功能：在指定位置之前插入数据，参数为头指针地址、指定位置（用SLTFind函数确定）、需插入的数据x。
首先断言，头指针和pos指针都不能为空，也就是链表不能为空
然后，也分两种情况，因为如果指定位置刚好是头结点，那么只需要使用头插函数即可。如果指定位置不是头结点，我们就需要找到 pos 指向的结点的前一个节点。定义一个指针变量 prev，让它从头往后找，只要它的 next 指针不是 pos，那么就继续往下个节点走，直到找到pos的前一个节点。
找到之后，让 prev 的 next 指针指向新节点，再让新节点的 next 指针指向pos就完成了在指定位置前插入数据。

7.SLTInsertAfter函数

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);

SLTNode* newnode = SLTBuyNode(x);
//先让newnode的next指向下一个节点
newnode->next = pos->next;
//再修改pos的next指针
pos->next = newnode;
}

解析：

功能：在指定位置之后插入数据。
因为受影响的节点只有pos指向的节点，所以只需要传pos指针和需要增加的数据 x 即可。
pos指针使用SLTFind函数指定即可
实现简单，注意顺序即可，将新节点的next指针指向pos节点的下一个节点，然后让pos指针的next指针指向新节点即可。

8.SLTErase函数

//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);

//如果pos位置是第一个位置
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
}
else
{
//找到pos前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

//释放
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

解析：

功能：删除指定位置的节点。
参数需用到头节点和pos指向节点
也要分两种情况，因为如果需删除节点刚好是头结点，直接头删即可，如果不是头结点，则需要找到指定位置的前一个节点，老套路，找到之后，先修改 prev 的next指针，然后释放pos指向的节点。

9.SLTEraseAfter函数

//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);

SLTNode* del = pos->next;

//让pos指向它之后的之后的数据
pos->next = pos->next->next;

free(del);
del = NULL;
}

解析：

功能：删除pos位置后一个节点
只需要pos指针即可
实现简单，先保存需删除的节点地址，然后改变pos的next指针指向，最后释放掉 del 即可。

10.SListDestroy函数

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

//循环销毁链表
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}

//记得将头指针指置空
*pphead = NULL;
}

解析：

功能：销毁整个链表
断言确保链表不为空
创建pcur循环遍历链表，只要pcur不为空，释放该空间。
最后记得将头指针置空

五、SList.c文件完整代码

#include "SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;

//循环打印
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}

printf("NULL\n");
}

//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{
//申请一个节点
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}

//赋值
node->data = x;
node->next = NULL;

return node;
}

//尾插
//因为要修改plist本身，因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//断言pphead不能为空指针
assert(pphead);
//申请新节点
SLTNode* newnode = SLTBuyNode(x);

//如果pphead指向的第一个节点就是空指针
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾结点
SLTNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}

//头插
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)
{
free(*pphead);
*pphead = NULL;
}
else
{
//两个及以上节点的情况
//申请两个节点用于指向尾节点和倒数第二个节点
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;

while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}

//销毁尾结点，然后让倒数第二个节点next指向空
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}

//头删
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;
}

//没找到
return NULL;
}

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

//如果指定位置是头结点
if (*pphead == pos)
{
//头插
SLTPushFront(pphead, x);
}
else
{
//新节点
SLTNode* newnode = SLTBuyNode(x);
//prev用于找到pos前一个节点
SLTNode* prev = *pphead;

while (prev->next != pos)
{
prev = prev->next;
}

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

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);

SLTNode* newnode = SLTBuyNode(x);
//先让newnode的next指向下一个节点
newnode->next = pos->next;
//再修改pos的next指针
pos->next = newnode;
}

//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);

//如果pos位置是第一个位置
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
}
else
{
//找到pos前一个节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

//释放
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);

SLTNode* del = pos->next;

//让pos指向它之后的之后的数据
pos->next = pos->next->next;

free(del);
del = NULL;
}

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

//循环销毁链表
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}

//记得将头指针指置空
*pphead = NULL;
}

六、使用演示

不完全演示：

#include "SList.h"

void SListTest1()
{
//指针要初始化为空
SLTNode* plist = NULL;
    
    //尾插
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushBack(&plist, 5);
printf("尾插：");
SLTPrint(plist);

    //头插
SLTPushFront(&plist, 11);
SLTPushFront(&plist, 12);
SLTPushFront(&plist, 13);
SLTPushFront(&plist, 14);
SLTPushFront(&plist, 15);
printf("头插：");
SLTPrint(plist);

    //尾删
SLTPopBack(&plist);
printf("尾删：");
SLTPrint(plist);

    //头删
SLTPopFront(&plist);
printf("头删：");
SLTPrint(plist);

    //指定位置之前插入数据
SLTInsert(&plist, SLTFind(plist, 2), 66);
printf("在2的前面插入66：");
SLTPrint(plist);

    //删除指定位置数据
SLTErase(&plist, SLTFind(plist, 66));
printf("删除66：");
SLTPrint(plist);

    //销毁链表
SListDestroy(&plist);
printf("销毁：");
SLTPrint(plist);
}

int main()
{
SListTest1();

return 0;
}

运行结果：

总结

以上就是本文的全部内容，感谢支持。

原文地址：https://blog.csdn.net/x_p96484685433/article/details/142557783

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

上一篇：物联网（一）——CMC特刊推荐
下一篇：naocs注册中心，配置管理，openfeign在idea中实现模块间的调用，getway的使用

Golang | Leetcode Golang题解之第452题用最少数量的箭引爆气球
Golang | Leetcode Golang题解之第452题用最少数量的箭引爆气球
阅读更多2024-10-03
图解大模型计算加速系列：vLLM源码解析2，调度器策略(Scheduler)
在本文中，我们会详细解读调度器（Scheduler）全部细节；在下一篇文章中，我们会详细解读块管理（blockmanager）的全部细节，并以parallel sampling，beam search
阅读更多2024-10-03
开源软件简介
各大软件供应商传统的对外封锁源代码的运营模式虽说有积极的一面，比如可以维护开发商的利益，使其可以持续地维护进一步开发的能力，以及可以保护软件商及客户的私密信息等等，但凡事都有两面，其局限性也越发明显，
阅读更多2024-10-03
Linux基础命令fsck详解
fsck（File System Consistency Check）是一个用于检查和修复 Linux 文件系统的工具。它能够识别文件系统中的错误并尝试修复它们。以下是fsck命令的详细参数和使用示例
阅读更多2024-10-03
实时音频示波器与频率响度显示软件
这个Python程序使用 Python 的 `PyAudio` 和 `Matplotlib` 库实现了一个实时音频示波器，并能够实时显示音频的频率和响度。程序会从麦克风采集音频数据，进行 FFT 变换
阅读更多2024-10-03
AMD GPU推理：三步让你了解AI推理的游戏规则
我们常听到“AI推理”这个词，但很多朋友可能只了解个大概。如果你对AI有基本的认识，可能会好奇：AMD的GPU怎么在推理中大展拳脚？它跟常见的NVIDIA相比又如何？今天，我们就来聊聊这个问题。你可能
阅读更多2024-10-03
某微商代理商补货商城系统存在任意文件读取漏洞
【代码】某微商代理商补货商城系统存在任意文件读取漏洞。
阅读更多2024-10-03
「Java开发指南」如何用MyEclipse为iPhone搭建Spring应用程序？
本教程将介绍如何用MyEclipse为iPhone搭建Spring应用程序，欢迎下载最新版IDE体验！
阅读更多2024-10-03
PYTHON实现HTTP request的一些有用的函数
我们知道，当需要设计一个程序和服务器进行交互时，往往会用到HTTP的request，即服务器有一个对外接口REST API，因此当向服务器发送符合格式要求的HTTP request时，服务器会给出响应
阅读更多2024-10-03
招联金融秋招内推2025
直接扫下方二维码，或点击内推官网https://wecruit.hotjob.cn/SU61025e262f9d247b98e0a2c2/mc/position/campus，使用内推码 igcefb
阅读更多2024-10-03

数据结构之链表（1），单链表

前言

一、什么是链表

1.概念

2.节点

3.链表的性质

4.与顺序表的对比

二、链表的分类

三、单链表

四、单链表的实现

1.SList.h文件

2.SList.c文件

1.SLTPrint函数

2.SLTBuyNode函数

3.SLTPushBack函数

4.SLTPushFront函数

5.SLTPopBack函数

6.SLTPopFront函数

7.SLTFind函数

8.SLTInsert函数

7.SLTInsertAfter函数

8.SLTErase函数

9.SLTEraseAfter函数

10.SListDestroy函数

五、SList.c文件完整代码

六、使用演示

总结

相关文章