什么是LRU算法
Least Recently Used，最近最少使用，当数据超过容量时，淘汰最近最少使用的一个然后再进行添加。
用单链表来进行实现：
维护一个链表，从头插入数据。当新数据插入时将新数据作为头部，指向旧的头结点。
向一个单链表插入数据，首先遍历这个链表，查看数据是否已经存在于链表中。如果存在，则删除原有数据，将新数据插入到头结点。
如果不存在，先看是否已经到达容量，如果没有到达容量则插入到头结点。如果到达容量则删除尾部节点，再进行插入。
在这个过程中，将最近使用过的又重新插入到了头部，在链表尾部的就是最近最少使用的一项，所以从尾部删除。
数据结构
首先我们需要定义一下节点的数据结构：
1
2
3
4
5
6
7
|
class Node {
Node next;
int val;
public Node(int val) {
this.val = val;
}
}
|
为了方便直接使用int作为存储的数据结构
定义实现
lru需要一个容量，以及链表的长度，还有头结点
我们添加节点，定义一个添加方法
为了方便查看数据，我们再定义一个打印数据方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class LruList {
Node head;
int length;
int maxLength;
public LruList(int maxLength){
this.maxLength = maxLength;
}
void add(int val){
...
}
void print(){
Node temp = head;
while (temp != null) {
System.out.print(temp.val + " ,");
temp = temp.next;
}
System.out.println();
}
}
|
我们在插入的时候，需要向头部插入，如果重复则删除当前节点，或者删除最后一个节点，我们将其抽离为单独的方法。最终的代码如下：
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
|
class LruList {
Node head;
int length;
int maxLength;
public LruList() {
}
public LruList(int maxLength) {
this.maxLength = maxLength;
}
void add(int val) {
Node node = new Node(val);
//当链表为空的情况
if (head == null) {
head = node;
length++;
return;
}
if (head.val == val) {
//如果是跟头部一样，则直接返回，因为需要先删除这个头部旧节点再添加，所以直接返回不做操作
return;
}
//进行遍历，查找是否已经存在，由于已经比较过头结点，所以从第二个节点开始
//同时，保存两个节点，便于删除
Node e = head;
Node next = e.next;
while (e != null && next != null) {
if (next.val == val) {
e.next = next.next;
next = null;
addHead(node);
return;
}
e = e.next;
next = next.next;
}
//新插入节点不存在，判断是否超过容量
if (length < maxLength) {
addHead(node);
length++;
} else {
//删除尾部节点，然后再从头插入
deleteLast();
addHead(node);
}
}
/**
* 删除尾部节点
*/
private void deleteLast() {
Node t = head;
while (t.next != null && t.next.next != null) {
t = t.next;
}
t.next = null;
}
/**
* 从头部插入节点
*/
private void addHead(Node e) {
e.next = head;
head = e;
}
/**
* 将链表打印
*/
void print() {
Node temp = head;
while (temp != null) {
System.out.print(temp.val + " ,");
temp = temp.next;
}
System.out.println();
}
}
class Node {
Node next;
int val;
public Node(int val) {
this.val = val;
}
}
|
测试一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void main(String[] args) {
LruList lruList = new LruList(5);
lruList.add(1);
lruList.add(2);
lruList.add(3);
lruList.add(4);
lruList.add(5);
lruList.add(1);
lruList.add(1);
lruList.add(3);
lruList.add(4);
lruList.add(5);
lruList.print();
}
|
最终打印结果为5,4,3,1,2。跟我们预期的结果一致。