数据结构与算法-----LRU算法的实现_lru算法数据结构

(一)定义

LRU是Least Recently Used的缩写，即最近最少使用、选择最久未使用的数据予以淘汰，它的目的是为了解决数据缓存空间不足时淘汰数据的顺序

(二)原理

基于单向链表实现的LRU算法，它的实现特点如下
1、添加新数据时添加在链表的头部
2、当数据命中，数据要移动到表头(命中：链表中的数据被访问)
3、(添加数据时)链表的缓存空间满时，将链表尾部的数据丢弃

(三)代码实现(基于单向链表)

LRUList.java

/**
 * 单向链表
 */
public class LRUList<T> {
    private Node headNode;  //头节点
    private int size;  //节点数

    public LRUList() {
        size = 0;
    }

    //再链头添加新的节点
    public void add(T data) {
        Node newNode = new Node(data, headNode);
        headNode = newNode;
        size++;
    }

    //查询节点
    public T get(int index) {
        checkPositionIndex(index);
        if (headNode != null) {
            Node target = headNode;
            for (int i = 0; i < index; i++) {
                target = target.next;
            }
            return target.mData;
        }
        return null;
    }

    //删除节点
    public boolean remove(int index) {
        checkPositionIndex(index);
        if (headNode != null) {
            Node head = headNode;
            Node target = headNode;
            for (int i = 0; i < index; i++) {
                head = target;
                target = target.next;
            }
            head.next = target.next;
            target.mData = null;
            target = null;
            size--;
            return true;
        }
        return false;
    }

    public boolean removeLast() {
        if (headNode != null) {
            Node head = headNode;
            Node target = headNode;
            while (target.next != null) {
                head = target;
                target = target.next;
            }
            head.next = null;  //链尾
            target.mData = null;  //gc
            size--;
            return true;
        }
        return false;
    }

    //判断下标是否符合条件
    public void checkPositionIndex(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("下标溢出");
    }


    //toString()方法
    @Override
    public String toString() {
        Node head = headNode;
        while (head.next != null) {
            System.out.print(head.mData + " ");
            head = head.next;
        }
        System.out.println();
        return super.toString();
    }

    //返回链表的节点数
    public int size() {
        return size;
    }

    //获取头节点
    public Node getHead() {
        if (headNode != null)
            return headNode;
        return null;
    }

    //设置头节点
    public void setHead(Node node) {
        this.headNode = node;
    }

    //节点
    class Node {
        private T mData;
        private Node next;

        public Node(T mData, Node mNode) {
            this.mData = mData;
            this.next = mNode;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

LRU算法表：
LRUDemo.java

public class LRUDemo<T> extends LRUList<T> {
    private int size;  //缓存大小
    private static final int DEFAULT_SIZE = 5; //默认缓存大小

    public LRUDemo() {
        this(DEFAULT_SIZE);
    }

    public LRUDemo(int size) {
        this.size = size;
    }

    //添加节点
    public void LRUAdd(T data) {
        if (size < size())
            removeLast();  //如果链表中的的个数大于最大缓存
        add(data);  //链表中的add方法
    }

    //查看节点
    public T LRUget(int index) {
        checkPositionIndex(index);  //链表中的下标判断方法
        T data = get(index);
        remove(index);
        Node node = new Node(data, getHead());
        setHead(node);
        return data;
    }

    //删除节点
    public boolean LRURemove() {
        if (getHead() != null) {
            removeLast();
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LRUDemo lru = new LRUDemo();
        for (int i = 0; i < 6; i++) {
            lru.LRUAdd("data"+i);
        }
        System.out.print("添加的数据："+" ");
        lru.toString();
        System.out.print("缓存满时添加数据后的显示："+" ");
        lru.LRUAdd(2520);
        lru.toString();
        System.out.print("命中(index = 2)数据后的显示："+" ");
        lru.LRUget(2);
        lru.toString();
        lru.LRURemove();
        System.out.print("URL删除数据后的显示："+" ");
        lru.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

结果截图：

由于是基于单向链表的LRU算法，所以在实现LRU算法时，我们先要实现单向链表(单向链表的具体解析点击进入)，在LRU算法代码中，有两个构造方法LRUDemo()、LRUDemo(int size)，它们分别是设置缓存大小的默认值和自定义缓存值，基于LRU算法的原理，添加节点 LRUAdd(T data)时，我们要先判断单向链表中的个数是否大于LRU缓存的大小(size < size())，如果大于先删除链尾的节点再往链头上添加节点，否则直接往链头上添加节点；在LRUget(int index)(查看节点)中，我们先将目的节点删除(remove(index));，再将这个节点添加到链头（Node node = new Node(data, getHead());）并设置链头的指向节点(setHead(node););由于LRU算法的删除是在链尾中进行的，因此我们只需直接调用单向链表中的removeLast();方法即可。

ok,lru算法的讲解到此就结束了，如果对你有帮助的话 本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】