LRU Cache

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(1)	O(log n)	O(log n)	O(log n)

Definition

Short

LRU Cache is a cache data structure that evicts the least recently used item when it is full.

Simplified

LRU Cache is like a clothes rack. It holds a limited amount of data. When new data comes in, it removes the least recently used data, similar to removing the least worn clothing from a full rack to make room for a new one. This keeps frequently used data quickly accessible.

Detailed

The Least Recently Used (LRU) Cache is a cache replacement algorithm that discards the least recently used items first. It can be implemented using a combination of a doubly linked list and a hash map for quick access and efficient operations or ordered map.

Practice

Practice

Aspect	Pseudo Code
LRU Cache on Map	get(key): if key not in items: return ø value = items.get(key) items.delete(key) items.set(key, value) return value set(key, value): items.delete(key) items.set(key, value) if items.size > capacity: for each head_key in items.keys(): items.delete(head_key) break
LRU Cache on Linked List	get(key): if nodes_map[key] == ø: return ø node = nodes_map[key] promote(node) return node.value set(key, value): if nodes_map[key] == ø: node = LinkedListNode(key, value) append(node) else: node = nodes_map[key] node.value = value promote(node) promote(node): evict(node) append(node) append(node): nodes_map[node.key] = node if head.next != ø: head.next = node tail.prev = node node.prev = head node.next = tail else: old_tail = tail.prev old_tail.next = node node.prev = old_tail node.next = tail tail.prev = node size += 1 if size > capacity: evict(head.next) evict(node): delete nodes_map[node.key] size -= 1 prev_node = node.prev next_node = node.next if prev_node == head and next_node == tail: head.next = ø tail.prev = ø size = 0 else if prev_node == head: next_node.prev = head head.next = next_node else if next_node == tail: prev_node.next = tail tail.prev = prev_node else: prev_node.next = next_node next_node.prev = prev_node

Solution

package main

import (
	"container/list"
)

type LRUCacheOnMap struct {
	capacity int
	items    map[interface{}]interface{}
}

func NewLRUCacheOnMap(capacity int) *LRUCacheOnMap {
	return &LRUCacheOnMap{
		capacity: capacity,
		items:    make(map[interface{}]interface{}),
	}
}

func (lru *LRUCacheOnMap) Get(key interface{}) interface{} {
	if val, ok := lru.items[key]; ok {
		delete(lru.items, key)
		lru.items[key] = val
		return val
	}
	return nil
}

func (lru *LRUCacheOnMap) Set(key, val interface{}) {
	delete(lru.items, key)
	lru.items[key] = val
	if len(lru.items) > lru.capacity {
		for headKey := range lru.items {
			delete(lru.items, headKey)
			break
		}
	}
}

type LinkedListNode struct {
	key, val  interface{}
	prev, next *LinkedListNode
}

type LRUCache struct {
	capacity int
	nodesMap map[interface{}]*LinkedListNode
	size     int
	head     *LinkedListNode
	tail     *LinkedListNode
}

func NewLRUCache(capacity int) *LRUCache {
	head := &LinkedListNode{}
	tail := &LinkedListNode{}
	head.next = tail
	tail.prev = head

	return &LRUCache{
		capacity: capacity,
		nodesMap: make(map[interface{}]*LinkedListNode),
		size:     0,
		head:     head,
		tail:     tail,
	}
}

func (lru *LRUCache) Get(key interface{}) interface{} {
	if node, ok := lru.nodesMap[key]; ok {
		lru.promote(node)
		return node.val
	}
	return nil
}

func (lru *LRUCache) Set(key, val interface{}) {
	if node, ok := lru.nodesMap[key]; ok {
		node.val = val
		lru.promote(node)
	} else {
		node := &LinkedListNode{key: key, val: val}
		lru.append(node)
	}
}

func (lru *LRUCache) promote(node *LinkedListNode) {
	lru.evict(node)
	lru.append(node)
}

func (lru *LRUCache) append(node *LinkedListNode) {
	lru.nodesMap[node.key] = node

	oldTail := lru.tail.prev
	oldTail.next = node
	node.prev = oldTail
	node.next = lru.tail
	lru.tail.prev = node

	lru.size++

	if lru.size > lru.capacity {
		lru.evict(lru.head.next)
	}
}

