forked from wangzheng0822/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLRUBaseLinkedList.java
More file actions
176 lines (147 loc) · 3.64 KB
/
LRUBaseLinkedList.java
File metadata and controls
176 lines (147 loc) · 3.64 KB
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
package linked.singlelist;
import java.util.Scanner;
/**
* 基于单链表LRU算法（java）
*
* @author hoda
* @create 2018-12-17
*/
public class LRUBaseLinkedList<T> {
/**
* 默认链表容量
*/
private final static Integer DEFAULT_CAPACITY = 10;
/**
* 头结点
*/
private SNode<T> headNode;
/**
* 链表长度
*/
private Integer length;
/**
* 链表容量
*/
private Integer capacity;
public LRUBaseLinkedList() {
this.headNode = new SNode<>();
this.capacity = DEFAULT_CAPACITY;
this.length = 0;
}
public LRUBaseLinkedList(Integer capacity) {
this.headNode = new SNode<>();
this.capacity = capacity;
this.length = 0;
}
public void add(T data) {
SNode preNode = findPreNode(data);
// 链表中存在，删除原数据，再插入到链表的头部
if (preNode != null) {
deleteElemOptim(preNode);
intsertElemAtBegin(data);
} else {
if (length >= this.capacity) {
//删除尾结点
deleteElemAtEnd();
}
intsertElemAtBegin(data);
}
}
/**
* 删除preNode结点下一个元素
*
* @param preNode
*/
private void deleteElemOptim(SNode preNode) {
SNode temp = preNode.getNext();
preNode.setNext(temp.getNext());
temp = null;
length--;
}
/**
* 链表头部插入节点
*
* @param data
*/
private void intsertElemAtBegin(T data) {
SNode next = headNode.getNext();
headNode.setNext(new SNode(data, next));
length++;
}
/**
* 获取查找到元素的前一个结点
*
* @param data
* @return
*/
private SNode findPreNode(T data) {
SNode node = headNode;
while (node.getNext() != null) {
if (data.equals(node.getNext().getElement())) {
return node;
}
node = node.getNext();
}
return null;
}
/**
* 删除尾结点
*/
private void deleteElemAtEnd() {
SNode ptr = headNode;
// 空链表直接返回
if (ptr.getNext() == null) {
return;
}
// 倒数第二个结点
while (ptr.getNext().getNext() != null) {
ptr = ptr.getNext();
}
SNode tmp = ptr.getNext();
ptr.setNext(null);
tmp = null;
length--;
}
private void printAll() {
SNode node = headNode.getNext();
while (node != null) {
System.out.print(node.getElement() + ",");
node = node.getNext();
}
System.out.println();
}
public class SNode<T> {
private T element;
private SNode next;
public SNode(T element) {
this.element = element;
}
public SNode(T element, SNode next) {
this.element = element;
this.next = next;
}
public SNode() {
this.next = null;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
public static void main(String[] args) {
LRUBaseLinkedList list = new LRUBaseLinkedList();
Scanner sc = new Scanner(System.in);
while (true) {
list.add(sc.nextInt());
list.printAll();
}
}
}