LRU Cache

A Least Recently Used cache implementation built with a hashmap and doubly linked list for O(1) get and put operations.

Overview

This project implements an LRU cache from scratch without using built-in ordered collections. Both get() and put() operations run in constant time.

Implementation

The cache uses two data structures:

• Hashmap: provides O(1) key lookup
• Doubly linked list: maintains usage order, with the most recently used item at the head and least recently used at the tail

When capacity is exceeded, the least recently used item (at the tail) is evicted in O(1) time.

Usage

python demo.py

Testing

pytest -v

License

MIT License, feel free to use, edit or copy for your own project.