func (lru *LRUCache) evict(node *LinkedListNode) {
	delete(lru.nodesMap, node.key)
	lru.size--

	prevNode := node.prev
	nextNode := node.next

	prevNode.next = nextNode
	nextNode.prev = prevNode
}

import java.util.HashMap;
import java.util.Map;

class LRUCacheOnMap {

  private final int capacity;
  private final Map<Object, Object> items;

  public LRUCacheOnMap(int capacity) {
    this.capacity = capacity;
    this.items = new HashMap<>();
  }

  public Object get(Object key) {
    if (!items.containsKey(key)) {
      return null;
    }
    Object val = items.remove(key);
    items.put(key, val);
    return val;
  }

  public void set(Object key, Object val) {
    items.remove(key);
    items.put(key, val);
    if (items.size() > capacity) {
      for (Object headKey : items.keySet()) {
        items.remove(headKey);
        break;
      }
    }
  }
}

class LinkedListNode {

  public Object key;
  public Object val;
  public LinkedListNode prev;
  public LinkedListNode next;

  public LinkedListNode(Object key, Object val, LinkedListNode prev, LinkedListNode next) {
    this.key = key;
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

class LRUCache {

  private final int capacity;
  private final Map<Object, LinkedListNode> nodesMap;
  private final LinkedListNode head;
  private final LinkedListNode tail;
  private int size;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.nodesMap = new HashMap<>();
    this.size = 0;
    this.head = new LinkedListNode(null, null, null, null);
    this.tail = new LinkedListNode(null, null, null, null);
    this.head.next = tail;
    this.tail.prev = head;
  }

  public Object get(Object key) {
    if (!nodesMap.containsKey(key)) {
      return null;
    }
    LinkedListNode node = nodesMap.get(key);
    promote(node);
    return node.val;
  }

  public void set(Object key, Object val) {
    if (nodesMap.containsKey(key)) {
      LinkedListNode node = nodesMap.get(key);
      node.val = val;
      promote(node);
    } else {
      LinkedListNode node = new LinkedListNode(key, val, null, null);
      append(node);
    }
  }

  private void promote(LinkedListNode node) {
    evict(node);
    append(node);
  }

  private void append(LinkedListNode node) {
    nodesMap.put(node.key, node);

    LinkedListNode oldTail = tail.prev;
    oldTail.next = node;
    node.prev = oldTail;
    node.next = tail;
    tail.prev = node;

    size += 1;

    if (size > capacity) {
      evict(head.next);
    }
  }

  private void evict(LinkedListNode node) {
    nodesMap.remove(node.key);
    size -= 1;

    LinkedListNode prevNode = node.prev;
    LinkedListNode nextNode = node.next;

    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }
}

class LRUCacheOnMap {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = new Map();
  }

  get(key) {
    if (!this.items.has(key)) {
      return undefined;
    }
    const val = this.items.get(key);
    this.items.delete(key);
    this.items.set(key, val);
    return val;
  }

  set(key, val) {
    this.items.delete(key);
    this.items.set(key, val);
    if (this.items.size > this.capacity) {
      for (const headKey of this.items.keys()) {
        this.items.delete(headKey);
        break;
      }
    }
  }
}

class LinkedListNode {
  constructor(key, val, prev = null, next = null) {
    this.key = key;
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodesMap = {};
    this.size = 0;
    this.head = new LinkedListNode();
    this.tail = new LinkedListNode();
  }

  get(key) {
    if (this.nodesMap[key] === undefined) {
      return undefined;
    }
    const node = this.nodesMap[key];
    this.promote(node);
    return node.val;
  }

  set(key, val) {
    if (this.nodesMap[key]) {
      const node = this.nodesMap[key];
      node.val = val;
      this.promote(node);
    } else {
      const node = new LinkedListNode(key, val);
      this.append(node);
    }
  }

  promote(node) {
    this.evict(node);
    this.append(node);
  }

