1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| package main
type DLinkNode struct {
key, val int
pre, next *DLinkNode
}
type LRUCache struct {
size, capacity int
cache map[int]*DLinkNode
head, tail *DLinkNode
}
func initDLinkNode(key, val int) *DLinkNode {
return &DLinkNode{
key: key,
val: val,
}
}
func Constructor(capacity int) LRUCache {
l := LRUCache{
size: 0,
capacity: capacity,
cache: map[int]*DLinkNode{},
head: initDLinkNode(0, 0),
tail: initDLinkNode(0, 0),
}
l.head.next = l.tail
l.tail.pre = l.head
return l
}
func removeNode(node *DLinkNode) {
node.next.pre = node.pre
node.pre.next = node.next
}
func (l *LRUCache) removeTail() {
node := l.tail.pre
removeNode(node)
delete(l.cache,node.key)
}
func (l *LRUCache) addHead(node *DLinkNode) {
node.next = l.head.next
node.pre = l.head
l.head.next.pre = node
l.head.next = node
}
func (l *LRUCache) moveToHead(node *DLinkNode) {
removeNode(node)
l.addHead(node)
}
func (l *LRUCache) Get(key int) int {
if node, ok := l.cache[key]; ok {
l.moveToHead(node)
return node.val
}
return -1
}
func (l *LRUCache) Put(key int, value int) {
if node, ok := l.cache[key]; ok {
node.val = value
l.moveToHead(node)
} else {
node := initDLinkNode(key, value)
l.cache[key] = node
l.size++
l.addHead(node)
if l.size > l.capacity {
l.removeTail()
l.size--
}
}
}
|
