链表的详解

1.单链表

1.1概念与结构

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

现实中数据结构： 

1.1.1结点

与顺序表不同的是，链表里的每节“车厢 ”都是独立申请下来的空间，我们称之为“结点”。

  • 结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

 图中指针变量pList保存的是第一个结点的地址，我们称pList此时“指向”第一个结点，如果我们希望pList“指向”第二个结点时，只需要修改pList保存的内容为第二个的地址。

链表中每个结点都是独立申请的（需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

1.1.2链表的性质

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

结构体代码：

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

当我们要保存一个整形数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整形数组，也需要保存下一个结点的地址。

1.2实现单链表

SList.h

#pragma once
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"//定义链表的结构
typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SL;//打印
void SLTPrint(SL* phead);//插入
void SLTPushBack(SL** pphead, SLDataType x);//尾插
void SLTPushFront(SL** pphead, SLDataType x);//头插//删除
void SLTPopBack(SL** pphead);//尾删
void SLTPopFront(SL** pphead);//头删//查找
SL* SLTFind(SL* phead, SLDataType x);//在指定位置之前插⼊数据
void SLTInsert(SL** pphead, SL* pos, SLDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SL* pos, SLDataType x);//删除pos结点
void SLTErase(SL** pphead, SL* pos);
//删除pos之后的结点
void SLTEraseAfter(SL* pos);
//销毁链表
void SListDestroy(SL** pphead);

功能1：打印

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

功能2：申请新的结点

SL* SLTBuyNode(SLDataType x)
{SL* node = (SL*)malloc(sizeof(SL));if (node == NULL){perreor("malloc fail");exit(1);}node->data = x;node->next = NULL;return node;
}

功能3：插入新的结点

void SLTPushBack(SL** pphead, SLDataType x)//尾插
{assert(pphead);SL* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SL* pcur = *pphead;//找尾结点while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
void SLTPushFront(SL** pphead, SLDataType x)//头插
{assert(pphead);SL* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

功能4：删除结点

void SLTPopBack(SL** pphead)//尾删
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SL* pcur = *pphead;SL* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;free(pcur);pcur = NULL;}
}
void SLTPopFront(SL** pphead)//头删
{assert(pphead && *pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}

功能5：查找

SL* SLTFind(SL* phead, SLDataType x)
{assert(phead);SL* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

功能6：在指定位置之前插入数据

void SLTInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SL* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}else{SL* newnode = SLTBuyNode(x);SL* pcur = *pphead;while (pcur->next == pos){pcur = pcur->next;}newnode->next = pcur->next;pcur->next = newnode;}
}

 功能7：在指定位置之后插入数据

