LRU Cache Implementation

class ListNode {
  int key;
  int value;
  ListNode? prev;
  ListNode? next;
  
  ListNode(this.key, this.value);
}

class LRUCache {
  int _capacity;
  Map<int, ListNode> _cache = {};
  ListNode _head = ListNode(-1, -1);
  ListNode _tail = ListNode(-1, -1);
  
  LRUCache(this._capacity) {
    _head.next = _tail;
    _tail.prev = _head;
  }
  
  int get(int key) {
    if (_cache.containsKey(key)) {
      ListNode node = _cache[key]!;
      
      // Move to front (most recently used)
      _removeNode(node);
      _addToFront(node);
      
      return node.value;
    }
    return -1;
  }
  
  void put(int key, int value) {
    if (_cache.containsKey(key)) {
      // Update existing key
      ListNode node = _cache[key]!;
      node.value = value;
      
      // Move to front
      _removeNode(node);
      _addToFront(node);
    } else {
      // Add new key
      if (_cache.length >= _capacity) {
        // Remove least recently used (from tail)
        ListNode lru = _tail.prev!;
        _removeNode(lru);
        _cache.remove(lru.key);
      }
      
      ListNode newNode = ListNode(key, value);
      _addToFront(newNode);
      _cache[key] = newNode;
    }
  }
  
  void _removeNode(ListNode node) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
  
  void _addToFront(ListNode node) {
    node.next = _head.next;
    node.prev = _head;
    _head.next!.prev = node;
    _head.next = node;
  }
  
  List<String> getKeys() {
    List<String> keys = [];
    ListNode? current = _head.next;
    while (current != _tail) {
      keys.add('{current!.key}:{current.value}');
      current = current.next;
    }
    return keys;
  }
}

void main() {
  LRUCache cache = LRUCache(3);
  
  cache.put(1, 10);
  cache.put(2, 20);
  cache.put(3, 30);
  
  print('Cache after adding 1,2,3: {cache.getKeys()}');
  
  print('Get key 2: {cache.get(2)}');
  print('Cache after accessing 2: {cache.getKeys()}');
  
  cache.put(4, 40); // This should evict key 1
  print('Cache after adding 4: {cache.getKeys()}');
}