Last active
June 7, 2024 00:15
-
-
Save leonardonicola/f18a9fbc810f35a4e4130c01295eb931 to your computer and use it in GitHub Desktop.
LRU Cache with Map and Linked List
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
class ListNode<T> { | |
next: ListNode<T> | null = null; | |
constructor(readonly data: T) {} | |
} | |
class LinkedList { | |
private size: number = 0; | |
private head: ListNode<string> | null = null; | |
get(data: string): null | unknown { | |
if (!this.head) { | |
return null; | |
} | |
let current: ListNode<string> | null = this.head; | |
while (current) { | |
if (current.data === data) { | |
return data; | |
} | |
current = current.next; | |
} | |
return null; | |
} | |
unshift(data: string) { | |
const node = new ListNode(data); | |
this.size++; | |
if (!this.head) { | |
this.head = node; | |
return; | |
} | |
node.next = this.head; | |
this.head = node; | |
} | |
remove(data: string): boolean { | |
if (!this.head) { | |
return false; | |
} | |
if (this.head.data === data) { | |
this.head = this.head.next; | |
this.size--; | |
return true; | |
} | |
let current = this.head.next; | |
let previous = this.head; | |
while (current) { | |
if (current.data === data) { | |
previous.next = current.next; | |
this.size--; | |
return true; | |
} | |
previous = current; | |
current = current.next; | |
} | |
return false; | |
} | |
pop(): string | null { | |
if (!this.head) { | |
return null; | |
} | |
if (!this.head.next) { | |
// If only one node in the list | |
let temp = this.head.data; | |
this.head = null; | |
this.size--; | |
return temp; | |
} | |
let current = this.head; | |
while (current.next && current.next.next) { | |
current = current.next; | |
} | |
// Current is now the penultimate | |
let temp = current.next!.data; | |
current.next = null; | |
this.size--; | |
return temp; | |
} | |
} | |
// LRU Cache | |
class LRUCache { | |
private cache: Map<string, unknown>; | |
lru: LinkedList; | |
constructor(readonly capacity: number) { | |
this.cache = new Map<string, unknown>(); | |
this.lru = new LinkedList(); | |
} | |
get(key: string): any { | |
const value = this.cache.get(key); | |
if (!value) return null; | |
// Add to the top of the Set | |
this.lru.remove(key); | |
this.lru.unshift(key); | |
return value; | |
} | |
set(key: string, val: unknown) { | |
// If full capacity, removed the Least Recently Used | |
if (this.cache.size === this.capacity) { | |
const removed = this.lru.pop(); | |
if (removed) { | |
this.cache.delete(removed); | |
} | |
} | |
this.lru.unshift(key); | |
this.cache.set(key, val); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment