-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLRUCache.java
More file actions
130 lines (111 loc) · 2.84 KB
/
Copy pathLRUCache.java
File metadata and controls
130 lines (111 loc) · 2.84 KB
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package data_structure;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
static class Node {
int key;
int value;
Node next;
Node prev;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final Map<Integer, Node> nodeMap;
private final Node head;
private final Node tail;
private final int capacity;
public LRUCache(int capacity) {
this.nodeMap = new HashMap<>();
this.capacity = capacity;
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
/*
* insert
* */
public void add(int key, int value) {
if (nodeMap.containsKey(key)) {
Node node = nodeMap.get(key);
node.value = value;
moveToFront(node);
} else {
Node node = new Node(key, value);
insertToFront(node);
nodeMap.put(node.key, node);
if (capacity < nodeMap.size()) {
removeLRU();
}
}
}
private void moveToFront(Node node) {
cutChain(node);
insertToFront(node);
}
private void insertToFront(Node node) {
Node next = head.next;
next.prev = node;
head.next = node;
}
private void cutChain(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
private void removeLRU() {
Node last = tail.prev;
Node prev = last.prev;
prev.next = tail;
tail.prev = prev;
nodeMap.remove(last.key);
}
/*
* get
* */
public int get(int key) {
if (!nodeMap.containsKey(key)) {
return -1;
}
Node node = nodeMap.get(key);
moveToFront(node);
return node.value;
}
/*
* delete
* */
public void evict(int key) {
if (!nodeMap.containsKey(key)) {
return;
}
Node node = nodeMap.get(key);
cutChain(node);
nodeMap.remove(key);
}
/*
* for test
* */
public void print() {
System.out.println("size : " + nodeMap.size());
for (Map.Entry<Integer, Node> node : nodeMap.entrySet()) {
System.out.println("key : %s, value : %s".formatted(node.getKey(), node.getValue().value));
}
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);
lruCache.add(1, 10);
lruCache.add(2, 11);
lruCache.add(3, 8);
lruCache.print();
lruCache.add(5, 11);
lruCache.print();
lruCache.add(2, 14);
lruCache.print();
lruCache.get(3);
lruCache.add(7, 99);
lruCache.print();
}
}