侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

Linked List(链表)

前端  /  管理员 发布于 8年前   571
目录
一、是什么
二、操作
遍历
插入
删除
三、应用场景
参考文献

Linked List

# 面试官:说说你对链表的理解?常见的操作有哪些?

# 一、是什么

链表(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/

  • 上一条:
    Laravel 5框架学习之Laravel入门和新建项目
    下一条:
    前端实现冒泡排序(Bubble Sort)
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 使用 Alpine.js 排序插件对元素进行排序(0个评论)
    • 在js中使用jszip + file-saver实现批量下载OSS文件功能示例(0个评论)
    • 在vue中实现父页面按钮显示子组件中的el-dialog效果(0个评论)
    • 使用mock-server实现模拟接口对接流程步骤(0个评论)
    • vue项目打包程序实现把项目打包成一个exe可执行程序(0个评论)
    • 近期文章
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 在go + gin中gorm实现指定搜索/区间搜索分页列表功能接口实例(0个评论)
    • 在go语言中实现IP/CIDR的ip和netmask互转及IP段形式互转及ip是否存在IP/CIDR(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • Laravel 11.15版本发布 - Eloquent Builder中添加的泛型(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客