void SLTInsertAfter(SL* pos, SLDataType x)
{assert(pos);SL* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

 功能8：删除pos结点

void SLTErase(SL** pphead, SL* pos)
{assert(pphead && *pphead);assert(pos);if (pos = *pphead){SL* next = (*pphead)->next;free(*pphead);*pphead = next;}else{SL* pcur = *pphead;while (pcur->next != pos);{pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

 功能9：删除pos之后的结点

void SLTEraseAfter(SL* pos)
{assert(pos && pos->next);SL* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

 功能10：销毁

void SListDestroy(SL** pphead)
{assert(pphead && *pphead);SL* pcur = *pphead;while (pcur){SL* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

1.3链表的分类

链表的结构非常多样，以下有8种链表结构：

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

  1. 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

2.双向链表

2.1概念与结构

带头 链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”

2.2实现双向链表

LIst.h

#pragma once
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#include"stdbool.h"//定义双向链表节点的结构
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//为了保持接口的一致性，优化接口都为一级指针
//初始化
LTNode* LTInit();//销毁
void LTDesTroy(LTNode** pphead);//打印
void LTPrint(LTNode* phead);//插入
//第一个参传一级还是二级，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如何不发生改变，pphead不会影响实参，传一级
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//删除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//找x值
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);

功能1：创建新的结点

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

功能2：初始化

LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

功能3：插入结点

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)//头插
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

功能4：打印

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

 功能5：判断链表是否为空

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next = phead;//正确说明链表为空，不正确说明链表不为空
}

功能6：删除结点

void LTPopBack(LTNode* phead)//尾删
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
void LTPopFront(LTNode* phead)//头删
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;LTNode* prev = del->next;phead->next = prev;prev->prev = phead;free(del);del = NULL;
}

 功能7：找x值

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

 功能8：在pos位置之后插入结点

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

功能9：删除指定位置结点

void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

功能10：销毁

void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead);{LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;pcur = NULL;
}

3.顺序表与链表的分析

不同点顺序表链表（单链表）
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容和空间浪费没有容量概念，按需申请释放，不存在空间浪费
应用场景元素高效存储+频繁访问任意位置高效插入和删除

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

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

相关文章

项目实战——高并发内存池

项目实战——高并发内存池

一.项目介绍 本项目——高并发内存池，是通过学习并模仿简化 google 的一个开源项目 tcmalloc ，全称 Thread-Caching Malloc，即线程缓存的malloc，模拟实现了一个自己的高并发内存池，用于高效的多线程内存管理&#xff…
阅读更多...
【魅力golang】之-通道

【魅力golang】之-通道

昨天发布了golang的最大特色之一--协程，与协程密不可分的是通道（channel），用来充当协程间相互通信的角色。通道是一种内置的数据结构，所以才造就了golang强大的并发能力。今天风云来爬一爬通道的详细用法。 通道在gol…
阅读更多...
【论文复现】农作物病害分类(Web端实现)

【论文复现】农作物病害分类(Web端实现)

📝个人主页🌹：Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀ 农作物病害分类 概述演示效果核心逻辑使用方式部署方式 概述 农作物病害是国家粮食安全的一个主要威胁，是决定农作物产量和质量的…
阅读更多...
Linux网络——网络基础

Linux网络——网络基础

Linux网络——网络基础 文章目录 Linux网络——网络基础一、计算机网络的发展背景1、网络的定义（1） 独立模式（2）网络互联 2、局域网 LAN3、广域网 WAN4、比较局域网和广域网5、扩展 —— 域域网和互联网 二、协议1、协议的概念2、…
阅读更多...
Reactor

Reactor

文章目录 正确的理解发送double free问题 1.把我们的reactor进行拆分2.链接管理3.Reactor的理论 listensock只需要设置_recv_cb，而其他sock，读，写，异常 所以今天写nullptr其实就不太对，添加为空就没办法去响应事件 获…
阅读更多...
Linux -- 线程的优点、pthread 线程库

Linux -- 线程的优点、pthread 线程库

目录 线程的优点 pthread 线程库 前言 认识线程库 简单验证线程的独立栈空间 线程的优点 与进程之间的切换相比，线程之间的切换需要操作系统做的工作要少得多。 调度进程时，CPU 中有一个 cache（缓存，提高运行效率&#xff0…
阅读更多...
centos权限大集合，覆盖多种权限类型，解惑权限后有“. + t s”问题！

centos权限大集合，覆盖多种权限类型，解惑权限后有“. + t s”问题！

在 CentOS 系统中，权限管理是操作系统的核心功能之一，确保不同用户和进程对文件、目录以及设备的访问被合理控制。 权限系统主要包括传统的 Unix 权限模型、特殊权限（SetUID、SetGID、Sticky 位）和更精细的访问控制列表&#xff…
阅读更多...
pyinstaller打包资源文件和ini配置文件怎么放

pyinstaller打包资源文件和ini配置文件怎么放

1.如果出现无法成功完成操作，因为文件包含病毒或潜在的垃圾软件，说明你的版本太高，更换pyinstaller版本。 pip install pyinstaller6.2.02.一开始打包的时windows下尽量选择打成文件夹的并且要是带命令行窗口的，容易查看错误。 …
阅读更多...
五种msvcr100.dll丢失的解决方法，有效修复msvcr100.dll丢失错误！跟msvcr100.dll错误问题说拜拜！

五种msvcr100.dll丢失的解决方法，有效修复msvcr100.dll丢失错误！跟msvcr100.dll错误问题说拜拜！

在日常电脑使用过程中，尤其是运行某些应用程序或游戏时，可能会遇到“msvcr100.dll丢失”的错误提示。这个动态链接库（DLL）文件是Microsoft Visual C Redistributable for Visual Studio 2010的一部分，对于许多程序的正…
阅读更多...
【前端】入门指南：Vue中使用Node.js进行数据库CRUD操作的详细步骤

【前端】入门指南：Vue中使用Node.js进行数据库CRUD操作的详细步骤

💥 欢迎来到我的博客！很高兴能在这里与您相遇！ 首页：GPT-千鑫 – 热爱AI、热爱Python的天选打工人，活到老学到老！！！导航 - 人工智能系列：包含 OpenAI API Key教程, 50个…
阅读更多...
【网络安全产品大调研系列】1. 漏洞扫描

【网络安全产品大调研系列】1. 漏洞扫描

1. 为什么会出现漏扫技术？ 每次黑客攻击事件进行追溯的时候，根据日志分析后，我们往往发现基本都是系统、Web、 弱口令、配置这四个方面中的其中一个出现的安全问题导致黑客可以轻松入侵的。 操作系统的版本滞后，没有更新补丁&am…
阅读更多...
Java爬虫：速卖通（AliExpress）商品评论获取指南

Java爬虫：速卖通（AliExpress）商品评论获取指南

引言 在当今的电商时代，商品评论对于消费者决策有着举足轻重的影响。速卖通（AliExpress），作为全球知名的在线零售平台之一，拥有海量的商品评论数据。对于商家而言，能够高效地获取这些评论数据，…
阅读更多...
AIDD - 探索语言模型在药物分子生成方面的应用

AIDD - 探索语言模型在药物分子生成方面的应用

AIDD - 探索语言模型在药物分子生成方面的应用 今天给大家讲一篇2024年10月在nature communications上发表的一篇关于分子生成的文章。现有的分子生成方法中往往只关注药物的特定属性，导致其适用性受限。因此作者提出了TamGen方法，用于针对特定靶点的分子…
阅读更多...
【每日学点鸿蒙知识】AVCodec、SmartPerf工具、web组件加载、监听键盘的显示隐藏、Asset Store Kit

【每日学点鸿蒙知识】AVCodec、SmartPerf工具、web组件加载、监听键盘的显示隐藏、Asset Store Kit

1、AVCodec 硬解咨询？ 在做视频播放硬解适配，这是 demo：https://gitee.com/openharmony-sig/ohos_videocompressor/blob/master/videoCompressor/src/main/cpp/video/decoder/VideoDec.cpp 请问： int32_t VideoDec::SetOutputS…
阅读更多...
怎么设置电脑密码？Windows和Mac设置密码的方法

怎么设置电脑密码？Windows和Mac设置密码的方法

为电脑设置密码是保护个人信息安全的重要措施。无论是Windows系统还是MacOS系统，设置密码的步骤都相对简单，但需要根据不同的操作系统选择不同的方法。 一、Windows系统电脑密码设置 方法一：通过控制面板设置账户密码 点击桌面左下角的“开…
阅读更多...
谷歌浏览器的网络安全检测工具介绍

谷歌浏览器的网络安全检测工具介绍

作为全球最受欢迎的浏览器之一，谷歌浏览器不仅提供了快速、便捷的浏览体验，还内置了一系列强大的网络安全检测工具，帮助用户识别潜在的网络威胁，保护个人隐私和数据安全。本文将详细介绍谷歌浏览器中的几项关键网络安全检测功能&a…
阅读更多...
一个比RTK或redux更轻量级更易使用的 React 第三方状态管理工具库的配置与使用

一个比RTK或redux更轻量级更易使用的 React 第三方状态管理工具库的配置与使用

本文由作者 Samdy_Chan 原创，未经作者同意，请勿随意转载！ 使用轻量级第三方的 React 状态管理库 zustand 管理共享状态数据 在 react 框架应用中，开发者应该大多数都是采用 redux 状态管理工具库来管理应用的共享状态数据，但用过 redux 的人都知道，其配置和使用相当复杂…
阅读更多...
菜鸟带新鸟——基于EPlan2022的部件库制作

菜鸟带新鸟——基于EPlan2022的部件库制作

首先，我们需要了解一些概念： Eplan的部件制作内容 以上内容是制作一个完整的部件所需要的。如果公司要求没有那么严格，我们就可以制作1-4级的内容就可以满足日常的使用啦！ 部件的创建方式 部件创建方式有4类： 1、单…
阅读更多...
Charles安装证书过程（手机）

Charles安装证书过程（手机）

背景：使用模拟器抓包时，发现https请求无法抓取，需要安装相应证书。我自己是因为模拟器升级了安卓7，发现之前安装的证书无效了，需要重新安装。 参考博客：夜神模拟器12Charles进行Https抓包_模拟器抓包ssl-C…
阅读更多...
Windows、CentOS环境下搭建自己的版本管理资料库：GitBlit

Windows、CentOS环境下搭建自己的版本管理资料库：GitBlit

可以搭建属于公司内部或者个人的Git服务器，方便程序代码及文档版本管理。 官网：http://www.gitblit.com/ Windows环境下安装 提前已经安装好了JDK。 官网下载Windows版的GitBlit。 将zip包解压到自己想要放置的文件夹下。 建立版本库路径&#xff0c…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023