数据结构系列之单链表实现一个简单的LRU算法

更多文章&＃xff0c;欢迎关注微信公众号&＃xff1a;深夜程猿

在上一篇文章简单聊聊了LRU算法理论篇&＃xff0c;这里就和大家使用单链表实现一个简单的LRU算法。其它类型的实现一样的思路&＃xff0c;只不过是处理的复杂程度不一样而已。

Node.java&＃xff1a;存储数据的结点

package lru;/*** &＃64;author wu* &＃64;since 2019/4/2*/ public class Node {private V data;private K key;/*** 指针&＃xff0c;指向下一节点*/private Node next;public V getData() {return data;}public void setData(V data) {this.data &＃61; data;}public Node getNext() {return next;}public void setNext(Node next) {this.next &＃61; next;}public K getKey() {return key;}public void setKey(K key) {this.key &＃61; key;} }

LinkedLru.java&＃xff1a;LRU实现

package lru;/*** &＃64;author wu* &＃64;since 2019/4/2*/ public class LinkedLru {private Node root;private int maxCapacity;private int defaultCapacity &＃61; 10;public LinkedLru(int maxCapacity) {if (maxCapacity <&＃61; 0) {throw new IllegalArgumentException("maxCapacity should not less than 0");}this.maxCapacity &＃61; maxCapacity;}public int getMaxCapacity() {return maxCapacity;}public LinkedLru() {this.maxCapacity &＃61; defaultCapacity;}public Node get(K key) {if (key &＃61;&＃61; null) {throw new IllegalArgumentException("key should not be null");}if (root &＃61;&＃61; null) {return null;}Node temp &＃61; root;while (temp !&＃61; null) {if (key.equals(temp.getKey())) {Node node &＃61; new Node<>();node.setData(temp.getData());node.setKey(temp.getKey());return node;}temp &＃61; temp.getNext();}return null;}public boolean add(Node data) {if (data &＃61;&＃61; null) {throw new IllegalArgumentException("can not cache null");}if (root &＃61;&＃61; null) {root &＃61; data;return true;} else {Node prev &＃61; root;Node next &＃61; root.getNext();Node header &＃61; root;Node cursor;int index &＃61; 1;while (true) {index&＃43;&＃43;;cursor &＃61; prev;if (index >&＃61; getMaxCapacity()) {// 设置data为头部结点data.setNext(header);root &＃61; data;// 缓存达到最大值&＃xff0c;淘汰数据&＃xff0c;此时prev就是尾部结点cursor.setNext(null);break;}if (next &＃61;&＃61; null) {// 容量没有达到最大&＃xff0c;已到缓存尾部&＃xff0c;并且数据还没有缓存过data.setNext(header);root &＃61; data;cursor.setNext(null);break;}if (next.getKey() &＃61;&＃61; data.getKey()) {// 数据存在&＃xff0c;交换指针&＃xff0c;数据放在首部data.setNext(header);prev.setNext(next.getNext());root &＃61; data;break;}prev &＃61; next;next &＃61; next.getNext();}}return true;}public Node getRoot() {return root;} }

测试类&＃xff1a;

package lru;import com.alibaba.fastjson.JSON;/*** &＃64;author wu* &＃64;since 2019/4/3*/ public class Test {public static void main(String[] args) {LinkedLru cache &＃61; new LinkedLru<>(10);int pos &＃61; 0;while (pos <100) {pos&＃43;&＃43;;Node node &＃61; new Node();node.setKey("key:" &＃43; pos);node.setData("data:" &＃43; pos);cache.add(node);}System.out.println(JSON.toJSONString(cache.getRoot()));System.out.println(JSON.toJSONString(cache.get("key:10")));System.out.println(JSON.toJSONString(cache.get("key:100")));}}

输出&＃xff1a;

{"data":"data:100","key":"key:100","next":{"data":"data:99","key":"key:99","next":{"data":"data:98","key":"key:98","next":{"data":"data:97","key":"key:97","next":{"data":"data:96","key":"key:96","next":{"data":"data:95","key":"key:95","next":{"data":"data:94","key":"key:94","next":{"data":"data:93","key":"key:93","next":{"data":"data:92","key":"key:92","next":{"data":"data:91","key":"key:91"}}}}}}}}}} null {"data":"data:100","key":"key:100"}