  append(node) {
    this.nodesMap[node.key] = node;

    if (!this.head.next) {
      this.head.next = node;
      this.tail.prev = node;
      node.prev = this.head;
      node.next = this.tail;
    } else {
      const oldTail = this.tail.prev;
      oldTail.next = node;
      node.prev = oldTail;
      node.next = this.tail;
      this.tail.prev = node;
    }

    this.size += 1;

    if (this.size > this.capacity) {
      this.evict(this.head.next);
    }
  }

  evict(node) {
    delete this.nodesMap[node.key];
    this.size -= 1;

    const prevNode = node.prev;
    const nextNode = node.next;

    if (prevNode === this.head && nextNode === this.tail) {
      this.head.next = null;
      this.tail.prev = null;
      this.size = 0;
      return;
    }

    if (prevNode === this.head) {
      nextNode.prev = this.head;
      this.head.next = nextNode;
      return;
    }

    if (nextNode === this.tail) {
      prevNode.next = this.tail;
      this.tail.prev = prevNode;
      return;
    }

    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }
}

class LRUCacheOnMap(private val capacity: Int) {
    private val items = mutableMapOf<Any, Any>()

    fun get(key: Any): Any? {
        if (!items.containsKey(key)) return null
        val value = items.remove(key)
        items[key] = value!!
        return value
    }

    fun set(key: Any, value: Any) {
        items.remove(key)
        items[key] = value
        if (items.size > capacity) {
            val headKey = items.keys.firstOrNull()
            items.remove(headKey)
        }
    }
}

class LinkedListNode(
        val key: Any,
        val value: Any,
        var prev: LinkedListNode? = null,
        var next: LinkedListNode? = null
)

class LRUCache(private val capacity: Int) {
    private val nodesMap = mutableMapOf<Any, LinkedListNode>()
    private var size = 0
    private val head = LinkedListNode(0, 0)
    private val tail = LinkedListNode(0, 0)

    fun get(key: Any): Any? {
        if (!nodesMap.containsKey(key)) return null
        val node = nodesMap[key]!!
        promote(node)
        return node.value
    }

    fun set(key: Any, value: Any) {
        if (nodesMap.containsKey(key)) {
            val node = nodesMap[key]!!
            node.value = value
            promote(node)
        } else {
            val node = LinkedListNode(key, value)
            append(node)
        }
    }

    private fun promote(node: LinkedListNode) {
        evict(node)
        append(node)
    }

    private fun append(node: LinkedListNode) {
        nodesMap[node.key] = node

        if (head.next == null) {
            head.next = node
            tail.prev = node
            node.prev = head
            node.next = tail
        } else {
            val oldTail = tail.prev!!
            oldTail.next = node
            node.prev = oldTail
            node.next = tail
            tail.prev = node
        }

        size += 1

        if (size > capacity) {
            evict(head.next!!)
        }
    }

    private fun evict(node: LinkedListNode) {
        nodesMap.remove(node.key)
        size -= 1

        val prevNode = node.prev!!
        val nextNode = node.next!!

        if (prevNode == head && nextNode == tail) {
            head.next = null
            tail.prev = null
            size = 0
            return
        }

        if (prevNode == head) {
            nextNode.prev = head
            head.next = nextNode
            return
        }

        if (nextNode == tail) {
            prevNode.next = tail
            tail.prev = prevNode
            return
        }

        prevNode.next = nextNode
        nextNode.prev = prevNode
    }
}

class LRUCacheOnMap:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = {}

    def get(self, key):
        if key not in self.items:
            return None
        val = self.items.pop(key)
        self.items[key] = val
        return val

    def set(self, key, val):
        if key in self.items:
            del self.items[key]
        self.items[key] = val
        if len(self.items) > self.capacity:
            head_key = next(iter(self.items))
            del self.items[head_key]


