LRU Cache Visualizer

An interactive web application that visualizes the Least Recently Used (LRU) Cache data structure with a beautiful, modern UI. This project provides both a visual learning tool and a production-ready LRU Cache implementation in TypeScript.

🌟 Features

• Interactive Visualization: Watch the LRU Cache in action with real-time visual feedback
• Production-Ready Implementation: Efficient O(1) time complexity for both get and put operations
• Modern UI: Beautiful interface with dark mode support
• Educational: Perfect for learning how LRU Cache works
• TypeScript: Fully typed for better developer experience
• Comprehensive Testing: Well-tested with high code coverage

📚 What is an LRU Cache?

A Least Recently Used (LRU) Cache is a data structure that stores a limited number of items and automatically evicts the least recently used item when the cache reaches its capacity. It's widely used in:

• Operating Systems: Page replacement algorithms
• Web Browsers: Browser cache management
• Databases: Query result caching
• CDNs: Content delivery optimization
• APIs: Response caching

How It Works

1. Get Operation: Retrieve a value by key and mark it as recently used
2. Put Operation: Insert or update a key-value pair
3. Eviction: When capacity is exceeded, remove the least recently used item

Algorithm Complexity

Operation	Time Complexity	Space Complexity
get(key)	O(1)	O(capacity)
put(key, value)	O(1)	O(capacity)

Implementation Details

This implementation uses:

• Circular Doubly-Linked List: For maintaining access order
• HashMap: For O(1) key lookups
• Head Pointer: Points to the most recently used item

🚀 Quick Start

Prerequisites

• Node.js 18+ and npm/yarn/pnpm

Installation

# Clone the repository
git clone https://github.com/Akshayy67/LRU-Cache.git
cd LRU-Cache

# Install dependencies
npm install

# Run the development server
npm run dev

Visit http://localhost:5173 to see the visualizer in action!

Build for Production

npm run build
npm run preview

💻 Usage

Using the Visualizer

1. Set Capacity: Choose the maximum number of items (1-10)
2. Put Operation: Enter a key and value, then click "Put"
3. Get Operation: Enter a key and click "Get"
4. Clear Cache: Reset the cache to start fresh
5. View Logs: See a timestamped history of all operations

Using the LRU Cache Class

Basic Usage

import { LRUCache } from './src/utils/LRUCache';

// Create a cache with capacity 3
const cache = new LRUCache(3);

// Add items
cache.put(1, 100);
cache.put(2, 200);
cache.put(3, 300);

// Get an item (returns the value and marks it as recently used)
const value = cache.get(1); // Returns 100

// Add another item (will evict the least recently used)
cache.put(4, 400); // Evicts key 2 (least recently used)

// Try to get evicted item
cache.get(2); // Returns -1 (not found)

// Get current state
const state = cache.getState();
console.log(state); // [{ key: 4, value: 400 }, { key: 1, value: 100 }, { key: 3, value: 300 }]

Advanced Example

// Create a cache for storing user sessions
const sessionCache = new LRUCache(100);

// Store session data
sessionCache.put(userId, sessionData);

// Retrieve session (marks as recently used)
const session = sessionCache.get(userId);

if (session === -1) {
  // Session expired or not found
  createNewSession(userId);
} else {
  // Session found and refreshed
  continueSession(session);
}

📖 API Reference

LRUCache

Constructor

constructor(capacity: number)

Creates a new LRU Cache with the specified capacity.

Parameters:

• capacity (number): Maximum number of items the cache can hold. Must be a positive integer.

Throws:

• Error: If capacity is not a positive integer.

Example:

const cache = new LRUCache(5);

Methods

get(key: number): number

Retrieves the value associated with the key. If the key exists, it's marked as recently used.

Parameters:

• key (number): The key to look up

Returns:

• number: The value associated with the key, or -1 if not found

Time Complexity: O(1)

Example:

const value = cache.get(1); // Returns value or -1

put(key: number, value: number): void

Inserts or updates a key-value pair. If the cache is at capacity, the least recently used item is evicted.

Parameters:

• key (number): The key to insert/update
• value (number): The value to store

Returns: void

Time Complexity: O(1)

Example:

cache.put(1, 100);
cache.put(1, 200); // Updates existing key

getState(): Array<{ key: number; value: number }>

Returns the current state of the cache as an array, ordered from most recently used to least recently used.

Returns:

• Array<{ key: number; value: number }>: Array of key-value pairs

Time Complexity: O(n) where n is the number of items in cache

Example:

const state = cache.getState();
// [{ key: 3, value: 300 }, { key: 1, value: 100 }]

🧪 Testing

Run the test suite:

npm test

Run tests with coverage:

npm run test:coverage

🏗️ Project Structure

LRU-Cache/
├── src/
│   ├── components/
│   │   ├── Description.tsx    # Algorithm explanation component
│   │   └── Visualizer.tsx     # Interactive visualizer component
│   ├── utils/
│   │   └── LRUCache.ts        # Core LRU Cache implementation
│   ├── App.tsx                # Main application component
│   ├── main.tsx               # Application entry point
│   └── index.css              # Global styles
├── examples/
│   ├── basic-usage.ts         # Basic usage examples
│   ├── node-example.js        # Node.js usage example
│   └── performance.ts         # Performance benchmarks
├── tests/
│   └── LRUCache.test.ts       # Unit tests
├── public/                    # Static assets
├── package.json
├── tsconfig.json
├── vite.config.ts
└── README.md

🎨 Technologies Used

• TypeScript: Type-safe JavaScript
• React: UI library
• Vite: Build tool and dev server
• TailwindCSS: Utility-first CSS framework
• Lucide React: Beautiful icons
• Vitest: Unit testing framework

🤝 Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

Please read CONTRIBUTING.md for details on our code of conduct and the process for submitting pull requests.

📝 License

This project is licensed under the MIT License - see the LICENSE file for details.

👨‍💻 Author

Akshay Juluri

• GitHub: @Akshayy67
• Email: akshayjuluri6704@gmail.com

🙏 Acknowledgments

• Inspired by the need for better data structure visualization tools
• Built with modern web technologies
• Thanks to the open-source community

📚 Learn More

• LRU Cache on Wikipedia
• LeetCode Problem: LRU Cache
• System Design: Caching Strategies

🐛 Known Issues

None at the moment. Please report any issues you find!

🗺️ Roadmap

• Add support for generic key-value types
• Implement TTL (Time To Live) for cache entries
• Add export/import cache state functionality
• Create mobile-responsive design improvements
• Add animation speed controls
• Support for different eviction policies (LFU, FIFO, etc.)

---

Made with ❤️ by Akshay Juluri