Data Structures: O(1) LRU Cache (Doubly Linked List + Hash Map)

Design and implement a Least Recently Used (LRU) Cache in C++ operating in strictly $O(1)$ average time complexity:

• ◦
  Use a custom Doubly Linked List (Node structure with key, value, prev, next) to maintain access order.
• ◦
  Use std::unordered_map<int, Node*> to map keys directly to node pointers for instant $O(1)$ lookup.
• ◦
  Maintain dummy head and tail sentinel nodes to avoid edge-case pointer checks.

• ◦
  LRUCache(int capacity): Initializes the cache with positive capacity.
• ◦
  int get(int key): Returns the value of the key if it exists, otherwise returns -1. Moves the accessed node to the front (head) of the list.
• ◦
  void put(int key, int value): Updates value if key exists (and moves to head). If key does not exist, inserts new node at the head. If capacity is exceeded, evicts the least recently used node from the tail and removes it from the hash map.
• ◦
  void displayCache() const: Displays current cached items from most recently used to least recently used.

• ◦
  Initialize LRUCache cache(2).
• ◦
  Perform sequence: put(1, 10), put(2, 20), get(1), put(3, 30) (evicts key 2), get(2) (returns -1), put(4, 40) (evicts key 1), get(1) (-1), get(3) (30), get(4) (40).