146.M LRU 缓存

Problem: 146. LRU 缓存

思路

通过map和双向链表实现。

• map保存键值对，value为双向链表的节点。

• 双向链表节点按被访问时间排序，越往前的表示访问时间越近。

• 为了方便处理节点的插入、移除等，让双向链表的head和tail分别作为伪节点存在。

Code

type LRUCache struct {
	m        map[int]*DLinkedNode
	head     *DLinkedNode
	tail     *DLinkedNode
	capacity int
}

type DLinkedNode struct {
	Key  int
	Val  int
	Pre  *DLinkedNode
	Next *DLinkedNode
}

func Constructor(capacity int) LRUCache {
	head := &DLinkedNode{Val: -1}
	tail := &DLinkedNode{Val: -1, Pre: head}
	head.Next = tail
	return LRUCache{
		m:        make(map[int]*DLinkedNode),
		head:     head,
		tail:     tail,
		capacity: capacity,
	}
}

func (l *LRUCache) Get(key int) int {
	if node, ok := l.m[key]; ok {
		l.MoveToHead(node)
		return node.Val
	}

	return -1
}

func (l *LRUCache) Put(key int, value int) {
	if node, ok := l.m[key]; ok {
		l.MoveToHead(node)
		node.Val = value
		return
	}

	if len(l.m) >= l.capacity {
		node := l.RemoveTail()
		delete(l.m, node.Key)
	}

	node := &DLinkedNode{Key: key, Val: value}
	l.AddToHead(node)
	l.m[key] = node
}

func (l *LRUCache) MoveToHead(node *DLinkedNode) {
	// 从现有位置移除
	node.Pre.Next = node.Next
	node.Next.Pre = node.Pre

	// 把节点插入到l.head之后
	l.AddToHead(node)
}

func (l *LRUCache) AddToHead(node *DLinkedNode) {
	node.Next = l.head.Next
	l.head.Next.Pre = node
	node.Pre = l.head
	l.head.Next = node
}

func (l *LRUCache) RemoveTail() *DLinkedNode {
	target := l.tail.Pre
	target.Pre.Next = target.Next
	target.Next.Pre = target.Pre
	return target
}