LRU

简单介绍

还记得第一次听到些词是在计算机组成原理课上，讲高速缓存存储器-cache章节涉及到的，当时一脸懵逼不知道说的是啥。

• LRU - 最近最少使用策略(Lastest Recently Used)
• LFU - 最少使用策略(Lastest Frequently Used)
• FIFO - 先进先出(First In First Out)

大家都是比较实在的人，相信大家肯定也不喜欢硬背这些东西，其实他们离我们生活很近，只是我们忽略了没有在意它们。

你可以试想一下如果现在有一大堆书，你会以什么方式扔这些书，对应⼀下，你的选择标准是不是和上⾯的三种策略神似呢？

链表实现LRU

下面用链表实现以下LRU策略。

要求是：链表做存储，当链表满了，我们就按照LRU最近最少使用策略的丢数据。

1.链表数据结构

public class LRULinkedList<T> {

    // 记录当前容量
    private int CAPACITY = 0;

    // 默认容量
    private int DEFAULT_CAPACITY = 5;

    // 设置守卫简化代码
    private SNode head;

    // 链表节点
    class SNode<T> {
        // 数据
        T data;
        // 指向下一个节点的指针
        SNode next;
    }
}

守卫

守卫的意思是守护边界，用于管理边界的一些操作，因为边界操作往往会出现很多种情况十分复杂，利用守卫就可以屏蔽掉多种情况，这是编码的一种技巧。

下面用两组场景，说一下写它的原因。

第一组

比如往链表结点p后⾯插⼊⼀个新的结点，正常插入只需要这样写。

newNode->next = p->next; 
p->next = newNode;

但是，当我们要向⼀个空链表中插⼊第⼀个结点，上面两行代码就不工作了，代码要在原有的基础上写一层判断，像下面这样子。

if(head == null){
    head = newNode;
}

第二组

再比如删除链表中的节点，如果要删除p节点的后继节点，只需要这样写

p->next = p->next->next;

但是如果要删除最后一个节点，就要多写下面的内容。

if (head->next == null) { 
    head = null; 
}

这么写简直太糟糕了，条件少还能吼得住，条件多少一个就是bug，怪不得老加班。那问题来了，有没有办法省掉第一组和第二组判断的那部分代码呢？

这时候就要用守卫来解决了，带守卫的链表叫带头链表，没有守卫节点的叫不带头链表，守卫在链表中并不存任何数据，像下图这样。

这样的技巧在数据结构与算法代码编写中十分常用，⽐如插⼊排序、归并排序、动态规划等，如果感觉有点不太理解，带守卫和不带守卫都可以尝试着写写，debug一下看看。

2.代码实现

// 添加
public void add(T data) {

    SNode preNode = findPreNode(data);

    if(preNode != null){
        // 删除前一个节点的下一个节点，也就是当前节点有点绕。。
        delete(preNode);
        // 插入到头
        insertBegin(data);
    }else{
        if(CAPACITY > DEFAULT_CAPACITY){
            // 删除最后节点
            deleteEnd();
        }
        insertBegin(data);
    }

}

// 删除队尾
public void deleteEnd() {
    SNode ptr = head;

    // 判断队列是否为空
    if(ptr.next == null){
        return;
    }

    // 找到倒数第二个节点
    while(ptr.next.next != null){
        ptr = ptr.next;
    }

    // 删除最后节点
    SNode tmp = ptr.next;
    ptr.next = null;
    tmp = null;
    CAPACITY--;
}

public void insertBegin(T data) {
    // 插入对头
    SNode next = head.next;
    head.next = new SNode(data,next);
    CAPACITY++;
}

// 删除当前节点
public void delete(SNode preNode) {
    SNode tmp = preNode.next;
    preNode.next = tmp.next;
    tmp = null;
    CAPACITY--;

}

// 寻找data对应的前一个节点
public SNode findPreNode(T data) {
    SNode node = head;
    while(node.next != null){
        if(data.equals(node.next.data)){
            return node;
        }
        node = node.next;
    }

    return null;
}

方便折腾下面是源码