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.

Solution:

A combination of HashMap and LinkedList are required. HashMap<Integer, ListNode> provides O(1) access, modification. LinkedList provides O(1) remove from the head and O(1) insert to the tail.

At initialization stage, we need to create two dummy nodes: head and tail. When a new node is inserted to the list, it should be inserted before the tail node. And when a least recent node needs to be removed, the head.next should be removed from the list.

Code:

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

public class Solution {
    private int capacity;
    private ListNode head = new ListNode(-1, -1);
    private ListNode tail = new ListNode(-1, -1);
    private HashMap<Integer, ListNode> hmap = new HashMap<>();

    public Solution(int inCapacity) {
        this.capacity = inCapacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!hmap.containsKey(key)) {
            return -1;
        }
        ListNode current = hmap.get(key);
        //remove current
        current.prev.next = current.next;
        current.next.prev = current.prev;
        appendToTail(current);
        return current.val;
    }

    private void appendToTail(ListNode current) {
        tail.prev.next = current;
        current.prev = tail.prev;
        current.next = tail;
        tail.prev = current;
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            hmap.get(key).val = value;
            return;
        }
        if (hmap.size() == capacity) {
            hmap.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        ListNode node = new ListNode(key, value);
        hmap.put(key, node);
        appendToTail(node);
    }
}