数据结构：单链表实现LRU缓存淘汰算法

紧接着上一篇博客：单链表简单实现——通过单链表实现LRU缓存淘汰算法
LRU（Least recently used，最近最少使用）
算法根据数据的历史访问记录来进行淘汰，其核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高。反过来就是淘汰掉最近最少使用的，通过链表实现：

1. 将要缓存的数据放入链表表头。
2. 如果有数据被访问，则将被访问的数据移动到链表表头。
3. 一旦有新的数据将要被缓存，但是缓存空间已满，则删除尾部数据。

/**
 * @author lichen
 * @version 1.0.0
 * @date 2020-05-12 9:43
 */
public class LruLinkedList<T> extends LinkedList<T> {

    int memorySize;
    static final int DEFAULT_CAP = 5;

    public LruLinkedList() {
        this(DEFAULT_CAP);
    }

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

    public void lruPut(T data) {
        if (size >= memorySize) {
            removeTail();
        }
        addHead(data);
    }

    public T lruRemove() {
        return removeTail();
    }

    public T lruGet(int index) {
        checkPositionIndex(index);
        Node pre = node;
        Node cur = node;
        for (int i = 0; i < index; i++) {
            pre = cur;
            cur = cur.next;
        }
        Node head = node;
        pre.next = cur.next;
        cur.next = head;
        node = cur;
        return cur.data;
    }

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

        lruLinkedList.lruPut(18);
        lruLinkedList.toString();
        lruLinkedList.lruRemove();
        lruLinkedList.toString();
    }


}