Implementing an LRU (Least Recently Used) Cache in JavaScript

LRU caches are a fundamental data structure used to optimize performance in various applications, such as database caching, web server caching, and function memoization. They store a fixed number of key-value pairs and evict the least recently used item when the cache is full. This challenge asks you to implement an LRU cache in JavaScript, demonstrating your understanding of data structures and algorithms.

Problem Description

You are to implement an LRUCache class that supports the following operations:

• get(key): Retrieves the value associated with the given key. If the key exists in the cache, move it to the front (most recently used) and return the value. If the key does not exist, return -1.
• put(key, value): Inserts or updates a key-value pair. If the key already exists, update the value and move the key to the front. If the cache is full, evict the least recently used item before inserting the new key-value pair.

The cache should maintain the order of keys based on their usage, with the most recently used key at the front. The eviction policy should be strictly "Least Recently Used" - the item that hasn't been accessed for the longest time should be removed first.

Examples

Example 1:

Input:
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)      // returns 1
put(3, 3)
get(2)      // returns -1 (evicted)
put(4, 4)
get(1)      // returns -1 (evicted)
get(3)      // returns 3
get(4)      // returns 4

Explanation: The cache is initialized with a capacity of 2. put(1, 1) and put(2, 2) add the key-value pairs. get(1) retrieves the value 1 and moves it to the front. put(3, 3) adds the key-value pair and evicts key 2 because it was the least recently used. get(2) returns -1 because key 2 was evicted. put(4, 4) adds the key-value pair and evicts key 1.

Example 2:

Input:
LRUCache(1)
put(1, 1)
get(2)      // returns -1
put(2, 2)
get(1)      // returns -1

Explanation: The cache has a capacity of 1. put(1, 1) adds the key-value pair. get(2) returns -1 because key 2 doesn't exist. put(2, 2) adds the key-value pair and evicts key 1. get(1) returns -1 because key 1 was evicted.

Example 3: (Edge Case - Capacity 0)

Input:
LRUCache(0)
put(1, 1)
get(1)      // returns -1

Explanation: The cache has a capacity of 0. Any put operations will effectively do nothing, and any get operations will return -1.

Constraints

• 0 <= capacity <= 3000
• 0 <= key <= 1000000
• 0 <= value <= 1000000
• All keys will be integers.
• Values will be integers.
• The number of operations will be at most 2 * 10⁵.
• The time complexity of get and put operations should be O(1).

Notes

Consider using a combination of a hash map (for fast key lookups) and a doubly linked list (to maintain the order of keys based on their usage). The hash map will store the key-value pairs, and the doubly linked list will store the keys in the order of their last access. When a key is accessed (either through get or put), it should be moved to the head of the linked list. When the cache is full and a new key needs to be added, the tail of the linked list (least recently used key) should be removed. Think carefully about how to efficiently update both the hash map and the linked list in O(1) time.