Lru cache

Hash Table Linked List Design Doubly-Linked List

46.9% acceptance

Feb 27, 2026

22941

1229

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

* impl LRUCache {

 *     fn new(capacity: i32) -> Self {

 *     }

 *     fn get(&self, key: i32) -> i32 {

 *     }

 *     fn put(&self, key: i32, value: i32) {

 *     }
 * }
 */

use std::cell::RefCell;
use std::rc::Rc;
impl Node {
  fn new(key: i32, val: i32) -> Rc<RefCell<Self>> {
    Rc::new(RefCell::new(Node {
      key,
      val,
      prev: None,
      next: None,
    }))
  }
}

impl LRUCache {
  fn new(capacity: i32) -> Self {
    LRUCache {
      capacity: capacity as usize,
      map: std::collections::HashMap::new(),
      head: None,
      tail: None,
    }
  }
  
  fn remove(&mut self, node: &Rc<RefCell<Node>>) {
    let prev = node.borrow().prev.clone();
    let next = node.borrow().next.clone();
    
    match (prev.as_ref(), next.as_ref()) {
      (Some(p), Some(n)) => {
        p.borrow_mut().next = Some(n.clone());
        n.borrow_mut().prev = Some(p.clone());
      }
      (None, Some(n)) => {
        n.borrow_mut().prev = None;
        self.head = Some(n.clone());
      }
      (Some(p), None) => {
        p.borrow_mut().next = None;
        self.tail = Some(p.clone());
      }
      (None, None) => {
        self.head = None;
        self.tail = None;
      }
    }
  }
  
  fn add_to_front(&mut self, node: &Rc<RefCell<Node>>) {
    node.borrow_mut().prev = None;
    node.borrow_mut().next = self.head.clone();
    
    if let Some(head) = self.head.as_ref() {
      head.borrow_mut().prev = Some(node.clone());
    } else {
      self.tail = Some(node.clone());
    }
    self.head = Some(node.clone());
  }
  
  fn get(&mut self, key: i32) -> i32 {
    if let Some(node) = self.map.get(&key).cloned() {
      let val = node.borrow().val;
      self.remove(&node);
      self.add_to_front(&node);
      val
    } else {
      -1
    }
  }
  
  fn put(&mut self, key: i32, value: i32) {
    if let Some(node) = self.map.get(&key).cloned() {
      node.borrow_mut().val = value;
      self.remove(&node);
      self.add_to_front(&node);
    } else {
      let node = Node::new(key, value);
      self.map.insert(key, node.clone());
      self.add_to_front(&node);
      
      if self.map.len() > self.capacity {
        if let Some(tail) = self.tail.clone() {
          let key = tail.borrow().key;
          self.remove(&tail);
          self.map.remove(&key);
        }
      }
    }
  }
}