LRU Cache @LeetCode

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.

	package leetcode;
	import java.util.HashMap;
	/**
	* Solution: HashMap + Double Linked List + head, tails nodes. A very good OOD problem.
	* We need to take care public private problem in this kind of question.
	*
	* Why HashMap and Double Linked List
	* 1. HashMap could check if a value is in the list using O(1)
	* 2. Double Linked List could delete a node and insert a node to rails using O(1).
	*
	* 1. Put hashMap, head, tail node initialization in LRU but not construct function.
	* 2. Use map.size() == capacity to check full state! Don't need external var.
	* 3. LinkedList should store key which makes it easy to delete when map.size() == capacity
	*
	* My solution(Wrong): HashMap + Single Linked List. use capacity, another volum var to check if it's full.
	* set:
	* 1. not full, add to tails directly.
	* 2. full,head move on. add new ListNode to tails.(delete head node(oldest)) Actually, head node is not oldest,
	* LRU node depends on the time use it but not the add sequence.
	* It's a dynamic queue but not a fix linked list, we must update it. I ignore this point.
	*
	* @author jeffwan
	* @date Apr 1, 2014
	*/
	public class LRUCache {
	private class Node {
	Node prev;
	Node next;
	int key;
	int value;
	public Node(int key, int value) {
	this.key = key;
	this.value = value;
	this.prev = null;
	this.next = null;
	}
	}
	private int capacity;
	private HashMap<Integer, Node> map = new HashMap<Integer, Node>();
	private Node head = new Node(-1, -1);
	private Node tail = new Node(-1, -1);
	public LRUCache(int capacity) {
	this.capacity = capacity;
	tail.prev = head;
	head.next = tail;
	}
	public int get(int key) {
	if (!map.containsKey(key)) {
	return -1;
	}
	// remove current from list
	Node current = map.get(key);
	current.prev.next = current.next;
	current.next.prev = current.prev;
	// move current to tails - - update its frequecy
	addToTail(current);
	return current.value;
	}
	public void set(int key, int value) {
	if (get(key) != -1) {
	map.get(key).value = value;
	return;
	}
	if (map.size() == capacity) {
	// remove head.next node
	map.remove(head.next.key);
	head.next = head.next.next;
	head.next.prev = head;
	}
	Node insert = new Node(key, value);
	map.put(key, insert);
	addToTail(insert);
	}
	private void addToTail(Node current) {
	current.prev = tail.prev;
	tail.prev = current;
	current.prev.next = current;
	current.next = tail;
	}
	}

view raw LRUCache.java hosted with ❤ by GitHub