线性数据结构:链表 LinkList
一、前言
链表的历史
于1955-1956年,由兰德公司的Allen Newell、Cliff Shaw和Herbert A. Simon开发了链表,作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由 Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使用链表。
到 1960 年代初,链表和使用这些结构作为主要数据表示的语言的实用性已经很好地建立起来。MIT 林肯实验室的 Bert Green于 1961 年 3 月在 IRE Transactions on Human Factors in Electronics 上发表了一篇题为“用于符号操作的计算机语言”的评论文章,总结了链表方法的优点。1964 年 4 月,Bobrow 和 Raphael 的一篇评论文章“列表处理计算机语言的比较”发表在 ACM 通讯中。
二、链表数据结构
在计算机科学中,链表是数据元素的线性集合,元素的线性顺序不是由它们在内存中的物理地址给出的。它是由一组节点组成的数据结构,每个元素指向下一个元素,这些节点一起,表示线性序列。

在最简单的链表结构下,每个节点由数据和指针(存放指向下一个节点的指针)两部分组成,这种数据结构允许在迭代时有效地从序列中的任何位置插入或删除元素。
链表的数据结构通过链的连接方式,提供了可以不需要扩容空间就更高效的插入和删除元素的操作,在适合的场景下它是一种非常方便的数据结构。但在一些需要遍历、指定位置操作、或者访问任意元素下,是需要循环遍历的,这将导致时间复杂度的提升。
三、链表分类类型
链表的主要表现形式分为;单向链表、双向链表、循环链表,接下来我们分别介绍下。
1. 单向链表
单链表包含具有数据字段的节点以及指向节点行中的下一个节点的“下一个”字段。可以对单链表执行的操作包括插入、删除和遍历。

2. 双向链表
在“双向链表”中,除了下一个节点链接之外,每个节点还包含指向序列中“前一个”节点的第二个链接字段。这两个链接可以称为'forward('s')和'backwards',或'next'和'prev'('previous')。

3. 循环链表
在列表的最后一个节点中,链接字段通常包含一个空引用,一个特殊的值用于指示缺少进一步的节点。一个不太常见的约定是让它指向列表的第一个节点。在这种情况下,列表被称为“循环”或“循环链接”;否则,它被称为“开放”或“线性”。它是一个列表,其中最后一个指针指向第一个节点。

