The combined DS

class LRUCache {
  Map map = new HashMap<>();
  Node head = new Node(), tail = new Node();
  int capacity;
  
  class Node { int key, val; Node prev, next; }
  
  public LRUCache(int cap) {
    capacity = cap;
    head.next = tail; tail.prev = head;
  }
}
Advertisement

get + put

public int get(int key) {
  if (!map.containsKey(key)) return -1;
  Node n = map.get(key);
  moveToHead(n);
  return n.val;
}
public void put(int key, int val) {
  if (map.containsKey(key)) { map.get(key).val = val; moveToHead(map.get(key)); return; }
  if (map.size() == capacity) { map.remove(tail.prev.key); remove(tail.prev); }
  Node n = new Node(); n.key = key; n.val = val;
  addToHead(n); map.put(key, n);
}
Advertisement

Why doubly linked

Remove any node in O(1) requires bidirectional pointers. Single-linked list would need parent lookup.

The combined DS

class LRUCache {
  Map map = new HashMap<>();
  Node head = new Node(), tail = new Node();
  int capacity;
  
  class Node { int key, val; Node prev, next; }
  
  public LRUCache(int cap) {
    capacity = cap;
    head.next = tail; tail.prev = head;
  }
}

get + put

public int get(int key) {
  if (!map.containsKey(key)) return -1;
  Node n = map.get(key);
  moveToHead(n);
  return n.val;
}
public void put(int key, int val) {
  if (map.containsKey(key)) { map.get(key).val = val; moveToHead(map.get(key)); return; }
  if (map.size() == capacity) { map.remove(tail.prev.key); remove(tail.prev); }
  Node n = new Node(); n.key = key; n.val = val;
  addToHead(n); map.put(key, n);
}

Why doubly linked

Remove any node in O(1) requires bidirectional pointers. Single-linked list would need parent lookup.

Java&amp;amp;#x27;s LinkedHashMap

Built-in LRU support: new LinkedHashMap(16, 0.75f, true) { protected boolean removeEldestEntry(...) { return size() > cap; } }. Save time.