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 {
    
	private final int MAX_CACHE_SIZE;
	private Entry first;
    private Entry last;
    private HashMap<Integer, Entry> hashMap;
    public LRUCache(int capacity) {
    	MAX_CACHE_SIZE = capacity;
    	hashMap = new HashMap();
    }
    
    public int get(int key) {
    	Entry entry = getEntry(key);
        if (entry == null) {
        	return -1;
        }
        moveToFirst(entry);
        return entry.value;
    }
    
    private void moveToFirst(Entry entry) {
		if (entry == first) {
			return;
		}
		if (entry.pre != null) {
			entry.pre.next = entry.next;
		}
		if (entry.next != null) {
			entry.next.pre = entry.pre;
		}
		if (entry == last) {
			last = last.pre;
		}
		if (first == null || last == null) {
            first = last = entry;
            return;
        }

        entry.next = first;
        first.pre = entry;
        first = entry;
        entry.pre = null;
	}

	private Entry getEntry(int key) {
		return hashMap.get(key);
	}

	public void set(int key, int value) {
		Entry entry = getEntry(key);
        if (entry == null) {
            if (hashMap.size() >= MAX_CACHE_SIZE) {
                hashMap.remove(last.key);
                removeLast();
            }
            entry = new Entry();
            entry.key = key;
        }
        entry.value = value;
        moveToFirst(entry);
        hashMap.put(key, entry);
    }
    
    private void removeLast() {
		if (last != null) {
			last = last.pre;
			if (last == null) {
				first = null;
			} else {
				last.next = null;
			}
		}
	}

	class Entry {
        public Entry pre;
        public Entry next;
        public int key;
        public int value;
    }
    
}