单向链表链表是一种将分散的节点（节点）串联起来的数据结构。在每个节点中，都会有两个核心元素，一个是数据，一个是下一个节点的地址，我们称之为后继指针(next)classNode{constructor(data){this.data=data;这。下一个=空；}}classLinkedList{constructor(){this.head=null;这个.size=0;}isEmpty(){/*判断是否为空*/}size(){/*获取链表的大小*/}getHead(){/*获取链表的头节点*/}indexOf(element){/*获取一个元素的位置*/}insertAtTail(element){/*在列表末尾插入一个元素*/}insertAt(element,index){/*在指定位置插入*/}remove(element){/*删除一个元素*/}removeAt(index){/*在指定位置删除*/}getElementAt(index){/*根据某个位置获取元素*/}removeAtHead(){/*删除头部位置的元素*/}}双链表在单链表的基础上增加了一个前节点指针属性。同样，双链表也可以在单链表的基础上进行扩展，在里面增加一个尾节点。对于从后到前的遍历，和从前到后的遍历一样，复杂度也是O(n)。类DoublyNode扩展节点{constructor(data,next,prev){super(data,next);this.prev=prev;}}classDoublyLinkedListextendsLinkedList{constructor(){this.tail=undefined;}}循环链表头尾链表。在双向循环链表的情况下，它是一个双向循环链表，除了顺时针方向的头尾连接外，还可以逆时针循环。如何使用链表缓存最近最少使用（LRU，leastrecentlyused）和最不频繁使用（LFU，leastfrequentlyused），简称LRU缓存和LFU缓存。LFU缓存在经典的LFU缓存中，有两种哈希表，一种是key-value哈希表，存储节点。还有一个频率哈希表，里面会根据每个访问频率有一个双向链表，如下图，如果访问一次key值为2和3的两个节点的内容，那么它们在频率为1的下面会按照访问顺序加入到链表中。LFU缓存中有两种哈希表，一种是键值哈希表，另一种是频率哈希表。插入新节点：这里我们检查缓存是否已满，如果是，则插入时其频率为1。如果未满，则插入新元素，删除尾元素。Updateoldnode：此时这个元素会被移动到header中。同样，为了计算下一个要移除的元素，最小频率minFreq减1。获取节点的动作：缓存可以返回节点，增加其频率计数，并将元素移动到头部双向链表。同样与插入场景类似，在最后一步中，将调整最小频率minFreq的值，以计算下一次操作将被替换的元素。classLFUCache{constructor(){this.keys={};//用于存储LFU节点的键值哈希表this.freq={};//用于存储LFU链表的频率哈希表this.capacity=capacity;//用来定义缓存的容量this.minFreq=0;//初始设置最小访问频率为0this.size=0;//初始设置缓存大小为0}set(){/*插入一个节点*/}get(){/*读取一个节点*/}}LRU缓存LRU缓存的目的是清除最旧的内容缓存，当新内容需要缓存在有限的内存空间中。当缓存中的元素被访问时，最新的元素被放置在列表的末尾。当访问不在缓存中的内容时，将删除第一个和最旧的内容。classLRUNodeextendsDoublyNode{constructor(key){this.key=key;}}classLRUCache{constructor(){this.keys={};//用于存储LFU节点的键值哈希表this.capacity=capacity;//用来定义缓存的容量this.size=0;//初始设置缓存大小为0}set(){/*插入一个节点*/}get(){/*读取一个节点*/}}极客时间《Jvascript进阶实战课》学习笔记Day17
