Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**. Implement the `LRUCache` class with `get(key)` and `put(key, value)` methods, both running in **O(1)** average time complexity. When the cache reaches capacity, evict the least recently used item before inserting a new one.
Input: LRUCache(2) → put(1,1) → put(2,2) → get(1) → put(3,3) → get(2) → put(4,4) → get(1) → get(3) → get(4)
Output: 1, -1, -1, 3, 4
After put(3,3), key 2 is evicted. After put(4,4), key 1 is evicted.