LRU构造的代码哪里有问题

Terence888

1. class ListNode:
   
2.     def __init__(self,key=None,value=None):
   
3.         self.key = key
   
4.         self.value = value
   
5.         self.next = None
   
6.         self.pre = None
   
7. class LRUCache:
   
8. #'''使用双向链表进行操作'''#
   
9.     def __init__(self, capacity: int):
   
10.         self.capacity = capacity #链表节点总数
    
11.         self.hashmap = {} #哈希表存储节点的key值，用于指示节点
    
12.         self.head = ListNode() #定义头结点和尾节点
    
13.         self.tail = ListNode()
    
14.         
    
15.         self.head.next = self.tail #初始化链表，头尾结点相接
    
16.         self.tail.pre = self.head
    
17.    
    
18.     def move_to_tail(self,key:int):
    
19.         node = self.hashmap[key]
    
20.         node.pre.next = node.next#将需要移动到尾部的结点从链表中拎出（相当于在原位置删除）
    
21.         node.next.pre = node.pre
    
22. 
    
23.         node.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
    
24.         node.next = self.tail
    
25.         self.tail.pre.next = node
    
26.         self.tail.pre = node
    
27. 
    
28. 
    
29. 
    
30.     def get(self, key: int) -> int:
    
31.         if key in self.hashmap:#defaultdict对于不存在的值返回空结点，dict对不存在的值会返回None
    
32.             self.move_to_tail(key) #把该被访问的结点移到链表尾部
    
33.             return self.hashmap[key].value
    
34.         else:
    
35.             return -1
    
36. 
    
37.     def put(self, key: int, value: int) -> None:
    
38.         if key in self.hashmap:#关键字key已存在于哈希表
    
39.             self.hashmap[key].value = value
    
40.             self.move_to_tail(key) #将更新后的key移动到链表尾部
    
41.         else:#哈希表不存在该关键字
    
42.             if len(self.hashmap) == self.capacity:#哈希表已达到最大容量
    
43.                 self.hashmap.pop(self.head.next.key)
    
44.                 self.head.next = self.head.next.next #头结点后删除该节点
    
45.                 self.head.next.pre = self.head
    
46. 
    
47.             #新结点添加在tail节点之前
    
48.             new = ListNode()
    
49.             self.hashmap[new.key] = new
    
50.             new.pre = self.tail.pre#将该节点插入到尾节点前面一个位置
    
51.             new.next = self.tail
    
52.             self.tail.pre.next = new
    
53.             self.tail.pre = new
    
54. 
    
55. # Your LRUCache object will be instantiated and called as such:
    
56. # obj = LRUCache(capacity)
    
57. # param_1 = obj.get(key)
    
58. # obj.put(key,value)

复制代码

上述代码哪里有错？半天没看出来