1. // 双向链表节点
    2. var LinkNode = function (key, val) {
    3.     if(!(this instanceof LinkNode)) {
    4.       return new LinkNode(key, val)
    5.   }
    6.   this.key = key;
    7.   this.val = val;
    8. }
    10. // 双向链表
    11. var DoubleLink = function() {
    12.     this.head  = new LinkNode(0, 0)
    13.   this.tail = new LinkNode(0, 0)
    14.   this.head.next = this.tail
    15.   this.tail.prev = this.head
    16.   this.size = 0
    17. }
    19. // // 在链表尾部添加节点 x，时间 O(1)
    20. DoubleLink.prototype.addLast = function(node) {
    21.     node.prev = this.tail.prev
    22.   node.next = this.tail
    23.   this.tail.prev.next = node
    24.   this.tail.prev = node
    25.   ++this.size
    26. }
    28. // 删除链表中的 x 节点（x 一定存在）
    29. // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    30. DoubleLink.prototype.remove = function (node) {
    31.     node.prev.next = node.next;
    32.     node.next.prev = node.prev;
    33.     --this.size;
    34. }
    37. // 删除链表中第一个节点，并返回该节点，时间 O(1)
    38. DoubleLink.prototype.removeFirst = function() {
    39.     if(this.head.next === this.tail) {
    40.       return null
    41.   }
    42.   let first = this.head.next
    43.   this.remove(first)
    44.   return first
    45. }
    47. // 返回链表长度，时间 O(1)
    48. DoubleLink.prototype.getSize = function () {
    49.     return this.size;
    50. }
    53. /**
    54.  * @param {number} capacity
    55.  */
    56. var LRUCache = function (capacity) {
    57.     this.map = new Map();
    58.     this.cache = new DoubleLink();
    59.       //最大容量
    60.     this.cap = capacity;
    61. };
    63. /**
    64.  * @param {number} key
    65.  * @return {number}
    66.  */
    67. LRUCache.prototype.get = function (key) {
    68.     if (!this.map.has(key)) {
    69.         return -1;
    70.     }
    71.     // 将该数据提升为最近使用的
    72.     this.makeRecently(key);
    73.     return this.map.get(key).val;
    74. };
    76. /**
    77.  * @param {number} key
    78.  * @param {number} value
    79.  * @return {void}
    80.  */
    81. LRUCache.prototype.put = function (key, value) {
    82.     if (this.map.has(key)) {
    83.         // 删除旧的数据
    84.         this.deleteKey(key);
    85.         // 新插入的数据为最近使用的数据
    86.         this.addRecently(key, value);
    87.         return;
    88.     }
    90.     if (this.cap === this.cache.getSize()) {
    91.         // 删除最久未使用的元素
    92.         this.removeLeastRecently();
    93.     }
    94.     // 添加为最近使用的元素
    95.     this.addRecently(key, value);
    96. };
    98. /**
    99.  * Your LRUCache object will be instantiated and called as such:
    100.  * var obj = new LRUCache(capacity)
    101.  * var param_1 = obj.get(key)
    102.  * obj.put(key,value)
    103.  */
    105. /* 将某个 key 提升为最近使用的 */
    106. LRUCache.prototype.makeRecently = function (key) {
    107.     let x = this.map.get(key);
    109.     // 先从链表中删除这个节点
    110.     this.cache.remove(x);
    112.     // 重新插入到队尾
    113.     this.cache.addLast(x);
    114. }
    116. /* 添加最近使用的元素 */
    117. LRUCache.prototype.addRecently = function (key, val) {
    118.     let x = new LinkNode(key, val);
    120.     // 链表尾部就是最近使用的元素
    121.     this.cache.addLast(x);
    122.     // 别忘了在 map 中添加 key 的映射
    123.     this.map.set(key, x);
    124. }
    126. /* 删除某一个 key */
    127. LRUCache.prototype.deleteKey = function (key) {
    128.     let x = this.map.get(key);
    129.     // 从链表中删除
    130.     this.cache.remove(x);
    131.     // 从 map 中删除
    132.     this.map.delete(key);
    134. }
    136. /* 删除最久未使用的元素 */
    137. LRUCache.prototype.removeLeastRecently = function () {
    138.     // 链表头部的第一个元素就是最久未使用的
    139.     let deletedNode = this.cache.removeFirst();
    141.     // 同时别忘了从 map 中删除它的 key
    142.     let deletedKey = deletedNode.key;
    143.     this.map.delete(deletedKey);
    144. }