LRUCache

LinkedHashMap way

public class LRUCache {
  private final LinkedHashMap<Integer, Integer> keyToValueMap;
  private final int maxCapacity;

  public LRUCache(int maxCapacity) {
    this.maxCapacity = maxCapacity;
    keyToValueMap = new LinkedHashMap<>(maxCapacity);
  }

  public void put(Integer key, Integer value) {
    keyToValueMap.put(key, value);

    if (keyToValueMap.size() > maxCapacity) {
      Integer oldestKey = keyToValueMap.keySet().iterator().next();
      keyToValueMap.remove(oldestKey);
    }

    updateRecentlyUsed(key);
  }

  public Integer get(Integer key) {
    if (!keyToValueMap.containsKey(key)) {
      return -1;
    }

    Integer value = keyToValueMap.get(key);
    updateRecentlyUsed(key);
    return value;
  }

  private void updateRecentlyUsed(Integer key) {
    Integer value = keyToValueMap.remove(key);
    keyToValueMap.put(key, value);
  }

}

Pros:

• Fast and easy to implement
  Cons:
• If in the future we want to add from the end, we need to loop through until the end to find the last node to remove

Hashmap + LinkedList way

package datastructures.LRUCache;

public interface Cache<K, V> {
  void put(K key, V value);
  V get(K key);
}

package datastructures.LRUCache;

class LRUNode {
  public LRUNode next;
  public LRUNode previous;
  public Integer key;
  public Integer value;

  public LRUNode() {

  }

  public LRUNode(Integer key, Integer value) {
    this.key = key;
    this.value = value;
  }
}

package datastructures.LRUCache;


import java.util.HashMap;
import java.util.Map;

public class LRUCache implements Cache<Integer, Integer> {
  private final Integer capacity;
  private final Map<Integer, LRUNode> keyToNode;
  private final LRUNode tailNode;
  private final LRUNode headNode;

  public LRUCache(int capacity) {
    tailNode = new LRUNode();
    headNode = new LRUNode();
    keyToNode = new HashMap<>(capacity);
    this.capacity = capacity;

    tailNode.previous = headNode;
    headNode.next = tailNode;
  }

  @Override 
  public void put(Integer key, Integer value) {
    LRUNode cacheNode = keyToNode.get(key);

    if (cacheNode == null) {
      cacheNode = new LRUNode(key, value);
      keyToNode.put(key, cacheNode);
    } else {
      cacheNode.value = value;
    }

    if (keyToNode.size() > capacity) {
      detach(cacheNode);
      removeLeastRecentlyUsed();
    }

    updateRecentlyUsed(cacheNode);
  }

  private void removeLeastRecentlyUsed() {
    LRUNode removeNode = headNode.next;
    headNode.next = removeNode.next;
    removeNode.next.previous = headNode;

    keyToNode.remove(removeNode.key);
  }


  @Override
  public Integer get(Integer key) {
    if (!keyToNode.containsKey(key)) {
      return -1;
    }

    LRUNode node = keyToNode.get(key);
    updateRecentlyUsed(node);
    return node.value;
  }

  private void updateRecentlyUsed(LRUNode cacheNode) {
    detach(cacheNode);
    connectToTail(cacheNode);
  }

  private void connectToTail(LRUNode cacheNode) {
    LRUNode previousTailNode = tailNode.previous;
    previousTailNode.next = cacheNode;

    cacheNode.previous = previousTailNode;
    cacheNode.next = tailNode;

    tailNode.previous = cacheNode;
  }

  private void detach(LRUNode cacheNode) {
    LRUNode previousNode = cacheNode.previous;
    LRUNode nextNode = cacheNode.next;

    if (previousNode != null) {
      previousNode.next = nextNode;
    }

    if (nextNode != null) {
      nextNode.previous = previousNode;
    }
  }

}

Remember to use a HashMap<Key, Node> in the Node we have previous, next and the pair of key, value.

Pros:

• Customisable
  Cons:
• Complex

Python implementation

class Node:
    def __init__(self, key=None, val=0):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None


class LRUCache:

    def __init__(self, capacity: int):
        self.store: dict[int, Node] = {}
        self.capacity = capacity
        
        self.head: Node = Node()
        self.tail: Node = Node()

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        _node: Node = self.store.get(key)

        if not _node: return -1

        self._updateRecentlyUsed(_node)
        
        return _node.val

    def put(self, key: int, val: int) -> None:
        _node: Node = self.store.get(key, Node(key, val))
        
        if key in self.store:
            self._updateRecentlyUsed(_node)
            _node.val = val
        else:
            self._attach(_node)
        
        self.store[key] = _node
        
        if len(self.store) > self.capacity:
            self._removeLRU()
    
    def _updateRecentlyUsed(self, node: Node):
        self._detach(node)
        self._attach(node)
        
    def _removeLRU(self):
        _lru = self.head.next
        
        if _lru is None or _lru.key is None:
            # Nothing to delete
            return

        del self.store[_lru.key]

        self._detach(_lru)

    def _detach(self, node: Node):
        if not node:
            return

        node.prev.next = node.next
        node.next.prev = node.prev

    def _attach(self, node: Node):
        node.next = self.tail
        node.prev = self.tail.prev
        
        node.prev.next = node
        node.next.prev = node