Python 实现LRU结构，用得最少的最先被踢出去，时间复杂度O(1)，内部使用双端队列

LRU.py

# coding:utf-8
class Node:
    def __init__(self, prev=None, nex=None, val=None):
        self.prev = prev
        self.next = nex
        self.val = val


class DoubleLinkList:
    def __init__(self):
        self.head = Node()
        self.head.next = self.head
        self.head.prev = self.head
        self.head.val = 0
        self.len = 0

    def __len__(self):
        return self.len

    def __str__(self):
        l = []
        count = 0
        p = self.head.next
        while count < len(self):
            l.append(str(p.val))
            p = p.next
            count += 1
        return "->".join(l)

    def add_at_head(self, val):
        # 将指定值放入链表
        node = Node(self.head, self.head.next, val)
        node.next.prev = node
        node.prev.next = node
        self.len += 1

    def add_at_tail(self, val):
        node = Node(self.head.prev, self.head, val)
        node.prev.next = node
        node.next.prev = node
        self.len += 1

    def add_at_index(self, index, val):
        """
        index从0开始，插入到index位置元素前面
        :param index:
        :param val:
        :return:
        """
        if index < 0 or index > self.len:
            raise IndexError('index错误')
        elif index == self.len:
            self.add_at_tail(val)
        elif index == 0:
            self.add_at_head(val)
        else:
            p = self.__get_index(index)
            node = Node(p.prev, p, val)
            node.prev.next = node
            node.next.prev = node
            self.len += 1

    def del_at_head(self):
        """
        删除链表头
        :return:
        """
        if self.len == 0:
            raise IndexError('链表为空')
        old_head = self.head
        self.head = self.head.next
        self.head.prev = old_head.prev
        self.head.prev.next = self.head
        del old_head
        self.len -= 1

    def del_at_tail(self):
        # 删除链表尾部
        if self.len == 0:
            raise IndexError('链表为空')
        old_tail = self.head.prev
        self.head.prev = old_tail.prev
        old_tail.prev.next = self.head
        del old_tail
        self.len -= 1

    def del_at_index(self, index):
        # 删除指定index元素
        if index < 0 or index >= self.len:
            raise IndexError('index超出链表范围')
        elif index == 0:
            self.del_at_head()
        elif index == self.len-1:
            self.del_at_tail()
        else:
            p = self.__get_index(index)
            p.next.prev = p.prev
            p.prev.next = p.next
            del p
        self.len -= 1

    def __get_index(self, index):
        # 内部方法，用来遍历到指定index
        count = 0
        p = self.head.next
        while count < index:
            p = p.next
            count += 1
        return p

    def get_at_index(self, index):
        # 得到指定index的内容
        if index < 0 or index >= self.len:
            raise IndexError('index超出链表范围')
        elif index == 0:
            return self.get_at_head()
        elif index == self.len-1:
            return self.get_at_tail()
        else:
            p = self.__get_index(index)
            return p

    def get_at_head(self):
        # 获得头部元素的值
        if self.len <= 0:
            raise IndexError('链表为空')
        return self.head.next

    def get_at_tail(self):
        # 获得尾部元素的值
        if self.len <= 0:
            raise IndexError('链表为空')
        return self.head.prev

    def del_by_node(self, node):
        """
        删除指定链表中node节点
        :param node:
        :return:
        """
        node.next.prev = node.prev
        node.prev.next = node.next
        del node
        self.len -= 1

    def add_by_node(self, node, val):
        """
        在当前node之前添加一个新的, node相当于迭代器
        :param val:
        :param node:
        :return:
        """
        n = Node(node.prev, node, val)
        n.prev.next = n
        n.next.prev = n
        self.len += 1
        return n

    def add_after_node(self, node, val):
        """
        在当前node之后添加一个新的, node相当于迭代器
        :param val:
        :param node:
        :return:
        """
        n = Node(node, node.next, val)
        n.prev.next = n
        n.next.prev = n
        self.len += 1
        return n


class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.key2index = {}
        self.key2value = {}
        self.key_list = DoubleLinkList()
        self.length = capacity
        self.size = 0

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.key2value:
            return -1
        value = self.key2value[key]
        node = self.key2index[key]
        self.key_list.del_by_node(node)  # 删除原来的节点
        node = self.key_list.add_after_node(self.key_list.head, key)
        self.key2index[key] = node
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.key2index:
            self.key2value[key] = value
            node = self.key2index[key]
            self.key_list.del_by_node(node)

            node = self.key_list.add_after_node(self.key_list.head, key)
            self.key2index[key] = node

        else:                               # key不在链表中
            if self.size < self.length:
                if self.size == 0:  # 链表为空
                    self.key_list.add_at_head(key)
                    self.key2index[key] = self.key_list.head.next
                    self.key2value[key] = value

                else:
                    node = self.key_list.add_after_node(self.key_list.head, key)  # 插入到头结点后
                    self.key2index[key] = node
                    self.key2value[key] = value
                self.size += 1

            elif self.size == self.length:
                delete_node = self.key_list.get_at_tail()    # 删除最后那个元素
                delete_key = delete_node.val
                self.key_list.del_at_tail()
                self.key2value.pop(delete_key)
                self.key2index.pop(delete_key)

                node = self.key_list.add_after_node(self.key_list.head, key)    # 添加到前面
                self.key2value[key] = value
                self.key2index[key] = node