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 ListNode:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    KEY_NOT_FOUND = -1

    def __init__(self, capacity: int):
        self.capacity = capacity

        self.keyToNodeMap: Map[key, ListNode] = {}

        self.head = ListNode(None, None)
        self.tail = ListNode(None, None)

        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.keyToNodeMap:
            return LRUCache.KEY_NOT_FOUND
        
        keyNode = self.keyToNodeMap.get(key)

        self.updateRecentlyUsed(keyNode)

        return keyNode.value
    
    def put(self, key: int, value: int) -> None:

        if key in self.keyToNodeMap:
            keyNode = self.keyToNodeMap.get(key)
            self.keyToNodeMap.get(key).value = value
            self.updateRecentlyUsed(keyNode)
        else:
            if (self.capacity == 0):
                self.removeLeastRecentlyUsed()
            else:
                self.capacity -= 1
            
            keyNode = ListNode(key, value)
            self.keyToNodeMap[key] = keyNode
            self.updateRecentlyUsed(keyNode)
    

    def removeLeastRecentlyUsed(self):
        leastRecentlyUsedNode = self.head.next
        self.detach(leastRecentlyUsedNode)
        self.keyToNodeMap.pop(leastRecentlyUsedNode.key)

    def updateRecentlyUsed(self, keyNode: ListNode) -> None:
        self.detach(keyNode)

        mostRecentNode = self.tail.prev
        mostRecentNode.next = keyNode

        keyNode.next = self.tail
        keyNode.prev = mostRecentNode
        self.tail.prev = keyNode
    

    def detach(self, keyNode: ListNode) -> None:
        nextNode = keyNode.next 
        prevNode = keyNode.prev

        if (not nextNode and not prevNode):
            # This is a new node. No action is required
            return 

        nextNode.prev = prevNode
        prevNode.next = nextNode

        keyNode.next = None
        keyNode.prev = None