数据结构3.链表

目录

 

1.链表的概念及结构

2.链表的分类

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

3.链表的实现

1.无头单向非循环链表

2.双向带头循环链表

4.顺序表和链表的区别


 

1.链表的概念及结构

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

20bd571bb7714a46a48e9a40c1faee6c.png

现实中 数据结构中

1e4de82376c243fb854495c0e56863ec.jpeg

注意:

1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

 

假设在32位系统上,结点中值域为int类型,则一个节点的大小为8个字节,则也可能有下述链表:

7ff321c5f1a34a20bafe5f91256306cf.jpeg

2.链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

1.单向或者双向

206bc742c9e547fd8df220e9ea528148.jpeg

2.带头或者不带头

哨兵位:不存储有效数据。

优势:不用探空(空就是空指针的意思)

88742977b03748b097429e9c3edd0b2c.jpeg

3.循环或者非循环

6960bee42c004bd7ae583038f547ffba.jpeg

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

6b45f22e533e4f4ca43be37281a28d07.jpeg

1.无头单向循环链表:结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表:结构最复杂,一般用在单独存储数据,实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

3.链表的实现

1.无头单向非循环链表

SList.h

b930f00f04b84da9b5b61256c9a5aaee.png

SList.c

3a4e0a95f206476d86349e9b09f4a0b9.png

2.双向带头循环链表

List.h

1dd00b4be32346aaa7805d977960fcc8.png

List.c

ac907ea57b984331ba9163850a053b2f.png

4.顺序表和链表的区别

1.存储空间:顺序表物理上一定连续;链表逻辑上连续,但物理上不一定连续。

2.随机访问:顺序表支持O(1);链表不支持:O(N)

3.任意位置插入或者删除元素:顺序表可能需要搬移元素,效率低;链表只需要修改指针指向。

4.插入:顺序表动态顺序表,空间不够时需要扩容;链表没有容量的概念。

5.应用场景:顺序表元素高效存储+频繁访问;链表任意位置插入或删除频繁。

6.缓存利用率:顺序表高;链表低

备注:缓存利用率参考存储体系结构以及局部原理性。

如图:转载@亚撒西带师

03fa519897df4bbdbfc0e69011b90b1a.png

 

 

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

A054-基于Spring Boot的青年公寓服务平台

🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…

paimon的四种changelog模式(2)-none模式

# 请先了解input模式 环境创建 CREATE CATALOG fs_catalog WITH (typepaimon,warehousefile:/data/soft/paimon/catalog );USE CATALOG fs_catalog;drop table if exists t_changelog_none ;CREATE TABLE t_changelog_none (age BIGINT,money BIGINT,hh STRING,PRIMARY KEY (h…

【CSS in Depth 2 精译_064】10.3 CSS 中的容器查询相对单位 + 10.4 CSS 容器样式查询 + 10.5 本章小结

当前内容所在位置(可进入专栏查看其他译好的章节内容) 【第十章 CSS 容器查询】 ✔️ 10.1 容器查询的一个简单示例 10.1.1 容器尺寸查询的用法 10.2 深入理解容器 10.2.1 容器的类型10.2.2 容器的名称10.2.3 容器与模块化 CSS 10.3 与容器相关的单位 ✔…

CSS笔记(二)类名复用

