-
Notifications
You must be signed in to change notification settings - Fork 2
/
LRUCache.py
165 lines (141 loc) · 4.13 KB
/
LRUCache.py
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# Used array to maintain the keys. O(n)
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cacheData = {}
self.cacheKey = []
def get(self, key: int) -> int:
if key in self.cacheData.keys():
if key in self.cacheKey:
self.cacheKey.remove(key)
self.cacheKey = [key] + self.cacheKey
return self.cacheData[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.cacheData.keys():
self.cacheData[key] = value
if key in self.cacheKey:
self.cacheKey.remove(key)
self.cacheKey = [key] + self.cacheKey
else:
if len(self.cacheData) < self.capacity:
self.cacheData[key] = value
self.cacheKey = [key] + self.cacheKey
else:
lastDataKey = self.cacheKey.pop()
del self.cacheData[lastDataKey]
self.cacheData[key] = value
self.cacheKey = [key] + self.cacheKey
# define the double linked-list node
class ListNode:
def __init__(self, key = None, value = None):
self.key = key
self.value = value
self.next = None
self.prev = None
# Used double linked-list to maintain the node. O(1)
class LRUCache_linkedList:
def __init__(self, capacity: int):
self.capacity = capacity
self.cacheData = {}
self.head: ListNode = None
self.tail: ListNode = None
def get(self, key: int) -> int:
node = self.cacheData.get(key)
if node:
# move the current node to the front of the linked list
self.__moveNodeToFront(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
node = self.cacheData.get(key)
if node:
# key already exsit in cache, update the value
node.value = value
# move the node to front since it has been updated
self.__moveNodeToFront(node)
else:
newNode = ListNode(key, value)
self.cacheData[key] = newNode
self.__addNodeAtFront(newNode)
if len(self.cacheData) > self.capacity:
del self.cacheData[self.tail.key]
self.__removeNode(self.tail)
def __moveNodeToFront(self, node: ListNode):
self.__removeNode(node)
self.__addNodeAtFront(node)
def __removeNode(self, node: ListNode):
# This method needs to consider if the node you want to remove is the head or the tail.
n = node.next # if node is tail, then n will be None
p = node.prev # if node is head, then p will be None
if not p:
self.head = n
node.next = None
if n:
n.prev = None
else:
p.next = n
if n:
n.prev = node.prev
else:
self.tail = node.prev
node.prev = None
def __addNodeAtFront(self, node: ListNode):
if not self.head:
# if the linked list does not exist yet
self.head = node
self.tail = node
return
node.next = self.head
self.head.prev = node
node.prev = None
self.head = node
########
# Test #
########
def printList(l: LRUCache_linkedList):
c = l.head
while c:
print(c.value, end = "-")
c = c.next
print("None")
l = LRUCache_linkedList(2)
l.put(1,1)
l.put(2,2)
printList(l)
# expected: 2 - 1
print("----")
print(l.get(1))
print("----")
printList(l)
# expected: 1 - 2
l.put(3,3)
printList(l)
# expected: 3 - 1
print("----")
print(l.get(2))
# expected: -1
print("----")
l.put(4,4)
printList(l)
# expected: 4 - 3
print("----")
print(l.get(1))
# expected: -1
print("----")
print("----")
print(l.get(3))
# expected: 3
print("----")
printList(l)
# expected: 3 - 4
print("----")
print(l.get(4))
# expected: 4
print("----")
printList(l)
# expected: 4 - 3