Linked List(链表)
前端  /  管理员 发布于 8年前   567
链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,由一系列结点(链表中每一个元素称为结点)组成
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域
节点用代码表示,则如下:
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)
的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)
和O(1)
链表的结构也十分多,常见的有四种形式:
关于链表的操作可以主要分成如下:
遍历很好理解,就是根据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
,不适合上述方式
解放方式可以是在头节点前面添加一个虚拟头节点,保证插入行为一致
向链表任意位置删除节点,如下图操作:
从上图可以看到删除节点的步骤为如下:
如果想要删除制定的节点,示意代码如下:
while (current != node){
pervious = current;
current = current.next;
nextNode = current.next;
}
pervious.next = nextNode
同样如何希望删除节点处理行为一致,可以在头节点前面添加一个虚拟头节点
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU
缓存、数据库缓存、浏览器缓存等等
当缓存空间被用满时,我们可能会使用LRU
最近最好使用策略去清楚,而实现LRU
算法的数据结构是链表,思路如下:
维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头部开始顺序遍历链表
由于链表插入删除效率极高,达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候,都可以使用链表
122 在
学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
Copyright·© 2019 侯体宗版权所有·
粤ICP备20027696号