依据单向链表手动实现LRU算法

雨点打透心脏的1/2处 2022-11-14 10:09 129阅读 0赞

今天我们依据单向链表 手动实现LRU算法：

一、LRU算法介绍：

1、首先，什么是LRU算法呢？

LRU全称 "Least Recently Used"，最近最少使用策略，判断最近被使用的时间，距离目前最远的数据优先被淘汰，作为一种根据访问时间来更改链表顺序从而实现缓存淘汰的算法，它是redis采用的淘汰算法之一。

2、原理图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

二、首先单链表实现代码（上篇文章分析过，此处仅贴代码）：

参考：[手写单向链表][Link 1]

package com.example.demo.linked.lruandlfu;
    
    class NandaoLinkedList<T> {
    
        Node list;
        int size;
    
        public NandaoLinkedList(){
            size = 0;
        }
    
        /**
         * 头部添加节点
         * @param data
         */
        public void put(T data){
            Node cur = new Node(data,list);
            list = cur;
            size ++;
        }
    
        /**
         * 在指定位置插入节点数据
         * @param index
         * @param data
         */
        public void put(int index,T data){
            Node head = list;
            Node cur = list;
            for(int i = 0; i < index;i++){
                head = cur;
                cur = cur.next;
            }
            cur = new Node(data,cur);
            head.next = cur;
            size++;
        }
    
        /**
         * 删除头部节点
         * @return
         */
        public T remove(){
            if (list != null) {
                Node head = list;
                list = head.next;
                head.next = null;
                size--;
            }
            return null;
        }
    
        /**
         * 删除指定位置的数据
         * @param index
         * @return
         */
        public T remove(int index){
            checkPositionIndex(index);
            if(index == 0){//首节点删除
                remove();
            }else {
                Node head = list;
                Node cur = list;
                for(int i=0;i<index;i++){
                    head = cur;
                    cur = cur.next;
                }
                head.next = cur.next;
                cur.next = null;
                size--;
            }
            return null;
        }
    
        /**
         * 删除未节点
         * @return
         */
        public T removeLast(){
            Node head = list;
            Node cur = list;
            if(list != null){
                while (cur.next != null){
                    head = cur;
                    cur = cur.next;
                }
                head.next = null;
                size--;
            }
            return null;
        }
    
        /**
         * 修改指定节点
         * @param index
         * @param newData
         * @return
         */
        public T setNode(int index,T newData){
            checkPositionIndex(index);
            Node cur = list;
            for(int i=0;i<index;i++){
                cur = cur.next;
            }
            cur.data = newData;
            return null;
        }
    
        /**
         * 获取头节点数据
         * @return
         */
        public T get(){
            if(list != null){
                return list.data;
            }else {
                return null;
            }
        }
    
        /**
         * 查询指定位置参数
         * @param index
         * @return
         */
        public T get(int index){
            checkPositionIndex(index);
            Node cur = list;
            for(int i=0;i<index;i++){
                cur = cur.next;
            }
            return cur.data;
        }
    
        /**
         * 链表节点是否越界的验证
         * @param index
         */
        public void checkPositionIndex(int index) {
            if(!(index>=0 && index <= size)){
                throw new IndexOutOfBoundsException("传的位置参数不在此链表范围之内！");
            }
        }
    
        /**
         * 链表节点的内部类
         */
        class Node{
            T data;
            Node next;
            public Node(T data,Node node){
                this.data = data;
                this.next = node;
            }
        }
    
        @Override
        public String toString() {
            Node node = list;
            System.out.println("结果为：");
            for(int i=0;i < size;i ++){
                System.out.print(node.data+ " ");
                node = node.next;
            }
            System.out.println("结束了！");
            return super.toString();
        }
    
        public static void main(String[] args) {
            NandaoLinkedList<Integer> linkedList = new NandaoLinkedList();
    
            linkedList.put(12);
            linkedList.put(2);
            linkedList.put(3);
            linkedList.put(4);
            linkedList.put(5);
            linkedList.put(6);
    
           // linkedList.put(2,2);
    
            //linkedList.remove();
          //  linkedList.remove(0);
           /// linkedList.removeLast();
            //linkedList.setNode(1,1);
          //  Integer integer = linkedList.get();
            Integer integer = linkedList.get(15);
            System.out.println("查询结果："+integer);
    
    
            //String s = linkedList.toString();
            //System.out.println("返回值："+ s );
        }
    
    }

三、LRU算法实现：

0、定义一个类继承链表类：

public class NandaoLruLinkedList<T> extends NandaoLinkedList<T> {
    
    //省略。。。。。
    }

1、参数及构造方法解析

int memory_size;//自定义最大容量
    
    static final int DEFAULT_SIZE = 5;//默认最大容量
    
    /**
     * 无参构造函数
     */
    public NandaoLruLinkedList(){
        this.memory_size =DEFAULT_SIZE;
    }
    
    /**
     * 有参构造函数
     * @param default_memory_size
     */
    public NandaoLruLinkedList(int default_memory_size){
        this.memory_size = default_memory_size;
    }

2、添加方法：

/**
     * 添加方法
     * @param data
     */
    public void lruPut(T data){
        if(size >= memory_size){
            removeLast();
            put(data);
        }else {
            put(data);
        }
    }

3、删除方法：

/**
     * 删除方法
     * @return
     */
    public T lruRemove(){
        return removeLast();//调用父类的方法
    }

4、查询方法：

/**
     * 查询方法
     * @return
     */
    public T lruGet(int index){
        checkPositionIndex(index);
        Node head = list;
        Node cur = list;
        Node pre = list;
        for(int i=0;i<index;i++){
            head = cur;
            cur = cur.next;
        }
        T data = cur.data;
        //把查到的节点放到头节点
        if(index > 0){
            head.next = cur.next;
            cur.next = pre;
            list = cur;
        }
        return data;
    }

5、测试方法

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

6、执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

到此，LRU算法分享完成，下篇我们分析LRU类似的算法LFU，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/2ff5fd77a68b4681b1e34f3c0609eab8.png
[Link 1]: https://blog.csdn.net/nandao158/article/details/115279515
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221022/94ef1df31bda4ab29aa7ae02ce608fc7.png