LRU Cache

LeetCode Q 146 - LRU Cache

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

Follow up:
Could you do both operations in O(1) time complexity?

Example:
LRUCache cache = new LRUCache( 2 / capacity / );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Solution

We use Double Linked List and HashTable to maintain the LRU Cache.

1. Double Linked List: it allows us to put the most recent node at first and remove the least frequent one, i.e. the last one in the list.

2. HashTable: enables visiting a node in O(1) time;

Code:

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

private void addFirst (DLLNode node) {
	DLLNode prevFirst = this.head.next;
	this.head.next = node; node.prev = this.head;
	node.next = prevFirst; prevFirst.prev = node;
}

private void remove (DLLNode node) {
	node.prev.next = node.next;
	node.next.prev = node.prev;
}

private DLLNode head, tail;
private Map<Integer, DLLNode> map;
private int count, capacity;

public LRUCache(int capacity) {
	this.head = new DLLNode(0, 0); this.tail = new DLLNode(0, 0);
	this.head.next = this.tail; this.head.prev = null;
	this.tail.prev = this.head; this.tail.next = null;
	this.map = new HashMap<>();
	this.count = 0;
	this.capacity = capacity;
}

public int get(int key) {
	if (!this.map.containsKey(key)) return -1;
	
	DLLNode curr = this.map.get(key);
	remove(curr);
	addFirst(curr);

	return curr.value;
}

public void put(int key, int value) {
	DLLNode node = this.map.get(key);
	if (node != null) {
		node.value = value;
		get(node);	
	} else {
		node = new DLLNode(key, value);
		addFirst(node);
		this.count++;
		if (this.count > this.capacity) {
			// remove tail
			this.map.remove(this.tail.prev.key); // first remove the node from the map
			remove(this.tail.prev); // then remove the node from the DLL
			this.count--;
		}
	}
}

tips: when removing the last element, the order of operations is important. That is remove that node from the map first, then remove it from the DLL.