说说你对链表的理解?常见的操作有哪些?
一、是什么
链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,由一系列结点(链表中每一个元素称为结点)组成
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域
节点用代码表示,则如下:
class Node {constructor(val) {this.val = val;this.next = null;}
}
- data 表示节点存放的数据
- next 表示下一个节点指向的内存空间
相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
链表的结构也十分多,常见的有四种形式:
- 单链表:除了头节点和尾节点,其他节点只包含一个后继指针
- 循环链表:跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点,首尾相连,形成了一个环
- 双向链表:每个结点具有两个方向指针,后继指针(next)指向后面的结点,前驱指针(prev)指向前面的结点,其中节点的前驱指针和尾结点的后继指针均指向空地址NULL
- 双向循环链表:跟双向链表基本一致,不过头节点前驱指针指向尾迹诶单和尾节点的后继指针指向头节点
二、操作
关于链表的操作可以主要分成如下:
- 遍历
- 插入
- 删除
遍历
遍历很好理解,就是根据next指针遍历下去,直到为null,如下:
let current = head
while(current){console.log(current.val)current = current.next
}
插入
向链表中间插入一个元素,可以如下图所示:
可以看到,插入节点可以分成如下步骤:
- 存储插入位置的前一个节点
- 存储插入位置的后一个节点
- 将插入位置的前一个节点的 next 指向插入节点
- 将插入节点的 next 指向前面存储的 next 节点
相关代码如下所示:
let current = head
while (current < position){pervious = current;current = current.next;
}
pervious.next = node;
node.next = current;
如果在头节点进行插入操作的时候,会实现previousNode节点为undefined,不适合上述方式
解放方式可以是在头节点前面添加一个虚拟头节点,保证插入行为一致
删除
向链表任意位置删除节点,如下图操作:
从上图可以看到删除节点的步骤为如下:
- 获取删除节点的前一个节点
- 获取删除节点的后一个节点
- 将前一个节点的 next 指向后一个节点
- 向删除节点的 next 指向为null
如果想要删除制定的节点,示意代码如下:
while (current != node){pervious = current;current = current.next;nextNode = current.next;
}
pervious.next = nextNode
同样如何希望删除节点处理行为一致,可以在头节点前面添加一个虚拟头节点
三、应用场景
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等
当缓存空间被用满时,我们可能会使用LRU最近最好使用策略去清楚,而实现LRU算法的数据结构是链表,思路如下:
维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头部开始顺序遍历链表
- 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据的对应结点,并将其从原来的位置删除,并插入到链表头部
- 如果此数据没在缓存链表中
- 如果此时缓存未满,可直接在链表头部插入新节点存储此数据
- 如果此时缓存已满,则删除链表尾部节点,再在链表头部插入新节点
由于链表插入删除效率极高,达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候,都可以使用链表
参考文献
- https://zh.wikipedia.org/zh-hans/%E9%93%BE%E8%A1%A8
- https://mah93.github.io/2019/07/19/js-linked/
如果对您有所帮助,欢迎您点个关注,我会定时更新技术文档,大家一起讨论学习,一起进步。
相关文章:
说说你对链表的理解?常见的操作有哪些?
一、是什么 链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,由一系列结点(链表中每一个元素称为结点)组成 每个结点包括两个部分&…...
每天五分钟深度学习:逻辑回归算法的损失函数和代价函数是什么?
本文重点 前面已经学习了逻辑回归的假设函数,训练出模型的关键就是学习出参数w和b,要想学习出这两个参数,此时需要最小化逻辑回归的代价函数才可以训练出w和b。那么本节课我们将学习逻辑回归算法的代价函数是什么? 为什么不能平方差损失函数 线性回归的代价函数我们使用…...
llama-factory SFT系列教程 (二),大模型在自定义数据集 lora 训练与部署
文章目录 简介支持的模型列表2. 添加自定义数据集3. lora 微调4. 大模型 lora 权重,部署问题 参考资料 简介 文章列表: llama-factory SFT系列教程 (一),大模型 API 部署与使用llama-factory SFT系列教程 (二),大模型在自定义数…...
C语言游戏实战(11):贪吃蛇大作战(多人对战)
成果展示: 贪吃蛇(多人对战) 前言: 这款贪吃蛇大作战是一款多人游戏,玩家需要控制一条蛇在地图上移动,吞噬其他蛇或者食物来增大自己的蛇身长度和宽度。本游戏使用C语言和easyx图形库编写,旨在…...
腾讯测试岗位的面试经历与经验分享【一面、二面与三面】
腾讯两个月的实习一转眼就结束了,回想起当时面试的经过,感觉自己是跌跌撞撞就这么过了,多少有点侥幸.马上腾讯又要来校招了,对于有意愿想投腾讯测试岗位的同学们,写了一些那时候面试的经历和自己的想法,算不上经验,仅供参考吧! 一面 — —技术基础,全面…...
手机移动端网卡信息获取原理分析
有些场景我们需要获取当前手机上的网卡信息(如双卡双待、Wifi等)。本文准备研究一下这块的原理,以便更好的掌握相关技术原理。 1、底层系统接口 getifaddrs 使用 getifaddrs 接口可以达到我们的目的,该接口会返回本地所有网卡的信…...
无人新零售引领的创新浪潮
无人新零售引领的创新浪潮 在数字化时代加速演进的背景下,无人新零售作为商业领域的一股新兴力量,正以其独特的高效性和便捷性重塑着传统的购物模式,开辟了一条充满创新潜力的发展道路。 依托人脸识别、物联网等尖端技术,无人新…...
SD-WAN提升企业网络体验
在现代企业中,网络体验已成为提升工作效率与业务质量的关键因素。SD-WAN技术的出现,以其独特的优势,为企业提供了优化网络连接、加速数据传输、提升服务质量和应用访问体验,以及增强网络稳定性的解决方案。接下来,我们…...
Docker搭建Let‘s Encrypt
Let’s Encrypt是一个免费、开放和自动化的证书颁发机构(CA),它提供了一种简单、无需重复的机制来获取和更新SSL/TLS证书。Let’s Encrypt Docker镜像允许用户在容器化环境中轻松部署和使用Let’s Encrypt的服务。 主要功能包括:…...
单链表讲解
一.链表的概念以及结构 链表是一种物理结构上不连续,逻辑结构上连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构与火车是类似的,一节一节的,数据就像乘客一样在车厢中一样。 与顺序表不同的…...
DFS算法系列 回溯
DFS算法系列-回溯 文章目录 DFS算法系列-回溯1. 算法介绍2. 算法应用2.1 全排列2.2 组合2.3 子集 3. 总结 1. 算法介绍 回溯算法是一种经典的递归算法,通常被用来解决排列问题、组合问题和搜索问题 基本思想 从一个初始状态开始,按一定的规则向前搜索&…...
Linux C应用编程:MQTT物联网
1 MQTT通信协议 MQTT(Message Queuing Telemetry Transport,消息队列遥测传 输)是一种基于客户端-服务端架构的消息传输协议,如今,MQTT 成为了最受欢迎的物联网协议,已广泛应用于车联网、智能家居、即时聊…...
企业常用Linux文件命令相关知识+小案例
远程连接工具无法连接VMWARE: 如果发现连接工具有时连不上,ip存在,这时候我们查看网络编辑器,更多配置,看vnet8是不是10段,nat设置是否是正确的? 软件重启一下虚机还原一下网络编辑器 查看文件…...
Istio介绍
1.什么是Istio Istio是一个开源的服务网格(Service Mesh)框架,它提供了一种简单的方式来为部署在Kubernetes等容器编排平台上的微服务应用添加网络功能。Istio的核心功能包括: 服务治理:Istio能够帮助管理服务之间的…...
代码随想录算法训练营第四十七天|leetcode115、392题
一、leetcode第392题 本题要求判断s是否为t的子序列,因此设置dp数组,dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数,可得递推公式是通过s[i-1]和t[j-1]是否相等区分。 具体代码如下: class Solution { publ…...
将Ubuntu18.04默认的python3.6升级到python3.8
1、查看现有的 python3 版本 python3 --version 2、安装 python3.8 sudo apt install python3.8 3、将 python3.6 和 3.8 添加到 update-alternatives sudo update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.6 1 sudo update-alternatives --insta…...
Python和Java哪个更适合后端开发?
Python和Java都是强大的后端开发语言,它们各自有鲜明的特点和适用场景。选择哪一个更适合后端开发,主要取决于具体的项目需求、团队技术栈、个人技能偏好以及长期发展考虑等因素。 下面是两者在后端开发中的优势和劣势: 「Python࿱…...
Python+pytest接口自动化之cookie绕过登录(保持登录状态)
前言 我们今天来聊聊pythonpytest接口自动化之cookie绕过登录(保持登录状态),在编写接口自动化测试用例或其他脚本的过程中,经常会遇到需要绕过用户名/密码或验证码登录,去请求接口的情况,一是因为有时验证…...
什么数据集成(Data Integration):如何将业务数据集成到云平台?
说到数据集成(Data Integration),简单地将所有数据倒入数据湖并不是解决办法。 在这篇文章中,我们将介绍如何轻松集成数据、链接不同来源的数据、将其置于合适的环境中,使其具有相关性并易于使用。 数据集成࿱…...
国外EDM邮件群发多少钱?哪个软件好?
在当今全球化市场环境下,电子邮件营销作为最有效的数字营销渠道之一,其影响力不容忽视。而高效精准的EDM(Electronic Direct Mail)邮件营销策略更是企业拓展海外市场、提升品牌知名度的关键手段。云衔科技以其创新的智能EDM邮件营…...
C语言入门算法——回文数
题目描述: 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个十进制数 56,将 56 加 65(即把 56 从右向左读),得到 121 是一个…...
OceanBase—操作实践
文档结构 1、概念简介2、核心设计3、操作实践3.3、数据同步 官方文档:https://www.oceanbase.com/docs/oceanbase-database-cn 1、概念简介 版本分为社区版和企业版,其中企业版兼容MySQL 和Oracle数据库语法; 2、核心设计 存储层 复制层 …...
智慧用电安全管理系统
智慧用电安全管理系统 智慧用电安全管理系统是智能电网中客户侧关键的构成部分,是基本建设新型智慧城市的基本,将完成地区内各种各样用电设备的智能化系统监管,完成地区内日常生活与工作中安全性、舒服。 一、智慧用电安全管理系统介绍 …...
Rust语言入门第二篇-Cargo教程
文章目录 Rust语言入门第二篇-Cargo教程一,Cargo 是什么二,Cargo教程Cargo.toml文件src/main.rs 文件构建并运行Cargo项目 Rust语言入门第二篇-Cargo教程 本节提供对cargo命令行工具的快速了解。我们演示了它为我们生成新包的能力,它在包内编…...
测试用例的编写方式
学习目标 能对穷举场景设计测试点能对限定边界规则设计测试点能对多条件依赖关系进行设计测试点能对于项目业务进行设计测试点 目录 等价类划分法案例 等价类划分 说明:在所有测试数据中,具有某种共同特征的数据集合进行划分分类: 有效等…...
HarmonyOS实战开发-状态管理、通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。
介绍 本示例通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。 效果预览 使用说明 1.点击首页中的基本类型进入对应页面,点击按钮可以更改圆形的颜色;点击查看源码可以展示基本类型功能效果的源码。 2.点击首页中的数组类型进入对…...
【Java开发指南 | 第二篇】标识符、Java关键字及注释
专栏:Java开发指南 CSDN秋说 文章目录 标识符Java关键字Java注释 标识符 Java 所有的组成部分都需要名字。类名、变量名以及方法名都被称为标识符。 所有的标识符都应该以字母(A-Z 或者 a-z),美元符($)、或者下划线&…...
3D可视化技术:研发基地的科技新篇章
在科技日新月异的今天,我们生活在一个充满无限可能性的时代。而在这个时代中,3D可视化技术正以其独特的魅力,引领着科技领域的新一轮变革。 3D可视化技术通过三维图像的方式,将现实世界或虚拟世界中的物体、场景等以立体、逼真的形…...
蓝旭前端05:JavaScript进阶
蓝旭前端05:JavaScript进阶 基础简单复习 数据类型 基本数据类型:Number、String、Boolean、Null、Undefined等。引用数据类型:Object、Array、Function等。typeof操作符:返回数据类型的字符串形式。 变量 变量声明࿱…...
【docker-compose】安装及配置
目录 安装在线安装离线安装 配置mysql5.7bitnami/mysql8.3redisweb前后台分离部署前端https(SSL)配置nginx动态传参资源限制:内存、cpunacossentinelgateway 问题汇总iptables No chain/target/match by that namedocker-compose.yml修改mysql密码,重启后…...
小程序购物平台/广东seo快速排名
最近学习php,按照书上的描述,下载好apache和php后,按照其中配置进行,结果遇到了上述问题。花费了近一个半小时的时间解决了上述问题。现把解决问题过程中看到的方法总结如下。 最先肯定是一定要注意版本问题,apache和p…...
药物研发网站怎么做/如何做一个自己的网站呢
http://blog.csdn.net/kesalin/article/details/8351935 前言 本文介绍了OpenGL ES 2.0 中的顶点缓冲对象(VBO: Vertex Buffer Object)和索引缓冲对象(IBO: Indice Buffer Object)的用法, 在之前的文章中图元的绘制没用使用VBO, 要绘制的顶点数据是以顶点数组的形式…...
合肥网站建设是什么意思/全媒体广告代理加盟
Shiro基础身份验证 如果要进行shiro的日志信息读取,那么需要使用一个org.apache.shiro.util.Factory接口,在这个接口里面定义有一 取得SecuruityManager接口对象的方法:public T getInstance(); Factory是接口,本次将通…...
织梦dede新闻网站源码手机站/做优化关键词
有意义的命名 一.命名范围:变量,方法,参数,类名,包名;文件名,文件夹。 二.命名规则 1.名副其实:看到名字,就应该了解其代表的意义,其用途很自然地理解其功能。 2.避免…...
变身 变装 wordpress/什么是seo标题优化
当我发送JSON对象数组我的jQuery的AJAX方法能够解析内容和显示数据在ListView的jQuery,但是当我只有一个单一的对象我相同的jquery ajax方法不能解析数据。JQuery的Ajax方法工作与多个JSON对象,但不与单个JSON对象这里我的JSON对象数组:{&quo…...
安徽建设相关网站/互联网优化
解决办法:换上usb接口,舍弃esata, 重新上电,就能识别了 转载于:https://www.cnblogs.com/norsd/archive/2012/03/12/6359474.html...