LRU Cache

package main

import "fmt"

// Node represents a doubly linked list node
type Node struct {
	key, value int
	prev, next *Node
}

// LRUCache represents the LRU Cache
type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

// Constructor initializes the LRUCache with a given capacity
func Constructor(capacity int) *LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

// Get retrieves the value of the key if it exists in the cache
func (lru *LRUCache) Get(key int) int {
	if node, exists := lru.cache[key]; exists {
		lru.moveToHead(node)
		return node.value
	}
	return -1
}

// Put inserts a key-value pair into the cache
func (lru *LRUCache) Put(key int, value int) {
	if node, exists := lru.cache[key]; exists {
		node.value = value
		lru.moveToHead(node)
	} else {
		newNode := &Node{key: key, value: value}
		lru.cache[key] = newNode
		lru.addToHead(newNode)

		if len(lru.cache) > lru.capacity {
			tail := lru.removeTail()
			delete(lru.cache, tail.key)
		}
	}
}

// moveToHead moves a node to the head of the list (most recently used)
func (lru *LRUCache) moveToHead(node *Node) {
	lru.removeNode(node)
	lru.addToHead(node)
}

// addToHead adds a node to the head of the doubly linked list
func (lru *LRUCache) addToHead(node *Node) {
	node.prev = lru.head
	node.next = lru.head.next
	lru.head.next.prev = node
	lru.head.next = node
}

// removeNode removes a node from the doubly linked list
func (lru *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

// removeTail removes the least recently used node (from the tail)
func (lru *LRUCache) removeTail() *Node {
	tail := lru.tail.prev
	lru.removeNode(tail)
	return tail
}

func main() {
	lru := Constructor(2)

	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1)) // Returns 1

	lru.Put(3, 3)           // Evicts key 2
	fmt.Println(lru.Get(2)) // Returns -1 (not found)

	lru.Put(4, 4)           // Evicts key 1
	fmt.Println(lru.Get(1)) // Returns -1 (not found)
	fmt.Println(lru.Get(3)) // Returns 3
	fmt.Println(lru.Get(4)) // Returns 4
}