LRU Cache in TypeScript

Overview

This project implements a generic Least Recently Used (LRU) Cache using TypeScript.

The cache provides O(1) average time complexity for insertion, retrieval, and deletion by combining a Hash Map with a Doubly Linked List.

---

Features

• Generic implementation using TypeScript
• O(1) get operation
• O(1) set operation
• O(1) delete operation
• Automatic eviction of the Least Recently Used item when capacity is exceeded
• Error handling for invalid cache capacity
• Unit tests using Jest

---

Project Structure

src/
│── Node.ts
│── DoublyLinkedList.ts
│── LRUCache.ts
│── index.ts

tests/
└── __tests__/
    └── lru.test.ts

---

Design Decisions

This implementation combines two data structures:

Map

• Provides O(1) lookup of cache entries.

Doubly Linked List

• Maintains the order of recently used items.
• Head represents the Most Recently Used (MRU).
• Tail represents the Least Recently Used (LRU).

When an item is accessed, it is moved to the front of the list.

When capacity is exceeded, the tail node is removed.

---

Time Complexity

Operation	Complexity
get()	O(1)
set()	O(1)
delete()	O(1)

---

Installation

npm install

---

Run the Project

npm start

---

Run Tests

npm test

---

Example

const cache = new LRUCache<string, number>(3);

cache.set("A", 10);
cache.set("B", 20);
cache.set("C", 30);

cache.get("A");

cache.set("D", 40);

console.log(cache.get("B")); // undefined

---

Future Improvements

• Time To Live (TTL)
• Cache Statistics
• Persistent Storage

---

Author

Arosree Satapathy