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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| type LRUCache struct {
capacity int
size int
hashMap map[int]*DLinkNode
head, tail *DLinkNode
}
type DLinkNode struct {
key, value int
prev *DLinkNode
next *DLinkNode
}
func NewDLinkNode(key, value int) *DLinkNode {
return &DLinkNode{
key: key,
value: value,
}
}
func Constructor(capacity int) LRUCache {
head := NewDLinkNode(0, 0)
tail := NewDLinkNode(0, 0)
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
hashMap: make(map[int]*DLinkNode),
head: head,
tail: tail,
size: 0,
}
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.hashMap[key]; ok {
this.moveToHead(node)
return node.value
} else {
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
node, ok := this.hashMap[key]
if ok {
node.value = value
this.moveToHead(node)
} else {
node = NewDLinkNode(key, value)
this.addToHead(node)
this.size++
}
if this.size > this.capacity {
delete(this.hashMap, this.tail.prev.key)
this.removeFromTail()
this.size--
}
this.hashMap[key] = node
}
func (this *LRUCache) removeNode(node *DLinkNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) moveToHead(node *DLinkNode) {
this.removeNode(node)
this.addToHead(node)
}
func (this *LRUCache) addToHead(node *DLinkNode) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
func (this *LRUCache) removeFromTail() {
this.removeNode(this.tail.prev)
}
|