# LRU Cache

## Problem

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

## Code - Java

public class Solution {

class Node {
Node prev = null;
Node next = null;
int val;
int key;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}

private Node head = new Node(0, 0);
private Node tail = new Node(0, 0);
private int capacity;
private Map<Integer, Node> map;

// @param capacity, an integer
public Solution(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>(capacity);
}

// @return an integer
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}

Node n = map.get(key);
moveToTail(n);
return n.val;
}

// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
if (map.containsKey(key)) {
Node n = map.get(key);
n.val = value;
moveToTail(n);
} else {
if (size() == capacity) {

}
Node newNode = new Node(key, value);
tail.prev.next = newNode;
newNode.prev = tail.prev;
newNode.next = tail;
tail.prev = newNode;
map.put(key, newNode);
}
}

private void moveToTail(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
tail.prev.next = n;
n.prev = tail.prev;
n.next = tail;
tail.prev = n;
}

private int size() {
int size = 0;
}