[LeetCode #5] LRU Cache

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.

public class LRUCache {
	class Node {
		int key;
		int value;
		Node prev;
		Node next;
	}
	
	private int lruCapacity;
	private Map<Integer, Node> lruCache;
	private Node head;
	private Node tail;

	public LRUCache(int capacity) {
		this.lruCapacity = capacity;
		this.lruCache = new HashMap<Integer, Node>();
	}

	public int get(int key) {
		// Existing key
		if (this.lruCache.containsKey(key)) {
			// Move to first place
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			// Return the value
			return node.value;
		}
		// Not found
		return -1;
	}

	private void add(Node node) {
		// Reset position
		node.next = null;
		node.prev = null;
		// First element
		if (null == this.head) {
			this.head = node;
			this.tail = node;
			return;
		}
		// Existing element
		this.head.prev = node;
		node.next = this.head;
		this.head = node;
	}

	private void remove(Node node) {
		// Nothing to do
		if (this.head == null || null == node) {
			return;
		}
		// The only one item
		if (this.head == this.tail && this.head == node) {
			this.head = null;
			this.tail = null;
			return;
		}
		// Remove from head
		if (node == this.head) {
			this.head.next.prev = null;
			this.head = this.head.next;
			return;
		}
		// Remove from end
		if (node == this.tail) {
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			return;
		}
		// Remove in the middle
		node.prev.next = node.next;
		node.next.prev = node.prev;

	}

	private void removeLast() {
		this.remove(this.tail);
	}

	private void moveFirst(Node node) {
		this.remove(node);
		this.add(node);
	}

	public void set(int key, int value) {
		if (this.lruCache.containsKey(key)) {
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			node.value = value;
			return;
		}
		// Out of capacity, cleaning the oldest slot
		if (this.lruCache.size() >= this.lruCapacity) {
			int id = this.tail.key;
			this.removeLast();
			this.lruCache.remove(id);
		}

		// New slot
		Node node = new Node();
		node.key = key;
		node.value = value;
		this.add(node);
		this.lruCache.put(key, node);
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s