Leetcode #146. LRUCache solution in Java (Doubly Linked List + HashMap)

Question

Problem Statement

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

This problem can be solved by implementing the Cache as a doubly linked list with head and tail pointers. This gives us constant time access to the head and tail of the Cache. For constant time access to all other nodes we can create a hashmap processMap which maps a key to its corresponding node in the Cache. Now, we can access any node in the linkedlist in constant time.

public void put(int key, int value) - First we check if there already exists an entry with the same key in the Cache. If it does then we remove this old entry from the processMap and the linked list. After this we insert the new entry at the end of the linked list.

public int get(int key) - We lookup the processMap and if there's an entry for the given key, we output the value of the node, remove the node from its current position and insert it at the end of the list. Otherwise, we return -1.

class ProcessNode {
    private int key, value;
    private ProcessNode previous, next;

    public ProcessNode(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }

    public void setNext(ProcessNode next) {
        this.next = next;
    }

    public ProcessNode getNext() {
        return next;
    }

    public void setPrevious(ProcessNode previous) {
        this.previous = previous;
    }

    public ProcessNode getPrevious() {
        return previous;
    }
}

class LRUCache {
    private int size = 0;
    private int capacity;

    private ProcessNode head = null;
    private ProcessNode tail = null;

    private Map<Integer, ProcessNode> processMap = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        ProcessNode processNode = processMap.get(key);

        if (processNode == null) {
            return -1;
        }

        remove(processNode);
        addLast(processNode);

        return processNode.getValue();
    }

    private void remove(ProcessNode processNode) {
        if (processNode == null) {
            return;
        }

        if ((processNode != head) && (processNode != tail)) {
            processNode.getPrevious().setNext(processNode.getNext());
            processNode.getNext().setPrevious(processNode.getPrevious());
        } else {
            if (processNode == head) {
                head = processNode.getNext();

                if (head != null) {
                    head.setPrevious(null);
                }
            }

            if (processNode == tail) {
                tail = processNode.getPrevious();

                if (tail != null) {
                    tail.setNext(null);
                }
            }
        }

        size--;
        processMap.remove(processNode.getKey());
    }

    private void removeFirst() {
        remove(head);
    }

    private void addLast(ProcessNode processNode) {
        if (size == capacity) {
            removeFirst();
        }

        if (tail != null) {
            tail.setNext(processNode);
            processNode.setPrevious(tail);
            tail = processNode;
        } else {
            head = processNode;
            tail = processNode;
        }

        size++;
        processMap.put(processNode.getKey(), processNode);
    }

    public void put(int key, int value) {
        ProcessNode existingNode = processMap.get(key);

        if (existingNode != null) {
            remove(existingNode);
        }

        ProcessNode newProcessNode = new ProcessNode(key, value);

        addLast(newProcessNode);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Please review my code and let me know if there's room for improvement.

Answer 1

Information hiding

If ProcessNode is only used by LRUCache, then it's an implementation detail that's best hidden from other classes. Instead of a local class, it would be better as a private static inner class.

Encapsulation and separation of concerns

LRUCache does multiple things:

• Enforce a maximum number of key value pairs
• Linked list operations

The linked list operations could be delegated to a dedicated class with remove(ListNode), removeFirst(ListNode), add(ListNode) methods.

With this reorganization, the implementation of LRUCache's main methods can focus on enforcing the bound on the number of entries, and be overall more clear and easier to understand, without having to follow through multiple methods the state changes of nodes, the map, and the size:

  public int get(int key) {
    ListNode node = nodeMap.get(key);

    if (node == null) {
      return -1;
    }

    list.remove(node);
    list.add(node);

    return node.getValue();
  }

  public void put(int key, int value) {
    ListNode newNode = new ListNode(key, value);
    list.add(newNode);

    ListNode oldNode = nodeMap.put(key, newNode);

    if (oldNode != null) {
      list.remove(oldNode);
    } else if (nodeMap.size() > capacity) {
      ListNode eldest = list.removeFirst();
      nodeMap.remove(eldest.getKey());
    }
  }

Naming

ProcessNode is just a node in a linked list. I find name "Process" a bit confusing. I recommend renaming to ListNode.

Minor technical improvements

There's no need to manage size manually, the map of nodes already has that information.

Some values are only assigned once, so they can be final, such as capacity, key, value.

The getters and setters are overkill for the node class without plans of future extensions. Especially when moved inside an inner LinkedList class. There's no real need here for such verbose boilerplate code.

Answer 2

I realize that this is old, but I happened to see it today.

Since this does not specify reinventing-the-wheel, it's worth noting that Java already has a Least Recently Used cache data structure: LinkedHashMap. So you could just say

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    protected final int LIMIT;

    public LRUCache(int capacity) {
        super(2 * capacity, .75, true);
        LIMIT = capacity;
    }

    @Override
    protected boolean removeEldestEntry() {
        return size() >= LIMIT;
    }

}

The true in the super constructor makes it last accessed order instead of last inserted. I doubled the capacity to make the map sparser. Hopefully that means fewer collisions.

Now you don't have to implement any additional logic for ProcessNode. It will delete old entries for you automatically. It has almost the same implementation as your original, with a few differences. If you really want, you could migrate your original behavior to this class. Or swap out the HashMap in your original for the LinkedHashMap.

class LRUCache {

    private final Map<Integer, Integer> processMap;

    public LRUCache(int capacity) {
        processMap = new LinkedHashMap<Integer, Integer>(capacity) {

            protected final int LIMIT;

            public LRUCache(int capacity) {
                super(2 * capacity, .75, true);
                LIMIT = capacity;
            }

            @Override
            protected boolean removeEldestEntry() {
                return size() >= LIMIT;
            }

        };
    }

    public int get(int key) {
        Integer value = processMap.get(key);

        if (value == null) {
            return -1;
        }

        return value;
    }

    public void put(int key, int value) {
        processMap.put(key, value);
    }

}

The remove method would also get easier but doesn't seem required by the problem statement. So you could actually leave it off.