数据结构之手撕链表（讲解➕源代码）

0.引言

我们在学习过顺序表之后，会发现两点不是很优秀的操作：
1.顺序表的头插和中间的插入：
        非常麻烦，需要不断的覆盖数据。
2.动态开辟空间：
        a.一般动态开辟的空间都是以2倍的形式开辟，当我们已经开辟了100个空间，并且存满了，此时我们还需要存放5个数据，那么就又需要开辟200个空间了，我们存放5个数据之后，还剩余了195个空间没有放数据，这也就导致了空间的浪费。
        b. 而我们开辟新空间，拷贝数据，释放旧空间还会有一定的消耗。

注意⚠️⚠️⚠️：
        我们在申请空间的时候必须要主动给它释放掉，因为申请空间的时候，是在堆上申请的，这段空间不会随着程序的结束而自然释放掉，所以要在我们程序结束之前，主动释放掉这段空间。

那有没有一种结构会很简便呢？答案肯定是有的，就是我们本次要讲解的链表。


1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的 。也就是说链表的物理结构不连续，但逻辑结构连续。

我们通常定义一个结构体来表示链表的节点，结构体内部要包括节点的值和指向下一个节点的指针。

链表开始的节点称作：头节点，通常用head表示；

链表末尾的节点称作：尾结点，通常用tail表示；

其余节点称作：中间节点。

2.链表的逻辑模型

如图：在逻辑模型，可以看出它们是一个接着一个的，在逻辑上连续。

3.链表的物理模型

如图：在物理模型中，我们看到每个节点的地址都不是连续的，但是通过指针链接起来了。

 4.链表的分类

4.1 单向链表

        

4.2 双向链表

4.3 带头单向链表（带哨兵位）

4.4带头双向链表（带哨兵位）

4.5循环单链表

4.6循环双向链表

4.7带头循环单链表

4.8带头循环双向链表

5. 单链表的实现（接口实现代码）

5.1单链表的定义

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

5.3单链表的销毁

void SLT_Destroy(SLTNode*phead)//销毁
{while (phead != NULL){SLTNode *over = phead->next;free(phead);phead = over;}
}

5.4单链表的动态申请一个节点空间

SLTNode* BuySListNode(SLTDataType x) //创造新节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

5.5单链表的头插头删

void SLTPushFront(SLTNode** pphead, SLTDataType x) //头插
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopFront(SLTNode** pphead) //头删
{// 空assert(*pphead);// 非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

5.6单链表的尾插尾删

void SLTPushBack(SLTNode** pphead, SLTDataType x) //尾插
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){// 改变的结构体的指针，所以要用二级指针*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}// 改变的结构体，用结构体的指针即可tail->next = newnode;}
}void SLTPopBack(SLTNode** pphead) //尾删
{// 1、空assert(*pphead);// 2、一个节点// 3、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

5.7单链表的在pos位置之前的插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//pos之前插入
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

5.8单链表的在pos位置之后的插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)//在pos之后插入
{assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;
}

5.9单链表的删除pos位置的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}
}

5.10单链表的删除pos位置之后的节点

void SLTEraseAfter(SLTNode* pos)
{assert(pos);// 检查pos是否是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

5.11单链表的查找

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

6.带头双向循环链表的实现（接口实现代码）

6.1带头双向循环链表的定义

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev; //前驱LTDataType data;struct ListNode* next; //后继
}ListNode;

6.2带头双向循环链表的初始化

ListNode* ListInit() //初始化链表
{ListNode *head = (ListNode*) malloc(sizeof (ListNode));if(head ==  NULL){perror("初始化开辟空间失败");exit(-1);}head->data = -1;head->prev = head;head->next = head;return head;
}

6.3带头双向循环链表的销毁

void ListDestory(ListNode* pHead) //销毁
{int len = ListSize(pHead) + 1;while (len--)ListPopFront(pHead);
}

6.4带头双向循环链表的打印

