Explain the principle of LRU cache and in what situations it is used.

LRU (Least Recently Used) cache is a data structure that stores a limited number of elements and removes the least recently used element when full.

Working principle:

• When an element is accessed, it becomes the "most recent".
• If the cache is full and a new element needs to be added, the element that has not been accessed for the longest time is removed.

This allows efficient memory usage by keeping the most relevant data.

Applications:

• Caching database query results.
• Caching images or files in memory.
• In resource-constrained systems for data access optimization.

Example in Go (simplified):

// Using container/list to store usage order
import (
    "container/list"
)

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

type entry struct {
    key   int
    value int
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) (int, bool) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return 0, false
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }
    if c.list.Len() == c.capacity {
        back := c.list.Back()
        if back != nil {
            c.list.Remove(back)
            delete(c.cache, back.Value.(*entry).key)
        }
    }
    elem := c.list.PushFront(&entry{key, value})
    c.cache[key] = elem
}