class LinkedListNode:
    def __init__(self, key, val, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes_map = {}
        self.size = 0
        self.head = LinkedListNode(None, None)
        self.tail = LinkedListNode(None, None)

    def get(self, key):
        if key not in self.nodes_map:
            return None
        node = self.nodes_map[key]
        self.promote(node)
        return node.val

    def set(self, key, val):
        if key in self.nodes_map:
            node = self.nodes_map[key]
            node.val = val
            self.promote(node)
        else:
            node = LinkedListNode(key, val)
            self.append(node)

    def promote(self, node):
        self.evict(node)
        self.append(node)

    def append(self, node):
        self.nodes_map[node.key] = node

        if not self.head.next:
            self.head.next = node
            self.tail.prev = node
            node.prev = self.head
            node.next = self.tail
        else:
            old_tail = self.tail.prev
            old_tail.next = node
            node.prev = old_tail
            node.next = self.tail
            self.tail.prev = node

        self.size += 1

        if self.size > self.capacity:
            self.evict(self.head.next)

    def evict(self, node):
        if node:
            del self.nodes_map[node.key]
            self.size -= 1

            prev_node = node.prev
            next_node = node.next

            if prev_node == self.head and next_node == self.tail:
                self.head.next = None
                self.tail.prev = None
                self.size = 0
                return

            if prev_node == self.head:
                next_node.prev = self.head
                self.head.next = next_node
                return

            if next_node == self.tail:
                prev_node.next = self.tail
                self.tail.prev = prev_node
                return

            prev_node.next = next_node
            next_node.prev = prev_node

use std::collections::{HashMap, LinkedList};

struct LRUCacheOnMap {
    capacity: usize,
    items: HashMap<String, i32>,
}

impl LRUCacheOnMap {
    fn new(capacity: usize) -> Self {
        LRUCacheOnMap {
            capacity,
            items: HashMap::new(),
        }
    }

    fn get(&mut self, key: &str) -> Option<i32> {
        if let Some(val) = self.items.remove(key) {
            self.items.insert(key.to_string(), val);
            Some(val)
        } else {
            None
        }
    }

    fn set(&mut self, key: &str, val: i32) {
        self.items.remove(key);
        self.items.insert(key.to_string(), val);

        if self.items.len() > self.capacity {
            if let Some(head_key) = self.items.keys().next().cloned() {
                self.items.remove(&head_key);
            }
        }
    }
}

struct LinkedListNode {
    key: String,
    val: i32,
    prev: Option<Box<LinkedListNode>>,
    next: Option<Box<LinkedListNode>>,
}

impl LinkedListNode {
    fn new(key: String, val: i32, prev: Option<Box<LinkedListNode>>, next: Option<Box<LinkedListNode>>) -> Self {
        LinkedListNode { key, val, prev, next }
    }
}

struct LRUCache {
    capacity: usize,
    nodes_map: HashMap<String, Box<LinkedListNode>>,
    size: usize,
    head: Box<LinkedListNode>,
    tail: Box<LinkedListNode>,
}

impl LRUCache {
    fn new(capacity: usize) -> Self {
        let head = Box::new(LinkedListNode::new("".to_string(), 0, None, None));
        let tail = Box::new(LinkedListNode::new("".to_string(), 0, None, None));

        LRUCache {
            capacity,
            nodes_map: HashMap::new(),
            size: 0,
            head: head.clone(),
            tail: tail.clone(),
        }
    }

    fn get(&mut self, key: &str) -> Option<i32> {
        if let Some(node) = self.nodes_map.get_mut(key) {
            self.promote(node);
            Some(node.val)
        } else {
            None
        }
    }

    fn set(&mut self, key: &str, val: i32) {
        if let Some(node) = self.nodes_map.get_mut(key) {
            node.val = val;
            self.promote(node);
        } else {
            let node = Box::new(LinkedListNode::new(key.to_string(), val, None, None));
            self.append(node);
        }
    }

    fn promote(&mut self, node: &mut Box<LinkedListNode>) {
        self.evict(node);
        self.append(node.clone());
    }

    fn append(&mut self, mut node: Box<LinkedListNode>) {
        self.nodes_map.insert(node.key.clone(), node.clone());

        if self.head.next.is_none() {
            self.head.next = Some(node.clone());
            self.tail.prev = Some(node.clone());
            node.prev = Some(self.head.clone());
            node.next = Some(self.tail.clone());
        } else {
            let old_tail = self.tail.prev.take().unwrap();
            old_tail.next = Some(node.clone());
            node.prev = Some(old_tail.clone());
            node.next = Some(self.tail.clone());
            self.tail.prev = Some(node.clone());
        }

        self.size += 1;

        if self.size > self.capacity {
            self.evict(self.head.next.as_deref().unwrap());
        }
    }

    fn evict(&mut self, node: Option<&Box<LinkedListNode>>) {
        if let Some(node) = node {
            self.nodes_map.remove(&node.key);
            self.size -= 1;

            let prev_node = node.prev.as_deref().unwrap();
            let next_node = node.next.as_deref().unwrap();

            if prev_node == &self.head && next_node == &self.tail {
                self.head.next = None;
                self.tail.prev = None;
                self.size = 0;
                return;
            }

            if prev_node == &self.head {
                next_node.prev = Some(self.head.clone());
                self.head.next = Some(next_node.clone());
                return;
            }

            if next_node == &self.tail {
                prev_node.next = Some(self.tail.clone());
                self.tail.prev = Some(prev_node.clone());
                return;
            }

            prev_node.next = Some(next_node.clone());
            next_node.prev = Some(prev_node.clone());
        }
    }
}

class LRUCacheOnMap {
  private capacity: number;
  private items: Map<string, any>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Map<string, any>();
  }

  get(key: string): any | undefined {
    if (!this.items.has(key)) {
      return undefined;
    }
    const val = this.items.get(key);
    this.items.delete(key);
    this.items.set(key, val);
    return val;
  }

  set(key: string, val: any): void {
    this.items.delete(key);
    this.items.set(key, val);
    if (this.items.size > this.capacity) {
      for (const headKey of this.items.keys()) {
        this.items.delete(headKey);
        break;
      }
    }
  }
}