void ListPrint(ListNode* phead) //打印
{assert(phead);ListNode *phead_next = phead->next;printf("phead <-> ");while(phead_next != phead){printf("%d <-> ",phead_next->data);phead_next = phead_next->next;}printf("phead\n");
}

6.5带头双向链表的增加节点

ListNode* BuyListNode(LTDataType x) //增加节点
{ListNode *newnode = (ListNode*) malloc(sizeof (ListNode));if(newnode == NULL){perror("增加节点开辟空间失败");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

6.6带头双向循环链表的在pos之前插入

void ListInsert(ListNode* pos,LTDataType x)//在pos位置之前插入
{assert(pos);ListNode *newnode = BuyListNode(x);ListNode *pos_prev = pos->prev;pos_prev->next = newnode;newnode->prev = pos_prev;newnode->next = pos;pos->prev = newnode;
}

6.7带头双向循环链表删除pos位置

void ListErase(ListNode* pos)//删除pos位置的节点
{assert(pos);ListNode *pos_next = pos->next;ListNode *pos_prev = pos->prev;pos_prev->next = pos_next;pos_next->prev = pos_prev;free(pos);
}

6.8带头双向循环链表的尾插尾删

void ListPushBack(ListNode* phead,LTDataType x)//尾插
{assert(phead);ListInsert(phead,x);
}void ListPopBack(ListNode* phead)//尾删
{assert(phead);ListErase(phead->prev);
}

6.9带头双向循环链表的头插头删

void ListPushFront(ListNode* phead,LTDataType x)//头插
{assert(phead);ListInsert(phead->next,x);
}void ListPopFront(ListNode* phead)//头删
{assert(phead);ListErase(phead->next);
}

6.10带头双向循环链表的长度求解

int ListSize(ListNode* phead)//求链表的长度
{assert(phead);int len = 0;ListNode *phead_next = phead->next;while(phead != phead_next){len++;phead_next = phead_next->next;}return len;
}

6.11带头双向循环链表的寻找某一节点

ListNode*ListFind(ListNode* phead, LTDataType num)//寻找某一个节点
{assert(phead);ListNode *find = phead->next;while(find != phead){if(find->data == num){return find;}find = find->next;}return NULL;
}

7.顺序表和链表的区别

不同点顺序表链表

存储空间上 

物理上一定连续逻辑一定连续，物理不一定

任意位置插入或者删除

元素

需要覆盖数据通过指针就能找到

插入 

动态顺序表需要扩容没有容量概念，需要一个给一个

缓存利用率

高低

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/159702.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

xml的语法

xml的语法

<!-- 1、每一个xml,有且只有一个根标签&#xff0c;所有xml标签必须写在根标签中 2、标签必须要有合闭 3、xml格式是否正确&#xff0c;可以通过浏览器打开xml。来校验xml格式是否正确 4、xml是区别大小写的 5、xml书写标签名时&#xff0c;不要出现空格等特…
阅读更多...
centos 7.9离线安装wget

centos 7.9离线安装wget

1.下载安装包 登录到wget官网上下载最新的wget的rpm安装包到本地 http://mirrors.163.com/centos/7/os/x86_64/Packages/ 2.上传安装包到服务器 3.安装 rpm -ivh wget-1.14-18.el7_6.1.x86_64.rpm 4.查看版本 wget -V
阅读更多...
集合的进阶

集合的进阶

不可变集合 创建不可变的集合 在创建了之后集合的长度内容都不可以变化 静态集合的创建在list &#xff0c;set &#xff0c;map接口当中都可以获取不可变集合 方法名称说明static list of(E …elements)创建一个具有指定元素集合list集合对象staticlist of(E…elements)创…
阅读更多...
智慧港口与无人机巡逻技术：走进未来的海上交通枢纽

智慧港口与无人机巡逻技术：走进未来的海上交通枢纽

在21世纪&#xff0c;随着全球贸易的日益繁荣&#xff0c;港口作为连接世界各地的重要交通枢纽显得尤为重要。为了提高港口的效率和安全性&#xff0c;智慧港口和无人机巡逻技术成为了最前沿的选择。其中&#xff0c;复亚智能无人机技术在智慧港口的建设和日常运营中扮演了至关…
阅读更多...
6、docker下mysql修改配置文件

6、docker下mysql修改配置文件

1、查看mysql镜像 如果没有mysql镜像则下载 docker images |grep mysql 2、查看mysql容器 docker ps |grep mysql 如果没有显示mysql容器信息&#xff0c;则创建 3、创建容器 docker run -it --name mysql-test -e MYSQL_ROOT_PASSWORDroot -p 3306:3306 -d f9653 4、在…
阅读更多...
消息队列缓存，以蓝牙消息服务为例

消息队列缓存，以蓝牙消息服务为例

前言 消息队列缓存&#xff0c;支持阻塞、非阻塞模式&#xff1b;支持协议、非协议模式 可自定义消息结构体数据内容 使用者只需设置一些宏定义、调用相应接口即可 这里我用蓝牙消息服务举例 有纰漏请指出&#xff0c;转载请说明。 学习交流请发邮件 1280253714qq.com 原…
阅读更多...
Go语言入门心法(一): 基础语法

Go语言入门心法(一): 基础语法

Go语言入门心法(一) Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言中变量认知 go语言中变量的定义: &#xff08;要想飞|先会走&#xff09;||&#xff08;翻身仗|抹遗憾 &#xff09; |&…
阅读更多...
基于IDEA集成环境---Nacos安装

基于IDEA集成环境---Nacos安装

Nacos服务器是独立安装部署的&#xff0c;因此我们需要下载最新的Nacos服务端程序&#xff0c;下载地址&#xff1a;https://github.com/alibaba/nacos。 将文件进行解压&#xff0c;得到以下内容&#xff1a; 直接将其拖入到项目文件夹下&#xff0c;便于我们一会在IDEA内部…
阅读更多...
mysql case when 不命中缓存

mysql case when 不命中缓存

case when 在sql 中非常方便数据不同维度统计&#xff0c;但是也会出现mysql 索引不命中问题&#xff0c;当多个case 出现时&#xff0c;需要提取出来到where里面优化 优化后 SELECT date(RecordTime) AS date, count( DISTINCT CASE WHEN Param 1 …
阅读更多...
什么是美体SDK？美摄美颜美体SDK对接开发指南

什么是美体SDK？美摄美颜美体SDK对接开发指南

在当今的数字世界中&#xff0c;人们对自我表达和形象展示的需求越来越高。美体SDK应运而生&#xff0c;为用户提供了一种全新的美颜美体体验&#xff0c;让每一个人都能享受到个性化的美丽与自信。 一、美体SDK的特点 轻量级&#xff1a;美体SDK体积小巧&#xff0c;不会对用…
阅读更多...
运用精益管理思想提升MES管理系统建设水平

运用精益管理思想提升MES管理系统建设水平

随着制造业的不断发展&#xff0c;MES生产管理系统已经成为了企业生产过程中不可或缺的一部分。而在MES管理系统建设过程中&#xff0c;精益管理的思想也越来越受到重视。本文将探讨如何运用精益管理的思想&#xff0c;提高MES系统的建设水平&#xff0c;以更好地服务于企业的生…
阅读更多...
Sanic​——Python函数变成API的神器

Sanic​——Python函数变成API的神器

今天给大家介绍一个超好用的框架&#xff0c;迅速将Python函数变成API&#xff0c;它就是最近越来越火的异步Web框架Sanic。 1. Sanic简介 Sanic 是 Python3.7 Web 服务器和 Web 框架&#xff0c;旨在提高性能。它允许使用 Python3.5 中添加的async/await语法&#xff0c;这使…
阅读更多...
1.Vue-在独立页面实现Vue的增删改查

1.Vue-在独立页面实现Vue的增删改查

题记 在独立页面实现Vue的增删改查&#xff0c;以下是具体的代码&#xff0c;和操作流程。 编写index.html页面 index.html文件如下&#xff1a; <!DOCTYPE html> <html> <head><title>Vue CRUD Example</title><!--在线导入vue文件-->&l…
阅读更多...
Linux系统之ip命令的基本使用

Linux系统之ip命令的基本使用

Linux系统之ip命令的基本使用 一、ip命令介绍1.1 ip命令简介1.2 ip命令的由来1.3 ip命令的安装包 二、ip命令使用帮助2.1 ip命令的help帮助信息2.2 ip命令使用帮助 三、查看网络信息3.1 显示当前网络接口信息3.2 显示网络设备运行状态3.3 显示详细设备信息3.4 查看路由表3.5 查…
阅读更多...
canvas画一个笑脸和画一个三角形

canvas画一个笑脸和画一个三角形

画一个笑脸主要用到的是画弧形的方法&#xff1a;arc&#xff0c;有五个参数&#xff1a;起始坐标&#xff0c;半径&#xff0c;弧形起始坐标&#xff0c;还有一个参数是顺时针还是逆时针。画的笑脸&#xff1a;虽然丑了点&#xff0c;但是学习了 代码&#xff1a; <!DOCTY…
阅读更多...
【Docker 内核详解】namespace 资源隔离（四）：Mount namespace Network namespace

【Docker 内核详解】namespace 资源隔离（四）：Mount namespace Network namespace

【Docker 内核详解 - namespace 资源隔离】系列包含&#xff1a; namespace 资源隔离&#xff08;一&#xff09;&#xff1a;进行 namespace API 操作的 4 种方式namespace 资源隔离&#xff08;二&#xff09;&#xff1a;UTS namespace & IPC namespacenamespace 资源隔…
阅读更多...
[23] T^3Bench: Benchmarking Current Progress in Text-to-3D Generation

[23] T^3Bench: Benchmarking Current Progress in Text-to-3D Generation

3D生成蓬勃发展&#xff0c;主流方法通过事例比较和用户调查来评价方法好坏&#xff0c;缺少客观比较指标&#xff1b;本文提出Bench&#xff0c;首次综合比较了不同生成方法&#xff1b;具体来说&#xff0c;本文设计了质量评估&#xff08;Quality Assessment&#xff09;和对…
阅读更多...
MyBatisPlus的学习项目页面

MyBatisPlus的学习项目页面

MyBatisPlus通过扫描实体类&#xff0c;并基于反射获取实体类信息作为数据库表信息 类名驼峰转下划线作为表名 名为id的字段作为主键 变量名驼峰转下划线作为表的字段名 常见注解 TableName&#xff1a;用来指定表名 Tableld&#xff1a;用来指定表中的主键字段信息 Tabl…
阅读更多...
攻防世界题目练习——Web引导模式（三）（持续更新）

攻防世界题目练习——Web引导模式（三）（持续更新）

题目目录 1. mfw2.3.4.5. 1. mfw 进去看到网页和页面内容如下&#xff1a; 看到url的参数 ?pageabout &#xff0c;我以为是文件包含什么的&#xff0c;反复试了几次&#xff0c;想用 …/…/…/…/etc/passwd &#xff0c;但是发现.似乎被过滤了&#xff0c;实在不知道怎么做…
阅读更多...
SpringCloud学习笔记-Nacos服务分级存储模型

SpringCloud学习笔记-Nacos服务分级存储模型

Nacos服务分级存储模型 一级是服务&#xff0c;例如userservice二级是集群&#xff0c;例如杭州或上海三级是实例&#xff0c;例如杭州机房的某台部署了userservice的服务器 微服务互相访问时&#xff0c;应该尽可能访问同集群实例&#xff0c;因为本地访问速度更快。当本集…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023