use std::collections::HashMap;
use std::hash::Hash;
const NIL: usize = usize::MAX;
struct Node<K, V> {
key: K,
value: V,
prev: usize,
next: usize,
}
pub struct LruCache<K, V> {
map: HashMap<K, usize>,
nodes: Vec<Node<K, V>>,
free: Vec<usize>,
head: usize,
tail: usize,
cap: usize,
}impl<K: Eq + Hash + Clone, V> LruCache<K, V> {
pub fn new(cap: usize) -> Self {
assert!(cap > 0, "capacity must be non-zero");
LruCache {
map: HashMap::with_capacity(cap),
nodes: Vec::with_capacity(cap),
free: Vec::new(),
head: NIL,
tail: NIL,
cap,
}
}
fn unlink(&mut self, idx: usize) {
let (prev, next) = (self.nodes[idx].prev, self.nodes[idx].next);
if prev != NIL {
self.nodes[prev].next = next;
} else {
self.head = next;
}
if next != NIL {
self.nodes[next].prev = prev;
} else {
self.tail = prev;
}
}
fn push_front(&mut self, idx: usize) {
self.nodes[idx].prev = NIL;
self.nodes[idx].next = self.head;
if self.head != NIL {
self.nodes[self.head].prev = idx;
}
self.head = idx;
if self.tail == NIL {
self.tail = idx;
}
}
}impl<K: Eq + Hash + Clone, V> LruCache<K, V> {
pub fn get(&mut self, key: &K) -> Option<&V> {
let idx = *self.map.get(key)?;
self.unlink(idx);
self.push_front(idx);
Some(&self.nodes[idx].value)
}
pub fn put(&mut self, key: K, value: V) {
if let Some(&idx) = self.map.get(&key) {
self.nodes[idx].value = value;
self.unlink(idx);
self.push_front(idx);
return;
}
let idx = match self.free.pop() {
Some(slot) => {
self.nodes[slot] = Node { key: key.clone(), value, prev: NIL, next: NIL };
slot
}
None => {
self.nodes.push(Node { key: key.clone(), value, prev: NIL, next: NIL });
self.nodes.len() - 1
}
};
self.map.insert(key, idx);
self.push_front(idx);
if self.map.len() > self.cap {
self.evict();
}
}
fn evict(&mut self) {
let victim = self.tail;
if victim == NIL {
return;
}
self.unlink(victim);
let key = self.nodes[victim].key.clone();
self.map.remove(&key);
self.free.push(victim);
}
pub fn len(&self) -> usize {
self.map.len()
}
}An LRU (least-recently-used) cache must answer two questions in constant time: given a key, where is its value, and which entry is the coldest one to evict when capacity is exceeded. A HashMap alone gives O(1) lookup but no ordering; a linked list alone gives O(1) reordering but no lookup. Combining them is the classic solution, and Lru cache shows the standard shape: a HashMap<K, usize> maps keys to node handles, while a doubly linked list keeps the entries ordered from most- to least-recently-used.
The subtle part in Rust is the list itself. A pointer-based list fights the borrow checker, so Node struct and LruCache use an arena: nodes live in a Vec<Node<K, V>> and links are plain usize indices rather than references. Freed slots are recycled through a free stack, which avoids unbounded growth as entries churn. This is an intrusive, index-based list — safe code, no unsafe, no Rc/RefCell overhead.
The internal helpers in list operations do the real work. unlink detaches a node by patching its neighbours' prev/next indices, carefully updating head or tail when the node sits at either end. push_front re-inserts a node as the new head, which is how a touched entry becomes most-recently-used. Because both operate purely on indices, they never move the underlying Vec data and stay O(1).
In public API, get looks up the index, unlinks the node, and pushes it to the front so recency is refreshed on every access. put either updates an existing entry (and promotes it) or allocates a slot — reusing a free index when available — and, once len exceeds cap, evicts the current tail via evict, removing it from the map and returning its slot to the pool.
The trade-offs are worth noting: the arena keeps allocations low and pointers safe, but stores keys twice (once in the map, once in the node for eviction cleanup). The design assumes single-threaded use; concurrent access needs an external lock. It is the right tool when a bounded, hot working set must be served with predictable constant-time cost.
Related snips
struct Config<'a> {
name: &'a str,
value: &'a str,
}
fn parse_config(line: &str) -> Config {Lifetime annotations for flexible borrowing in structs
require "csv"
class PeopleCsvStream
include Enumerable
HEADERS = %w[id full_name email signed_up_at plan].freezeResilient CSV Export as a Streamed Response
use crossbeam::channel::unbounded;
use std::thread;
fn main() {
let (tx, rx) = unbounded();Crossbeam for advanced concurrent data structures
use tracing::{info, instrument};
#[instrument]
fn process_request(user_id: u64) {
info!(user_id, "Processing request");
// Work happens heretracing for structured logging and distributed tracing
use std::sync::mpsc;
use std::thread;
fn main() {
let (tx, rx) = mpsc::channel();Channels (mpsc) for message passing between threads
use clap::Parser;
#[derive(Parser, Debug)]
#[command(author, version, about)]
struct Args {
#[arg(short, long)]clap for CLI argument parsing with derive macros
Share this code
Here's the card — post it anywhere.
