LRU 算法实现

题目要求

golang 实现lru算法，要求在 O(1) 时间内完成get和put请求

js
package main

import "fmt"

// 双向链表节点
type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

// LRU Cache
type LRUCache struct {
	capacity int
	size     int
	cache    map[int]*Node
	head     *Node // 哨兵头
	tail     *Node // 哨兵尾
}

// 初始化
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,
	}
}

// 获取
func (l *LRUCache) Get(key int) int {
	if node, ok := l.cache[key]; ok {
		l.moveToHead(node)
		return node.value
	}
	return -1
}

// 插入/更新
func (l *LRUCache) Put(key int, value int) {
	// 如果存在，更新并移动到头部
	if node, ok := l.cache[key]; ok {
		node.value = value
		l.moveToHead(node)
		return
	}

	// 新节点
	node := &Node{
		key:   key,
		value: value,
	}

	l.cache[key] = node
	l.addToHead(node)
	l.size++

	// 超过容量，删除尾部
	if l.size > l.capacity {
		removed := l.removeTail()
		delete(l.cache, removed.key)
		l.size--
	}
}

// 移动到头部
func (l *LRUCache) moveToHead(node *Node) {
	l.removeNode(node)
	l.addToHead(node)
}

// 添加到头部
func (l *LRUCache) addToHead(node *Node) {
	node.prev = l.head
	node.next = l.head.next

	l.head.next.prev = node
	l.head.next = node
}

// 删除节点
func (l *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

// 删除尾部（最久未使用）
func (l *LRUCache) removeTail() *Node {
	node := l.tail.prev
	l.removeNode(node)
	return node
}

// 测试
func main() {
	lru := Constructor(2)

	lru.Put(1, 1)
	lru.Put(2, 2)

	fmt.Println(lru.Get(1)) // 1

	lru.Put(3, 3)           // 淘汰 key=2

	fmt.Println(lru.Get(2)) // -1
	lru.Put(4, 4)           // 淘汰 key=1

	fmt.Println(lru.Get(1)) // -1
	fmt.Println(lru.Get(3)) // 3
	fmt.Println(lru.Get(4)) // 4
}