# 【基础篇 - Day 12】 2020-11-12 - 146. LRU 缓存机制（02.链表 ）
# 题目描述
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4题目地址：https://leetcode-cn.com/problems/lru-cache/
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(1) 两个操作都是 01
空间复杂度: O(N)
双向链表进行增删，Map 进行查找，明天再写一遍
/**
* @param {number} capacity
*/
class DoubleLinkedListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
var LRUCache = function (capacity) {
this.head = new DoubleLinkedListNode(null, null)
this.tail = new DoubleLinkedListNode(null, null)
this.head.next = this.tail
this.tail.prev = this.head
this.hash = new Map()
this.max = capacity
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (this.hash.has(key)) {
const node = this.hash.get(key)
this._addToHead(this._remove(node))
return node.value
} else {
return -1
}
};
LRUCache.prototype._isFull = function () {
return this.hash.size < this.max
};
LRUCache.prototype._addToHead = function (node) {
const head = this.head.next
node.next = head
head.prev = node
node.prev = this.head
this.head.next = node
};
LRUCache.prototype._remove = function (node) {
node.prev.next = node.next
node.next.prev = node.prev
node.prev = null
node.next = null
return node
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.hash.has(key)) {
const node = this.hash.get(key)
node.value = value
this._addToHead(this._remove(node))
return
}
const newHead = new DoubleLinkedListNode(key, value)
console.log(this._isFull())
if (!this._isFull()) {
const tail = this.tail.prev
this.hash.delete(tail.key)
this._remove(tail)
}
this.hash.set(key, newHead)
this._addToHead(newHead)
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/