Implement LRU Cache

  • LRU Cache (Least Recently Used)
  • LFU (Least Frequently Used)
  • FIFO (First IN First Out)
  • And many more…
package mainimport (
"fmt"
)
type Node struct {
Key int
Value int
Prev *Node
Next *Node
}
type LRUCache struct {
Capacity int
Count int
HashMap map[int]*Node
Head *Node
Tail *Node
}
func CreateLRUcache(cap int) *LRUCache {
cache := new(LRUCache)
cache.HashMap = make(map[int]*Node)
cache.Head = new(Node)
cache.Tail = new(Node)
cache.Head.Next = cache.Tail
cache.Tail.Prev = cache.Head
cache.Capacity = cap
return cache
}
func (cache *LRUCache) delNodeFromList(key int) {
node := cache.Head
// Iterating to reach the required node
for node.Next.Key != key && node != cache.Tail {
node = node.Next
}
if node == cache.Tail {
return
}
// resetting pointers to eliminate node
prevNode := node.Next.Next
node.Next = node.Next.Next
prevNode.Prev = node
cache.Count--
}
func (cache *LRUCache) pushNodeToFrontOfList(node *Node) {
if cache.Head.Next == cache.Tail {
// Head is pointing to tail
node.Next = cache.Tail
node.Prev = cache.Head
cache.Head.Next = node
cache.Tail.Prev = node
} else {
node.Next = cache.Head.Next
node.Prev = cache.Head
cache.Head.Next = node
node.Next.Prev = node
}
cache.Count++
}
func (cache *LRUCache) delLastNode() {
if cache.Tail.Prev == cache.Head {
// List is empty
return
}
lastNode := cache.Tail.Prev
secLastnode := lastNode.Prev
secLastnode.Next = cache.Tail
cache.Tail.Prev = secLastnode
// Decrementing the counter on deleting last node
cache.Count--
}
func (cache *LRUCache) isCacheFull() bool {
if cache.Capacity == cache.Count {
return true
}
return false
}
func (cache *LRUCache) Get(key int) int {
ok := false
var val *Node
if val, ok = cache.HashMap[key]; !ok {
return -1
}
// here we have the val
cache.delNodeFromList(key) // Deleting from doubly ll
cache.pushNodeToFrontOfList(val)
return val.Value
}
func (cache *LRUCache) Put(key, val int) {
fmt.Println("Pushing key : ", key, " Val : ", val)
ok := false
var valNode *Node
if valNode, ok = cache.HashMap[key]; ok {
delete(cache.HashMap, key) // Deleting from hashmap
cache.delNodeFromList(key) // Deleting from doubly ll
cache.pushNodeToFrontOfList(valNode)
return
}
if cache.isCacheFull() {
fmt.Println("Cache full ")
delete(cache.HashMap, cache.Tail.Prev.Key)
cache.delLastNode()
}
node := new(Node)
node.Key = key
node.Value = val
cache.HashMap[key] = node
cache.pushNodeToFrontOfList(node)
}
func (cache *LRUCache) Iter() {
fmt.Println("\nPrinting map : ", cache.HashMap)
fmt.Print("Printing Double Linked List : ")
node := cache.Head.Next
for node != cache.Tail {
fmt.Print(node.Key, ":", node.Value, " ")
node = node.Next
}
fmt.Println()
}
func main() {
cache := CreateLRUcache(3)
fmt.Println("Get 1 : ", cache.Get(1))
cache.Iter()
cache.Put(2, 2)
cache.Iter()
cache.Put(3, 3)
cache.Iter()
cache.Put(4, 4)
cache.Iter()
fmt.Println("Get 2 : ", cache.Get(2))
cache.Put(5, 5)
cache.Iter()
fmt.Println("Get 2 : ", cache.Get(2))
}
Get 1 :  -1

Printing map : map[]
Printing Double Linked List :
Pushing key : 2 Val : 2

Printing map : map[2:0xc0000b8060]
Printing Double Linked List : 2:2
Pushing key : 3 Val : 3

Printing map : map[2:0xc0000b8060 3:0xc0000b80a0]
Printing Double Linked List : 3:3 2:2
Pushing key : 4 Val : 4

Printing map : map[2:0xc0000b8060 3:0xc0000b80a0 4:0xc0000b80e0]
Printing Double Linked List : 4:4 3:3 2:2
Get 2 : 2
Pushing key : 5 Val : 5
Cache full

Printing map : map[2:0xc0000b8060 4:0xc0000b80e0 5:0xc0000b8120]
Printing Double Linked List : 5:5 2:2 4:4
Get 2 : 2

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Prince Pereira

Prince Pereira

31 Followers

Software Engineer II - Microsoft | SDN | Java | Golang | DS & Algo | Microservices | Kubernetes | Docker | gRPC & Protocol Buffer