简单实现LRU缓存淘汰算法

全明星记得给wade投票哦！！！

最近没怎么写博客了，因为自从我写了几篇微信公众号之后，我就觉得微信公众号比博客好写多了，而且分享在朋友圈看的人也多。然后这几天想了一下，还是应该坚持写博客，微信公众号不太适合纯技术分享而且在PC端要想看的话还得手机把文章分享到PC端才知道网址。博客就不一样了，要想看我的博客不管你是啥终端直接访问我的博客域名zhangxingr.github.io，理论上一直都可以访问，除非github倒闭了或者在国内被墙了。好啦，下面开始说正文，今天是简单实现LRU缓存淘汰算法。

LRU缓存淘汰算法（Least Recently Used），直白的解释就是最近最少使用的缓存淘汰算法，它有两个作用，一个是淘汰剔除调最近这段时间很少使用的数据，一个是把使用频率高的数据、最近使用的数据放在要读取的数据块的最前面方便读取。

我用Java简单实现了一个LRU缓存淘汰算法。主要的原理就是，我们维护一个最大长度固定的链表，比如最大长度为10。那么当往这个链表插入数据的时候，我们遍历链表，看这个插入的数据再链表中是否已经存在，如果存在则将数据从当前位置移除并添加到链表头部；如果数据不存在则还要看当前链表满还是没有满，如果没有满则直接添加到头部，如果满了则删除链表末尾的数据再将数据添加到头部。这样我们就保证了最新的、使用频率最高的数据永远再链表的头部位置。

下面是具体的代码：

package com.structure;

import java.util.LinkedList;

/**
 * @author zhangxingrui
 * @create 2019-01-11 16:23
 **/
public class MainLRU {

    private static LinkedList<Integer> list = new LinkedList<>();
    private static int size = 10;

    public static void main(String[] args) {
        // 初始化链表数据
        init();

        add(new Node(9));
        add(new Node(10));
        add(new Node(11));
    }

    private static void init(){
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
    }

    private static void add(Node node){
        boolean flag = false;
        int a = 0;
        for (Integer num : list) {
            if(num == node.data){
                flag = true;
                list.remove(a);
                list.add(0, num);
                System.out.println("添加数据的时候数据已存在的情况：" + list);
                break;
            }
            a++;
        }

        // 如果数据没有存在于链表中
        if(!flag){
            if(list.size() < size){
                // 如果数据还没有满，则直接添加到头部
                list.add(0, node.data);
                System.out.println("添加数据的时候数据不存在，同时链表未满的情况：" + list);
            }else{
                // 如果数据已满，则先删除末尾数据再把数据添加到头部
                list.remove(size - 1);
                list.add(0, node.data);
                System.out.println("添加数据的时候数据不存在，同时链表已满的情况：" + list);
            }
        }
    }

}

好啦，本文到此结束，不知道看我博客的朋友有没有喜欢看小说的，最近看了一部小说叫“大王饶命”，挺好看的，是我最近这几年看的最好的一部小说了。