Dynamic Cache System

A Python implementation of a dynamic cache system with LRU (Least Recently Used) and LFU (Least Frequently Used) eviction policies using Doubly Linked Lists and AVL Trees.

Features

• LRU Cache: Implemented using Doubly Linked List (DLL) and HashMap
• LFU Cache: Implemented using AVL Tree for frequency-based eviction
• Menu-driven Interface: Interactive console interface for testing
• Performance Metrics: Tracks hit ratio, miss ratio, and eviction rate
• Write-through Caching: Data consistency between cache and memory

Data Structures Used

1. Doubly Linked List (DLL): For maintaining access order in LRU
2. HashMap: For O(1) lookups of cache entries
3. AVL Tree: For maintaining frequency counts in LFU
4. Integrated Design: DLL + HashMap for efficient cache operations

Time Complexity

• get() operation: O(1)
• put() operation: O(1) amortized
• LRU eviction: O(1)
• Cache display: O(n)

Installation & Usage

# Clone the repository
git clone https://github.com/leena0110/dynamic-cache-system.git

# Navigate to project directory
cd dynamic-cache-system

# Run the cache system
python cache_system.py