- 雙向鏈表定義: “雙向鏈表”相對于“單向鏈表”是一種更復(fù)雜的鏈表。原因在于恨憎， 雙向鏈表的每個節(jié)點有兩個鏈接地址:
- next:指向下一個節(jié)點，當(dāng)此節(jié)點為 節(jié)點時郊楣，指向空值;
- pre: 指向前一個節(jié)點憔恳，當(dāng)此節(jié)點為 節(jié)點時，指向空值
class LRUCache(object):
def __init__(self, capacity):
# cache 的最大記錄數(shù)
self.maxsize = capacity
# 用于真實的存儲數(shù)據(jù)
self.inner_dd = {}
# 鏈表-頭指針
self.head = None
# 鏈表-尾指針
self.tail = None
def put(self, key, value):
# 達到指定大小
if len(self.inner_dd) >= self.maxsize:
self.remove_head_node()
node = Node()
node.data = (key, value)
self.insert_to_tail(node)
self.inner_dd[key] = node
def insert_to_tail(self, node):
if self.tail is None:
self.tail = node
self.head = node
else:
self.tail.next = node
node.pre = self.tail
self.tail = node
def remove_head_node(self):
node = self.head
del self.inner_dd[node.data[0]]
node = None
self.head = self.head.next
self.head.pre = None
def get(self, key):
if key in self.inner_dd:
# 如果命中, 需要將對應(yīng)的節(jié)點移動到隊列的尾部
node = self.inner_dd.get(key)
self.move_to_tail(node)
return node.data[1]
return None
def move_to_tail(self, node):
# 只需處理在隊列頭部和中間的情況
if not (node == self.tail):
if node == self.head:
self.head = node.next
self.head.pre = None
self.tail.next = node
node.pre = self.tail
node.next = None
self.tail = node
else:
pre_node = node.pre
next_node = node.next
pre_node.next = next_node
next_node.pre = pre_node
self.tail.next = node
node.pre = self.tail
node.next = None
self.tail = node
class Node(object):
def __init__(self):
self.pre = None
self.next = None
# (key, value)
self.data = None
def __eq__(self, other):
if self.data[0] == other.data[0]:
return True
return False
def __str__(self):
return str(self.data)
if __name__ == '__main__':
obj = LRUCache(10)
param_1 = obj.get(key)
obj.put(key, value)
