lru-cache.go

// https://leetcode.com/problems/lru-cache

type LRUCache struct {
    cache map[int]*listNode
    head *listNode
    tail *listNode
    capacity int
}

type listNode struct {
    Next *listNode
    Prev *listNode
    Val int
    Key int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        cache: make(map[int]*listNode),
        head: nil,
        tail: nil,
        capacity: capacity,
    }
}


func (c *LRUCache) Get(key int) int {
    node := c.get(key)
    
    if node == nil {
        return -1
    }
    
    return node.Val
}


func (c *LRUCache) Put(key int, value int)  {
    // we get a node by the get function (we should mark it as the most recently used)
    if node := c.get(key); node != nil {
        node.Val = value
        return
    }

    node := &listNode{
        Next: nil,
        Prev: nil,
        Val: value,
        Key: key,
    }
    
    c.cache[key] = node
    
    // we have empty cache, initialize it
    if c.head == nil {
        c.head = node
        c.tail = node
        return
    }
    
    // delete head if we are out of the capacity
    if len(c.cache) > c.capacity {
        delete(c.cache, c.head.Key)
        c.head = c.head.Next
    }
    
    // mark the current node as a tail 
    if len(c.cache) > 1 {
        c.tail.Next = node
        node.Prev = c.tail
    }
    
    c.tail = node
}

func (c *LRUCache) get(key int) *listNode {
    node := c.cache[key]
    
    if node == nil {
        return node
    }
    
    if node.Next != nil {
        // if HEAD points at the current node, we should declare this node as HEAD
        if c.head == node {
            c.head = node.Next
        }
        
        // remove the current node from the list
        left, right := node, node.Next

        if left.Prev != nil {
            left.Prev.Next = right
        }

        right.Prev = left.Prev
        
        // add the current to the tail and mark it as a tail
        c.tail.Next = node
        node.Prev = c.tail
        node.Next = nil
        c.tail = node
    }
    
    return node
}