#include <stdlib.h>
#define MAX_KEY 10000 // 0 <= key <= 10^4, so an array can replace the hash map
typedef struct Node {
int key, value;
struct Node *prev, *next;
} Node;
typedef struct {
int cap, size;
Node *head, *tail; // dummy nodes
Node *map[MAX_KEY + 1];
} LRUCache;
static Node *newNode(int key, int value) {
Node *n = malloc(sizeof(Node));
n->key = key;
n->value = value;
n->prev = n->next = NULL;
return n;
}
static void removeNode(Node *n) {
n->prev->next = n->next;
n->next->prev = n->prev;
}
static void insertFront(LRUCache *obj, Node *n) {
n->prev = obj->head;
n->next = obj->head->next;
obj->head->next->prev = n;
obj->head->next = n;
}
LRUCache *lRUCacheCreate(int capacity) {
LRUCache *obj = calloc(1, sizeof(LRUCache));
obj->cap = capacity;
obj->head = newNode(0, 0);
obj->tail = newNode(0, 0);
obj->head->next = obj->tail;
obj->tail->prev = obj->head;
return obj;
}
int lRUCacheGet(LRUCache *obj, int key) {
Node *n = obj->map[key];
if (!n)
return -1;
removeNode(n);
insertFront(obj, n);
return n->value;
}
void lRUCachePut(LRUCache *obj, int key, int value) {
Node *n = obj->map[key];
if (n) {
n->value = value;
removeNode(n);
insertFront(obj, n);
return;
}
if (obj->size == obj->cap) {
Node *lru = obj->tail->prev;
removeNode(lru);
obj->map[lru->key] = NULL; // clear before free
free(lru);
obj->size--;
}
n = newNode(key, value);
obj->map[key] = n;
insertFront(obj, n);
obj->size++;
}
void lRUCacheFree(LRUCache *obj) {
Node *cur = obj->head;
while (cur) {
Node *nxt = cur->next;
free(cur);
cur = nxt;
}
free(obj);
}
#include <unordered_map>
using namespace std;
class LRUCache {
struct Node {
int key, value;
Node *prev = nullptr, *next = nullptr;
Node(int k = 0, int v = 0) : key(k), value(v) {}
};
int cap;
Node *head, *tail; // dummy nodes
unordered_map<int, Node *> map;
void remove(Node *n) {
n->prev->next = n->next;
n->next->prev = n->prev;
}
void insertFront(Node *n) {
n->prev = head;
n->next = head->next;
head->next->prev = n;
head->next = n;
}
public:
LRUCache(int capacity) : cap(capacity) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
~LRUCache() {
Node *cur = head;
while (cur) {
Node *nxt = cur->next;
delete cur;
cur = nxt;
}
}
int get(int key) {
auto it = map.find(key);
if (it == map.end())
return -1;
Node *n = it->second;
remove(n);
insertFront(n);
return n->value;
}
void put(int key, int value) {
auto it = map.find(key);
if (it != map.end()) {
Node *n = it->second;
n->value = value;
remove(n);
insertFront(n);
return;
}
if ((int)map.size() == cap) {
Node *lru = tail->prev;
remove(lru);
map.erase(lru->key); // erase before delete
delete lru;
}
Node *n = new Node(key, value);
map[key] = n;
insertFront(n);
}
};
package linkedlists
type lruNode struct {
key, value int
prev, next *lruNode
}
type LRUCache struct {
cap int
head, tail *lruNode // dummy nodes
nodes map[int]*lruNode
}
func Constructor(capacity int) LRUCache {
head, tail := &lruNode{}, &lruNode{}
head.next = tail
tail.prev = head
return LRUCache{cap: capacity, head: head, tail: tail, nodes: map[int]*lruNode{}}
}
func (c *LRUCache) remove(n *lruNode) {
n.prev.next = n.next
n.next.prev = n.prev
}
func (c *LRUCache) insertFront(n *lruNode) {
n.prev = c.head
n.next = c.head.next
c.head.next.prev = n
c.head.next = n
}
func (c *LRUCache) Get(key int) int {
n, ok := c.nodes[key]
if !ok {
return -1
}
c.remove(n)
c.insertFront(n)
return n.value
}
func (c *LRUCache) Put(key int, value int) {
if n, ok := c.nodes[key]; ok {
n.value = value
c.remove(n)
c.insertFront(n)
return
}
if len(c.nodes) == c.cap {
lru := c.tail.prev
c.remove(lru)
delete(c.nodes, lru.key)
}
n := &lruNode{key: key, value: value}
c.nodes[key] = n
c.insertFront(n)
}
import java.util.HashMap;
import java.util.Map;
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int cap;
private final Node head = new Node(0, 0), tail = new Node(0, 0); // dummy nodes
private final Map<Integer, Node> map = new HashMap<>();
public LRUCache(int capacity) {
cap = capacity;
head.next = tail;
tail.prev = head;
}
private void remove(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void insertFront(Node n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
}
public int get(int key) {
Node n = map.get(key);
if (n == null)
return -1;
remove(n);
insertFront(n);
return n.value;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) {
n.value = value;
remove(n);
insertFront(n);
return;
}
if (map.size() == cap) {
Node lru = tail.prev;
remove(lru);
map.remove(lru.key);
}
n = new Node(key, value);
map.put(key, n);
insertFront(n);
}
}
class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map();
this.head = new Node(); // dummy nodes
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
}
remove(n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
insertFront(n) {
n.prev = this.head;
n.next = this.head.next;
this.head.next.prev = n;
this.head.next = n;
}
get(key) {
const n = this.map.get(key);
if (!n) return -1;
this.remove(n);
this.insertFront(n);
return n.value;
}
put(key, value) {
let n = this.map.get(key);
if (n) {
n.value = value;
this.remove(n);
this.insertFront(n);
return;
}
if (this.map.size === this.cap) {
const lru = this.tail.prev;
this.remove(lru);
this.map.delete(lru.key);
}
n = new Node(key, value);
this.map.set(key, n);
this.insertFront(n);
}
}
module.exports = LRUCache;
class Node:
def __init__(self, key: int = 0, value: int = 0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head = Node() # dummy nodes
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, n: Node) -> None:
n.prev.next = n.next
n.next.prev = n.prev
def _insert_front(self, n: Node) -> None:
n.prev = self.head
n.next = self.head.next
self.head.next.prev = n
self.head.next = n
def get(self, key: int) -> int:
n = self.map.get(key)
if n is None:
return -1
self._remove(n)
self._insert_front(n)
return n.value
def put(self, key: int, value: int) -> None:
n = self.map.get(key)
if n is not None:
n.value = value
self._remove(n)
self._insert_front(n)
return
if len(self.map) == self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
n = Node(key, value)
self.map[key] = n
self._insert_front(n)
// A pointer-based doubly linked list fights Rust's ownership rules (every node
// has two owners), so the nodes live in a Vec and link to each other by index.
// Slots 0 and 1 are the dummy head and tail; an evicted node's slot is reused.
use std::collections::HashMap;
const HEAD: usize = 0;
const TAIL: usize = 1;
struct Node {
key: i32,
value: i32,
prev: usize,
next: usize,
}
struct LRUCache {
cap: usize,
nodes: Vec<Node>,
map: HashMap<i32, usize>,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
let nodes = vec![
Node { key: 0, value: 0, prev: HEAD, next: TAIL },
Node { key: 0, value: 0, prev: HEAD, next: TAIL },
];
LRUCache { cap: capacity as usize, nodes, map: HashMap::new() }
}
fn remove(&mut self, i: usize) {
let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
self.nodes[prev].next = next;
self.nodes[next].prev = prev;
}
fn insert_front(&mut self, i: usize) {
let first = self.nodes[HEAD].next;
self.nodes[i].prev = HEAD;
self.nodes[i].next = first;
self.nodes[first].prev = i;
self.nodes[HEAD].next = i;
}
fn get(&mut self, key: i32) -> i32 {
match self.map.get(&key) {
None => -1,
Some(&i) => {
self.remove(i);
self.insert_front(i);
self.nodes[i].value
}
}
}
fn put(&mut self, key: i32, value: i32) {
if let Some(&i) = self.map.get(&key) {
self.nodes[i].value = value;
self.remove(i);
self.insert_front(i);
return;
}
let i = if self.map.len() == self.cap {
let lru = self.nodes[TAIL].prev;
self.remove(lru);
self.map.remove(&self.nodes[lru].key);
self.nodes[lru].key = key;
self.nodes[lru].value = value;
lru // reuse the evicted slot
} else {
self.nodes.push(Node { key, value, prev: HEAD, next: TAIL });
self.nodes.len() - 1
};
self.map.insert(key, i);
self.insert_front(i);
}
}