常见面试问题
- 描述一下链表的数据结构?
- Java 中 LinkedList 使用的是单向链表、双向链表还是循环链表?
- 链表中数据的插入、删除、获取元素,时间复杂度是多少?
- 什么场景下使用链表更合适?
相关文章:
线性数据结构:链表 LinkList
一、前言 链表的历史 于1955-1956年,由兰德公司的Allen Newell、Cliff Shaw和Herbert A. Simon开发了链表,作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由 Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使…...
对restful的支持 rust-grpc-proxy
目录前言快速体验说明1. 启动目标服务2. 启动代理3. 测试4. example.sh尾语前言 继上一篇博文的展望,这个月rust-grpc-proxy提供了对restful的简单支持。 并且提供了完成的用例,见地址如下, https://github.com/woshihaoren4/grpc-proxy/tre…...
【模拟集成电路】环路滤波器(LPF)设计
环路滤波器 LPF 设计 前言环路滤波器设计仿真结果各部分链接链接:前言 本文主要内容是对环路滤波器 模块设计设计进行阐述,LPF在电荷泵频率综合器中,主要作用是进行滤波,消除毛刺,因此一个简单的RC就可以起到很好的效果…...
adb及cmd部分常用命令
adb及cmd部分常用命令cmd常用命令adb常用命令内存/cpu相关此文章日常记录,有可能存在不准确的地方,仅供参考即可。 cmd常用命令 返回上一级: cd… 进入指定盘: D: 进入指定路径: cd 文件路径 查看子文件列表…...
ProtoBuf介绍
1 编码和解码编写网络应用程序时,因为数据在网络传输的都是二进制字节码数据,在发送数据时进行编码,在接受数据时进行解码codec(编码器)的组成部分有2个:decoder(解码器)和encoder&a…...
数据结构:完全二叉树开胃菜小练习
目录 一.前言 二.完全二叉树的重要结构特点 三.完全二叉树开胃菜小练习 1.一个重要的数学结论 2.简单的小练习 一.前言 关于树及完全二叉树的基础概念(及树结点编号规则)参见:http://t.csdn.cn/imdrahttp://t.csdn.cn/imdra 完全二叉树是一种非常重要的数据结构: n个结点的…...
mybatis与jpa
1、官方文档 mybatis:mybatis-spring – jpa:https://springdoc.cn/spring-data-jpa/ 应用文档 jpa详解_java菜鸟1的博客-CSDN博客 JPA简介及其使用详解_Tourist-xl的博客-CSDN博客_jpa的作用 2、使用比较 mybatis一般用于互联网性质的项目&#x…...
js 求解《初级算法》66. 加一
一、题目描述 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外,这个整数不会以零开头。 示例 1: 输入:…...
力扣-游戏玩法分析
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:511. 游戏玩法分析二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结…...
ZZNUOJ_用C语言编写程序实现1186 : 奖学金(结构体专题)(附完整源码)
题目描述 某校发放奖学金共5种,获取条件各不同: 1.阳明奖学金,每人8000,期末平均成绩>80,且在本学期发表论文大于等于1篇; 2.梨洲奖学金,每人4000,期末平均成绩>85,且班级评议成绩>80; 3.成绩优秀奖,每人2000,期末平均成绩>90; 4.西部奖学金,…...
加油站ai系统视频监测 yolov5
加油站ai系统视频监测通过yolov5网络模型深度学习边缘计算技术,加油站ai系统视频监测对现场卸油过程中人员违规离岗、现场灭火器没有按要求正确摆放、以及卸油前需要遵守静电释放15分钟、打电话、明火烟雾情况、抽烟行为进行自动识别。YOLO系列算法是一类典型的one-…...
【JDK8新特性之Stream流-Stream结果收集案例实操】
一.JDK8新特性之Stream流-Stream结果收集以及案例实操 二.Stream结果收集(collect函数)-实例实操 2.1 结果收集到集合中 /*** Stream将结果收集到集合中以及具体的实现 collect*/Testpublic void test01(){// 收集到List中 接口List<Integer> list Stream.of(1, 2, 3…...
Fiddler 抓包工具
HTTP代理所谓的http代理,其实就是代理客户机的http访问,主要代理浏览器访问页面。代理服务器是介于浏览器和web服务器之间的一台服务器,有了它之后,浏览器不是直接到Web服务器去取回网页而是向代理服务器发出请求,Requ…...
2023最新版网络安全保姆级指南,手把手带你从零基础进阶渗透攻防工程师
前言 一份网络攻防渗透测试的学习路线,不藏私了! 1、学习编程语言(phpmysqljshtml) 原因: phpmysql可以帮助你快速的理解B/S架构是怎样运行的,只有理解了他的运行原理才能够真正的找到问题/漏洞所在。所以对于国内那些上来就说…...
排序基础之选择排序法
目录 前言 一、什么是选择排序 二、实现选择排序 三、使用泛型扩展 四、使用自定义类型测试 前言 今天天气不错,这么好的天气不干点啥实在是有点可惜了,于是乎,拿出键盘撸一把! 来,今天来学习一下排序算法中的选…...
2.24测试用例
一.测试模型1.V模型特点:1.明确标注了测试的类型2.明确标注了测试阶段和开发阶段的对应关系缺点:测试后置2.W模型也叫双v模型,测试阶段全流程介入缺点:1.上一阶段完成.下一个阶段才能开始2.开发模型和测试模型也保持着一种线性的前后关系3.重文档,重过程,不支持敏捷模式二.设计…...
面试必刷101 Java题解 -- part 1
练习地址 面试必刷101-牛客1、链表反转2、链表内指定区间反转**3. 链表中的节点每k个一组翻转**4、**合并两个排序的链表**5、**合并k个已排序的链表**6、**判断链表中是否有环****7、链表中环的入口结点**8、链表中倒数最后k个结点**9、删除链表的倒数第n个节点****10、两个链…...
Python---关联与继承
专栏:python 个人主页:HaiFan. 专栏简介:Python在学,希望能够得到各位的支持!!! 关联与继承前言has a关联关系is a继承关系子类不添加__init__子类添加__init__前言 has a关联关系 has - a 是在…...
数据库行业的 “叛逆者”:大数据已“死”,MotherDuck 当立
“大数据”已死——现今我们最重要的事情不是担心数据大小,而是专注于我们将如何使用它来做出更好的决策。数据库行业发展至今,在数据层面有很多的加速和变革,尤其是过去几年的云数仓爆炸式增长,带来了行业的很多变化。毫无疑问&a…...
Linux->进程优先级
目录 1. 优先级的概念 2. 优先级的运作方式 3. Linux下查看进程优先级以及调整 3.1 查看进程优先级 3.2 修改进程优先级 1. 优先级的概念 1. cpu资源分配的先后顺序,就是指进程的优先权(priority)。 2. 优先权高的进程有优先执行权利。配…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