这里我通过两张不同位置的卡片来实现效果 代码 <!DOCTYPE html> <html><head><style>/*设置画布*/body{/* 方便排列与对齐*/display: flex; /*画布布满整个窗口*/height: 100vh;/*水平居中*/justify-content: center;/*垂直居中*/align-items: cente…

常用函数的使用错题汇总

#include <iostream> #include <fstream> #include <string>int main() {std::ifstream fin("example.txt"); // 创建 ifstream 对象并打开文件// 检查文件是否成功打开if (!fin) {std::cerr << "Error opening file!" << s…

【树莓派5】移动热点获取树莓派IP并初次登录SSH

本篇文章包含的内容 1 打开系统热点2 烧录系统设置3 配置 MobaXterm4 初次启动树莓派配置选项4.1 换源4.2 更新软件包4.3 安装vim编辑器4.4 更改CPU FAN温度转速 Windows版本&#xff1a;Windows11 24H2树莓派&#xff1a;树莓派5&#xff0c;Raspberry Pi 5SSH软件&#xff1a…

分布式调用 - 服务间的远程调用RPC

文章目录 导图PreRPC 概述RPC 调用过程RPC 动态代理1. 接口定义 (SeverProvider)2. 实现类 (ServerProviderImpl)3. 动态代理类 (DynamicProxy)4. 客户端 (Client)5. 代码工作流程6. 总结和注意点7. 结果输出8. 小结 RPC 序列化1. JSON (JavaScript Object Notation)2. Hessian…

基于Matlab湍流对高斯光束传播影响的模拟与评估

随着光学通信与激光技术的不断发展&#xff0c;湍流对光束传播的影响已成为研究中的重要课题。特别是在大气湍流条件下&#xff0c;光束的传播会受到相位扰动的影响&#xff0c;从而导致光束质量的恶化、能量损失及光束中心的偏移等问题。本文基于高斯光束模型&#xff0c;提出…

19. C++STL 5(深入理解vector,vector的模拟实现,二维动态数组)

⭐本篇重点&#xff1a;vector深入理解和模拟实现 ⭐本篇代码&#xff1a;c学习/09.vector-2 橘子真甜/c-learning-of-yzc - 码云 - 开源中国 (gitee.com) 目录 一. 深入理解vector 二. 使用模板模拟实现vector &#xff08;包含迭代器&#xff09; 2.1 模拟vector类的成员…

PDF文件怎么加密?如何给pdf文档加密码保护?(2025全新科普)

PDF文件因其跨平台兼容性和格式稳定性&#xff0c;成为广泛使用的文档格式。 然而&#xff0c;随着信息泄露风险的增加&#xff0c;如何保护PDF文件的安全成为了一个重要问题。 本文将介绍几种2025年最新的PDF文件加密方法&#xff0c;帮助用户为PDF文档添加密码保护。 一、使…

服务器端使用国密证书

服务器端国密证书nignx代理配置 1.资料准备 从gmssl实验室下载已经编译完成的gmssl包 地址&#xff1a;https://www.gmssl.cn/gmssl/index.jsp 下载位置&#xff1a; 保证openssl支持国密算法&#xff0c;ssl 1.1.1 已支持&#xff0c;检查一下最佳 准备一个支持国密的ngin…

第04章_运算符(基础)

1. 算术运算符 算术运算符主要用于数学运算&#xff0c;其可以连接运算符前后的两个数值或表达式&#xff0c;对数值或表达式进行加&#xff08;&#xff09;、减&#xff08;-&#xff09;、乘&#xff08;*&#xff09;、除&#xff08;/&#xff09;和取模&#xff08;%&am…

如何寻找适合的HTTP代理IP资源?

一、怎么找代理IP资源&#xff1f; 在选择代理IP资源的时候&#xff0c;很多小伙伴往往将可用率作为首要的参考指标。事实上&#xff0c;市面上的住宅IP或拨号VPS代理IP资源&#xff0c;其可用率普遍在95%以上&#xff0c;因此IP可用率并不是唯一的评判标准 其实更应该关注的…

FinalShell工具数据备份升级、密码解密方法

前言 FinalShell 作为国产的服务器管理工具和远程终端软件。一个一体化的运维工具&#xff0c;在国内运维人员中还是比较受欢迎。它整合了多个常用功能&#xff0c;界面友好&#xff0c;使用方便。不过它是一个闭源的商业软件&#xff0c;虽然提供免费版本&#xff0c;但部分高…

华三(HCL)和华为(eNSP)模拟器共存安装手册

接上章叙述&#xff0c;解决同一台PC上同时部署华三(HCL)和华为(eNSP&#xff09;模拟器。原因就是华三HCL 的老版本如v2及以下使用VirtualBox v5版本&#xff0c;可以直接和eNSP兼容Oracle VirtualBox&#xff0c;而其他版本均使用Oracle VirtualBox v6以上的版本&#xff0c;…

0.shell 脚本执行方式

1.脚本格式要求 &#x1f951;脚本以 #!/bin/bash 开头 &#x1f966; 脚本要有可执行权限 2.执行脚本的两种方式 &#x1f96c; 方式1&#xff1a;赋予x执行权限 &#x1f952; ​​​​​​​方式2&#xff1a; sh执行 ​​​​​​​

EXCEL截取某一列从第一个字符开始到特定字符结束的字符串到新的一列

使用EXCEL中的公式进行特定截取 假设列A是一组产品的编码&#xff0c;我们需要的数据是“-”之前的字段。 我们需要在B1单元格输入公式“LEFT(A1,SEARCH("-",A1)-1)”然后选中B1至B4单元格&#xff0c;按“CTRLD”向下填充&#xff0c;就可以得出其它几行“-”之前的…

ComfyUI绘画|图生图工作流搭建

今天先分享到这里~ ComfyUI绘画|关于 ComfyUI 的学习建议

Css—实现3D导航栏

一、背景 最近在其他的网页中看到了一个很有趣的3d效果&#xff0c;这个效果就是使用css3中的3D转换实现的&#xff0c;所以今天的内容就是3D的导航栏效果。那么话不多说&#xff0c;直接开始主要内容的讲解。 二、效果展示 三、思路解析 1、首先我们需要将这个导航使用一个大…

书生大模型实战营第四期-入门岛-4. maas课程任务

书生大模型实战营第四期-入门岛-4. maas课程任务 任务一、模型下载 任务内容 使用Hugging Face平台、魔搭社区平台&#xff08;可选&#xff09;和魔乐社区平台&#xff08;可选&#xff09;下载文档中提到的模型&#xff08;至少需要下载config.json文件、model.safetensor…