链表(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)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候,都可以使用链表
本文作者:毛超颖
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!