Python实现双向链表 | 利用双向链表模拟FIFO缓存置换算法

🐡 双向链表和FIFO

• 双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 —— 摘自维基
• 双向链表就是将内存中的各个节点通过指针的方式链接起来的数据结构。
• FIFO：即先进先出，这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。它基于双向链表实现，即最先添加的节点最先弹出。

🗽 代码：双向链表

# coding=utf-8
class Node:  # 链表由节点组成，双向链表的节点包含上节点的地址和下节点的地址，还有它自身的key和value
    def __init__(self, key, value):  # 可以理解为：key表示内存地址，value表示数据
        self.next = None
        self.prev = None
        self.key = key
        self.value = value

    def __str__(self):
        val = '({} : {})'.format(self.key, self.value)
        return val

    def __repr__(self):
        val = '({} : {})'.format(self.key, self.value)
        return val


class DoubleLinkedList:
    def __init__(self, capacity=0xffff):
        self.size = 0  # 链表中已有的节点个数
        self.capacity = capacity  # 链表的最多可容纳的节点个数
        self.head = None  # 头指针
        self.tail = None  # 尾指针

    def __add_head(self, node):
        """向头部添加节点"""
        if not self.head:  # 如果链表头部为空，即链表没有节点
            self.head = self.tail = node
            self.head.next = None
            self.head.prev = None
        else:  # 如果链表头部不为空，即链表有节点
            self.head.prev = node
            node.next = self.head
            self.head = node
            self.head.prev = None
        self.size += 1
        return node

    def __add_tail(self, node):
        """向尾部添加节点"""
        if not self.tail:  # 同上，尾部节点为空说明链表无节点
            self.tail = self.head = node
            self.tail.next = None
            self.tail.prev = None
        else:  # 若链表有节点
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
            self.tail.next = None
        self.size += 1
        return node

    def __del_tail(self):
        if not self.tail:  # 先判断一下删除的必要性
            return
        else:
            tail_node = self.tail  # 保存删除的节点，方法结束后要返回它
            if self.tail.prev:
                self.tail.prev.next = None
                self.tail = self.tail.prev
            else:
                self.tail = self.head = None
        self.size -= 1
        return tail_node

    def __del_head(self):
        if not self.head:
            return
        else:
            node = self.head
            if self.head.next:
                self.head.next.prev = None
                self.head = self.head.next
            else:
                self.head = self.tail = None
        self.size -= 1
        return node

    def __remove(self, node):
        """删除任意节点（删除参数提供的node节点对象）"""
        if not node:  # 若node为空，默认删除尾节点，于是调用__del_tail()方法
            return self.__del_tail()
        else:  # 若node不为空
            if node == self.tail:
                self.__del_tail()
            elif node == self.head:
                self.__del_head()
            else:
                node.prev.next = node.next
                node.next.prev = node.prev
                self.size -= 1
        return node

    # 以下是封装API的方法
    def pop(self):
        """从头部弹出"""
        return self.__del_head()

    def append(self, node):
        """向尾部添加"""
        return self.__add_tail(node)

    def append_front(self, node):
        """向头部添加"""
        return self.__add_head(node)

    def remove(self, node=None):
        """删除指定的节点，若没指定则删除尾部节点"""
        return self.__remove(node)

    def print(self):
        """用来检测的打印函数"""
        p = self.head
        line = ''
        while p:
            line += '%s' % p
            p = p.next
            if p:
                line += '->'
        print(line)


if __name__ == '__main__':
    l = DoubleLinkedList(10)
    nodes = []
    for i in range(10):
        nodes.append(Node(i, i ** 2))

    l.append(nodes[1])
    l.print()
    l.append(nodes[2])
    l.print()
    l.append_front(nodes[3])
    l.print()
    l.pop()
    l.print()
    l.remove(nodes[1])
    l.print()

🏀 代码：FIFO算法

from DoubleLinkedList import DoubleLinkedList, Node


class FIFOCache:
    """使用FIFO算法的缓存，基于双向链表"""
    def __init__(self, capacity):  # 属性: 容量、大小、链表和map字典（相当于hashmap）
        self.capacity = capacity
        self.size = 0
        self.list = DoubleLinkedList(self.capacity)
        self.map = {}  # 每次添加（调用put方法），就存储节点的key和节点的映射关系，用于查询和获取节点

    def put(self, key, value):
        """添加节点到缓存，若节点已存在便修改"""
        if self.capacity == 0:  # 容量为0说明不能添加
            return
        if key in self.map:  # 如果链表中已有相同的key存在，只需修改key对应的节点：获取，再把它从链表取出，修改后在添加到链表末尾
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append(node)
        else:  # 如果没有，则要添加
            if self.capacity == self.size:  # 若缓存已满
                node = self.list.pop()  # 链表末尾是新节点，头部是最先进入的节点，所以从头部开始弹出
                del self.map[node.key]
                self.size -= 1
            node = Node(key, value)
            self.list.append(node)
            self.map[key] = node
            self.size += 1

    def get(self, key):
        """获得节点的值"""
        if key not in self.map:
            return -1
        else:
            return self.map[key].value

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = FIFOCache(2)
    cache.put(1, 1)
    cache.print()
    cache.put(2, 2)
    cache.print()
    print(cache.get(1))

20190822