JavaScript双向链表实现LRU缓存算法的示例代码

首先，我们需要了解下什么是双向链表和LRU缓存算法。

双向链表：每个节点有两个指针，一个指向其前驱节点，一个指向其后继节点。双向链表的优势在于可以快速对链表中的任意节点进行插入、删除和移动操作，时间复杂度均为O(1)。

LRU缓存算法：Least Recently Used，即最近最少使用。LRU缓存算法通过记录缓存中每个数据项的访问时间，当缓存空间满时，将最近最少使用的数据项从缓存中移除，以空出空间保存新数据。

接下来是双向链表实现LRU缓存算法的示例代码：

class CacheNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.prev = null
    this.next = null
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.length = 0
    this.head = new CacheNode(null, null)
    this.tail = new CacheNode(null, null)
    this.head.next = this.tail
    this.tail.prev = this.head
    this.cache = {}
  }

  get(key) {
    if (key in this.cache) {
      const node = this.cache[key]
      this.moveToHead(node)
      return node.value
    } else {
      return -1
    }
  }

  put(key, value) {
    if (key in this.cache) {
      const node = this.cache[key]
      node.value = value
      this.moveToHead(node)
    } else {
      const node = new CacheNode(key, value)
      this.cache[key] = node
      this.addToHead(node)
      this.length++
      if (this.length > this.capacity) {
        this.removeTail()
        this.length--
      }
    }
  }

  moveToHead(node) {
    this.removeNode(node)
    this.addToHead(node)
  }

  addToHead(node) {
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
  }

  removeNode(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }

  removeTail() {
    const node = this.tail.prev
    this.removeNode(node)
    delete this.cache[node.key]
  }
}

这里我们定义了两个类：CacheNode 和 LRUCache。CacheNode 表示缓存的节点，包含一个key和value属性，以及两个指针prev和next。LRUCache 是缓存的数据结构，包含一个capacity属性表示缓存容量，一个length属性表示当前缓存中元素的数量，一个head属性表示双向链表的头节点，一个tail属性表示双向链表的尾节点，和一个cache对象表示缓存中的所有数据。

get(key) 方法表示获取缓存中的数据。如果不存在，则返回-1。如果存在，则将对应节点移动到双向链表的头部，表示最近使用了该数据，并返回节点的值。

put(key, value) 方法表示往缓存中添加数据。如果缓存中已经存在该数据，直接移动到双向链表的头部即可。如果不存在，新建一个节点，添加到双向链表的头部，并在cache中增加对key的引用。如果缓存容量已满，需要将双向链表尾部的节点删掉，并在cache中删除对应的key的引用。

moveToHead(node) 方法表示将节点移动到双向链表的头部，表示最近使用了该数据。需要先将该节点从双向链表中删除，然后添加到双向链表的头部。

addToHead(node) 方法表示添加节点到双向链表的头部。

removeNode(node) 方法表示从双向链表中删除节点。

removeTail() 方法表示删除双向链表的尾节点。需要先删除该节点的引用，再从双向链表中删除该节点。

下面是一个示例：

const cache = new LRUCache(2)

cache.put(1, 'a')
cache.put(2, 'b')

console.log(cache.get(1)) // output: 'a'

cache.put(3, 'c')

console.log(cache.get(2)) // output: -1

cache.put(4, 'd')

console.log(cache.get(1)) // output: -1
console.log(cache.get(3)) // output: 'c'
console.log(cache.get(4)) // output: 'd'

这里我们创建了一个容量为2的LRUCache。然后分别往cache中添加数据，最后输出各个数据的值。在输出数据之前，我们先打印LRUCache的状态。可以看到，当调用put方法，向cache中添加第3个元素时，cache中已经满了，需要将最旧的数据（key=1）删除。最后输出的结果中也验证了这点。