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]
'''