Created
November 2, 2021 12:41
-
-
Save ali-alaei/8dfabedfa6a621c16f765902b5bef0ff to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class LRUCache { | |
//double linked list class | |
class DLinkedNode { | |
int key; | |
int value; | |
DLinkedNode prev; | |
DLinkedNode next; | |
} | |
//Adding a new node to the DLL | |
private void addNode(DLinkedNode node) { | |
//Since the new node is the most recently used node, | |
//we add it after the pseudo head. | |
//Pseudo Head and Tail of the DLL will remain the same. | |
node.prev = head; | |
node.next = head.next; | |
//The former node after the pseudo head, now points to | |
//the new node as its previous node. | |
head.next.prev = node; | |
//The next node after the pseudo head is the added node. | |
head.next = node; | |
} | |
//Removing a node from the DLL | |
private void removeNode(DLinkedNode node){ | |
//The node before and after the deleted node | |
DLinkedNode prev = node.prev; | |
DLinkedNode next = node.next; | |
//The previous node points to the node after | |
//the removed node. | |
prev.next = next; | |
//The next node points to the node before | |
//the removed node. | |
next.prev = prev; | |
} | |
//Moving a node to the head of the DLL | |
//Used to update the MRU and LRU nodes | |
private void moveToHead(DLinkedNode node){ | |
//First removes the node, then adds it | |
//to the DLL again. | |
removeNode(node); | |
addNode(node); | |
} | |
//Pops out the node before the pseudo tail | |
//and returns the removed node. | |
private DLinkedNode popTail() { | |
DLinkedNode res = tail.prev; | |
removeNode(res); | |
return res; | |
} | |
//The map of integers to the DLL (Cache) | |
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, | |
DLinkedNode>(); | |
private int size; | |
private int capacity; | |
private DLinkedNode head, tail; | |
//Initializing the cache | |
public LRUCache(int capacity) { | |
//current size of the link list | |
this.size = 0; | |
this.capacity = capacity; | |
head = new DLinkedNode(); | |
tail = new DLinkedNode(); | |
head.next = tail; | |
tail.prev = head; | |
} | |
//Get method | |
public int get(int key) { | |
DLinkedNode node = cache.get(key); | |
if (node == null) return -1; | |
//Moves the node to the start of the DLL as MRU | |
moveToHead(node); | |
return node.value; | |
} | |
//Put method | |
public void put(int key, int value) { | |
//Checks if the given node already exists | |
DLinkedNode node = cache.get(key); | |
//Adding a new node to the cache | |
if(node == null) { | |
DLinkedNode newNode = new DLinkedNode(); | |
newNode.key = key; | |
newNode.value = value; | |
cache.put(key, newNode); | |
addNode(newNode); | |
++size; | |
//If the cache capacity is full, pop the tail (LRU) | |
if(size > capacity) { | |
DLinkedNode tail = popTail(); | |
cache.remove(tail.key); | |
--size; | |
} | |
} | |
//Else, Updates the value and the position | |
//of the previously existing node | |
else { | |
node.value = value; | |
moveToHead(node); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment