LRU全称Least Recently Used,最近最久未使用算法，是一种OPT的一种近似替代，可以采用两种方式实现，即链表和有序哈希表。
这里先使用链表来实现。
具体思路如下:定义页面容量，即链表最大长度，每当有页面中断产生时，先判断当前链表的长度，如果小于最大长度，则遍历链表，如果发现该元素，则头插，如果没有，则构造新节点，且链表长度+1,；当链表长度已经等于最大长度了，则执行与上面相同的操作，不同的是，链表长度不再变化。
class LinkListNode():
def __init__(self,x):
self.val = x
self.next = None
class LRU():
#初始化函数
def __init__(self,length):
#记录链表长度
self.length = 0
#链表最大长度
self.max_length = length
#构造哑结点，方便头插操作
self.dump = LinkListNode(None)
#页面置换函数
def Lru(self,node):
#如果当前链表长度小于链表最大长度
if self.length < self.max_length:
#检查原链表中是否包含待插入的结点
pre = self.dump
cur = self.dump.next
while cur:
if cur.val != node:
cur = cur.next
pre = pre.next
#如果存在则将该节点头插
else:
pre.next = cur.next
cur.next = self.dump.next
self.dump = cur
return self.dump.next
#如果遍历完整个链表都不存在，则构造新节点头插，且链表长度+1
New_node = LinkListNode(node)
New_node.next = self.dump.next
self.dump.next = New_node
self.length += 1
return self.dump.next
#如果当前链表长度等于链表最大长度
else:
#检查原链表中是否包含待插入的结点
pre = self.dump
cur = self.dump.next
while cur.next:
if cur.val != node:
cur = cur.next
pre = pre.next
else:
pre.next = cur.next
cur.next = self.dump.next
self.dump.next = cur
return self.dump.next
if cur.val == node:
cur.next = self.dump.next
self.dump.next = cur
pre.next = None
return self.dump.next
else:
New_node = LinkListNode(node)
pre.next = None
New_node.next = self.dump.next
self.dump.next = New_node
return self.dump.next
#打印链表函数
def PrintLinkList(head):
cur = head
List = []
while cur:
List.append(cur.val)
cur = cur.next
print(List)
if __name__ == '__main__':
'''
1 1
2 1 2
3 2 1 3
1 3 2 1
4 1 3 4
'''
res = LRU(3)
PrintLinkList(res.Lru(1))
PrintLinkList(res.Lru(2))
PrintLinkList(res.Lru(3))
PrintLinkList(res.Lru(1))
PrintLinkList(res.Lru(4))
'''
[1]
[2, 1]
[3, 2, 1]
[1, 3, 2]
[4, 1, 3]
'''
