## Algorithm

Problem Name: 146. LRU Cache

Implement the `LRUCache` class:

• `LRUCache(int capacity)` Initialize the LRU cache with positive size `capacity`.
• `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`.
• `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, evict the least recently used key.

The functions `get` and `put` must each run in `O(1)` average time complexity.

Example 1:

```Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
```

Constraints:

• `1 <= capacity <= 3000`
• `0 <= key <= 104`
• `0 <= value <= 105`
• At most `2 * 105` calls will be made to `get` and `put`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct kvlist {
int key;
int val;
struct kvlist *prev;
struct kvlist *next;
};

typedef struct {
int kf;
int sz;
int idx;
struct kvlist **kp;
struct kvlist *buff;
struct kvlist *tail;
} LRUCache;

LRUCache* lRUCacheCreate(int capacity) {
LRUCache *obj;
int i;

obj = calloc(1, sizeof(LRUCache));
//assert(obj);

obj->kf = 1024 * 10;
obj->kp = calloc(obj->kf, sizeof(struct kvlist *));
obj->sz = capacity;
obj->buff = calloc(obj->sz, sizeof(struct kvlist));
obj->idx = 0;

obj->tail = &obj->buff[obj->sz - 1];
if (obj->sz > 1) {
obj->tail->prev = &obj->buff[obj->sz - 2];
}
for (i = 1; i  <  obj->sz - 1; i ++) {
obj->buff[i].prev = &obj->buff[i - 1];
obj->buff[i].next = &obj->buff[i + 1];
}

return obj;
}

struct kvlist *lookup(LRUCache *obj, int key) {
struct kvlist *l;

l = obj->kp[key % obj->kf];
while (l && l->key != key) {
}

return l;
}

void move2tail(LRUCache *obj, struct kvlist *l) {
if (l == obj->tail) return;
obj->tail = l;
return;
}
// take it out of the loop
l->prev->next = l->next;
l->next->prev = l->prev;
l->prev = obj->tail;
obj->tail->next = l;

obj->tail = l;
}

int lRUCacheGet(LRUCache* obj, int key) {
int val;
struct kvlist *l;

l = lookup(obj, key);

if (!l) return -1;

val = l->val;

move2tail(obj, l);

return val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
int i;
struct kvlist *l, **pp;

l = lookup(obj, key);
if (!l) {

// remove it from hash table
i = l->key % obj->kf;
pp = &obj->kp[i];
while (*pp && *pp != l) {
}

// insert it to hash table with new key
l->key = key;
i = key % obj->kf;
obj->kp[i] = l;
}

l->val = value;

move2tail(obj, l);
}

void lRUCacheFree(LRUCache* obj) {
free(obj->kp);
free(obj->buff);
}
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
}

int get(int key) {
if(!m.count(key) || m[key] == -1) return -1;
q.push_back(key);
visited[key]++;
return m[key];
}

void put(int key, int value) {
if(!m.count(key)|| m[key] == -1) count++;
else visited[key]++;
if(count > capacity){
while(visited[q.front()]) visited[q.front()]--, q.pop_front();
m[q.front()] = -1;
q.pop_front();
count--;
}
q.push_back(key);
m[key] = value;
}

private:
unordered_map < int, int>m;
unordered_map<int, int>visited;
deque < int>q;
int count = 0;
int capacity = 0;
};
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class LRUCache {

private final Map map;
private final Node tail;
private int capacity;

public LRUCache(int capacity) {
this.map = new HashMap < >();
this.tail = new Node(-1, -1);
this.capacity = capacity;
}

public int get(int key) {
if (!this.map.containsKey(key)) {
return -1;
}
Node node = this.map.get(key);
removeNode(node);
return this.map.get(key).val;
}

public void put(int key, int value) {
if (!map.containsKey(key)) {
if (capacity == 0) {
removeNode(tail.prev);
}
} else {
removeNode(this.map.get(key));
}
}

this.map.put(node.key, node);
this.capacity--;
}

private void removeNode(Node node) {
Node nextNode = node.next;
node.prev.next = nextNode;
nextNode.prev = node.prev;
this.map.remove(node.key);
this.capacity++;
}

private static class Node {
Node next;
Node prev;
int key;
int val;

public Node(int key, int val) {
this.key = key;
this.val = val;
this.next = null;
this.prev = null;
}
}
}
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
class Node {
constructor(key, val) {
this.val = val;
this.key = key;
this.next = this.pre = null;
}
}

const LRUCache = function(capacity) {
this.capacity = capacity;
this.count = 0;
this.start = new Node(-1, -1);
this.end = new Node(-1, -1);
this.start.next = this.end;
this.end.pre = this.start;
this.map = {};
};

// insert node into the next of the start
const insertAfter = function(start, node) {
let next = start.next;
start.next = node;
node.pre = start;
node.next = next;
next.pre = node;
};

const detach = function(node) {
let pre = node.pre,
next = node.next;
pre.next = next;
next.pre = pre;
node.next = node.pre = null;
};

/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let node = this.map[key];
if (node != undefined) {
detach(node);
insertAfter(this.start, node);
return node.val;
} else {
return -1;
}
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let node = this.map[key];
if (!node) {
if (this.count == this.capacity) {
// deleting last nodes
let t = this.end.pre;
detach(t);
delete this.map[t.key];
} else {
this.count++;
}
node = new Node(key, value);
this.map[key] = node;
insertAfter(this.start, node);
} else {
node.val = value;
detach(node);
insertAfter(this.start, node);
}
};
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Node:
def __init__(self, key, value):
self.key = key
self.val = value
self.next = self.pre = None
self.pre = None
class LRUCache:
def remove(self, node):
node.pre.next, node.next.pre = node.next, node.pre
self.dic.pop(node.key)

node.pre = self.tail.pre
node.next = self.tail
self.tail.pre.next = self.tail.pre = node
self.dic[node.key] = node

def __init__(self, capacity):
self.dic = {}
self.n = capacity
self.head = self.tail = Node(0, 0)

def get(self, key):
if key in self.dic:
node = self.dic[key]
self.remove(node)
return node.val
return -1

def put(self, key, value):
if key in self.dic:
self.remove(self.dic[key])
node = Node(key, value)
if len(self.dic) > self.n:
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0146_LRUCache
{
private int size;

public _0146_LRUCache(int capacity)
{
this.size = 0;
this.capacity = capacity;
this.hashMap = new Dictionary < int, DoubleLinkNode>();

}

public int Get(int key)
{
if (!hashMap.ContainsKey(key)) return -1;

var node = hashMap[key];
return node.Value;
}

public void Put(int key, int value)
{
if (hashMap.ContainsKey(key))
{
var node = hashMap[key];
node.Value = value;
return;
}

{
Key = key,
Value = value
};
size++;

if (size > capacity)
{
var node = RemoveLatestNode();
hashMap.Remove(node.Key);
size--;
}
}

{
RemoveNode(node);
}

{
var previous = node.Prev;
var next = node.Next;

previous.Next = next;
next.Prev = previous;
}

{

node.Next = next;
next.Prev = node;

}

{
var last = dummyTail.Prev;
RemoveNode(last);
return last;
}

{
public int Key { get; set; }
public int Value { get; set; }
public DoubleLinkNode Prev { get; set; }
public DoubleLinkNode Next { get; set; }
}
}
}
``````
Copy The Code &

Input

cmd
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

cmd
[null, null, null, 1, null, -1, null, -1, 3, 4]