手机的物理结构是有限的，内存的存储也是有限的，所以就需要在内存不足时对数据进行清理。
内存的淘汰机制主要有以下几种：
1、FIFO （First In, First Out）
先进先出算法
2、LFU (Least Frequently Used)
最不经常使用算法
3、LRU (Least Recently Used)
最近最少使用算法

自己实现Lru算法

下面我们详细说明下LRU最近最少使用算法。

下面我们将使用单链表来实现LRU算法。
我们在上一篇文章自己用单链表实现的LinkedList 基础上进行操作。
首先将LinkedList里面的一些私有变量和方法改为用protected修饰。
然后我们实现Lru算法。

public class MyLruLinkedList<T> extends MyLinkedList<T> {
    private static final int DEFAULT_SIZE = 5;
    private int memorySize;

    public MyLruLinkedList() {
        this(DEFAULT_SIZE);
    }

    public MyLruLinkedList(int memorySize) {
        this.memorySize = memorySize;
    }

    /**
     * 添加数据
     *
     * @param data
     */
    public void addLru(T data) {
        //如果元素个数大于设置的最大存储数，则需要删除队尾的节点
        if (size >= memorySize) {
            //删除链表尾部的节点
            removeLast();
            //添加数据
            add(data);
        } else {
            //没有超过最大存储数，则直接添加
            add(data);
        }
    }

    /**
     * 删除数据，因为Lru是删除队尾最近最少使用的数据，所以直接删除链表最后一个节点即可
     *
     * @return
     */
    public T removeLru() {
        return removeLast();
    }

    /**
     * 获取数据，需要把访问的数据移动到链表的头部
     *
     * @param index
     * @return
     */
    public T getLru(int index) {
        checkIndexOutOfBounds(index);
        Node preNode = head;
        Node currentNode = head;
        for (int i = 0; i < index; i++) {
            preNode = currentNode;
            currentNode = currentNode.next;
        }

        //需要将访问的节点移动到链表表头，所以需要把访问节点的前一个节点的next指向访问节点的下一个节点
        preNode.next =  currentNode.next;
        //获取原来的头部
        Node headLast = head;
        currentNode.next = headLast;
        //访问的节点成为新的表头
        head = currentNode;
        return currentNode.data;
    }
}

测试代码：

public static void main(String[] args) {
        MyLruLinkedList<Integer> MyLruLinkedList = new MyLruLinkedList<>(5);
        for(int i = 0; i <4; i++) {
            MyLruLinkedList.addLru(i);
        }
        MyLruLinkedList.toString();
        System.out.println(MyLruLinkedList.getLru(3));
        MyLruLinkedList.toString();
        MyLruLinkedList.addLru(20);
        MyLruLinkedList.toString();

        MyLruLinkedList.addLru(18);
        MyLruLinkedList.toString();
    }

我们看下输出结果：
3 2 1 0
0
0 3 2 1
20 0 3 2 1
18 20 0 3 2

由输出结果我们可以看到，新添加和访问的节点都移动到了链表头部，并且当添加的数据操作最大限度时，会删除链表尾部的节点。所以是满足Lru算法的要求的。