LRU Cache Implementation

Abhinay Gupta
1 min readJul 14, 2021

--

class LRUCache {

private Map<Integer, Node> map;
final Node head = new Node();
final Node tail = new Node();
private int capacity;
public LRUCache(int capacity) {
this.map = new HashMap<>(capacity);
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}

public int get(int key) {
int result = -1;
Node node = map.get(key);
if(node != null) {
result=node.value;
remove(node);
add(node);
}

return result;
}

public void put(int key, int value) {
Node node = map.get(key);
if(node != null) {
remove(node);
node.value = value;
add(node);
}
else
{
if(map.size() == capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
node = new Node();
node.key = key;
node.value = value;
map.put(key, node);
add(node);
}
}

//add the first node to Doubly Linked List
public void add(Node node){
Node head_next = head.next;
head.next = node;
node.next = head_next;
node.prev = head;
head_next.prev = node;

}

//remove the node of Doubly LinkedList
public void remove(Node node){
Node next_node = node.next;
Node prev_node = node.prev;

next_node.prev = prev_node;
prev_node.next = next_node;
}

class Node {
int key;
int value;
Node next;
Node prev;

}
}

--

--

Abhinay Gupta

Exploring personal growth, tech, and culture through engaging storytelling | Inspiring and connecting with readers worldwide.