class LinkedListNode {
  public key: string;
  public val: any;
  public prev: LinkedListNode | null;
  public next: LinkedListNode | null;

  constructor(
    key: string,
    val: any,
    prev: LinkedListNode | null = null,
    next: LinkedListNode | null = null,
  ) {
    this.key = key;
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

class LRUCache {
  private capacity: number;
  private nodesMap: { [key: string]: LinkedListNode };
  private size: number;
  private head: LinkedListNode;
  private tail: LinkedListNode;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.nodesMap = {};
    this.size = 0;
    this.head = new LinkedListNode("", null);
    this.tail = new LinkedListNode("", null);
  }

  get(key: string): any | undefined {
    if (this.nodesMap[key] === undefined) {
      return undefined;
    }
    const node = this.nodesMap[key];
    this.promote(node);
    return node.val;
  }

  set(key: string, val: any): void {
    if (this.nodesMap[key]) {
      const node = this.nodesMap[key];
      node.val = val;
      this.promote(node);
    } else {
      const node = new LinkedListNode(key, val);
      this.append(node);
    }
  }

  private promote(node: LinkedListNode): void {
    this.evict(node);
    this.append(node);
  }

  private append(node: LinkedListNode): void {
    this.nodesMap[node.key] = node;

    if (!this.head.next) {
      this.head.next = node;
      this.tail.prev = node;
      node.prev = this.head;
      node.next = this.tail;
    } else {
      const oldTail = this.tail.prev as LinkedListNode;
      oldTail.next = node;
      node.prev = oldTail;
      node.next = this.tail;
      this.tail.prev = node;
    }

    this.size += 1;

    if (this.size > this.capacity) {
      this.evict(this.head.next as LinkedListNode);
    }
  }

  private evict(node: LinkedListNode): void {
    delete this.nodesMap[node.key];
    this.size -= 1;

    const prevNode = node.prev as LinkedListNode;
    const nextNode = node.next as LinkedListNode;

    if (prevNode === this.head && nextNode === this.tail) {
      this.head.next = null;
      this.tail.prev = null;
      this.size = 0;
      return;
    }

    if (prevNode === this.head) {
      nextNode.prev = this.head;
      this.head.next = nextNode;
      return;
    }

    if (nextNode === this.tail) {
      prevNode.next = this.tail;
      this.tail.prev = prevNode;
      return;
    }

    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }
}