• 雙向鏈表定義: “雙向鏈表”相對(duì)于“單向鏈表”是一種更復(fù)雜的鏈表。原因在于， 雙向鏈表的每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接地址:
  • next:指向下一個(gè)節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)為 節(jié)點(diǎn)時(shí)，指向空值;
  • pre: 指向前一個(gè)節(jié)點(diǎn)，當(dāng)此節(jié)點(diǎn)為 節(jié)點(diǎn)時(shí)，指向空值

class LRUCache(object):
    def __init__(self, capacity):
        # cache 的最大記錄數(shù)
        self.maxsize = capacity
        # 用于真實(shí)的存儲(chǔ)數(shù)據(jù)
        self.inner_dd = {}
        # 鏈表-頭指針
        self.head = None
        # 鏈表-尾指針
        self.tail = None

    def put(self, key, value):
        # 達(dá)到指定大小
        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:
            # 如果命中, 需要將對(duì)應(yīng)的節(jié)點(diǎn)移動(dòng)到隊(duì)列的尾部
            node = self.inner_dd.get(key)
            self.move_to_tail(node)
            return node.data[1]
        return None

    def move_to_tail(self, node):
        # 只需處理在隊(duì)列頭部和中間的情況
        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)