LRU算法详解以及实现_牛客lru算法

定义：LRU（Least Recently Used）最近最少使用的，就是剔除旧的很少使用的。
LRU算法的规则：

1、新数据插入到链表头部；

2、当缓存命中（即缓存数据被访问），数据要移到表头；

3、当链表满的时候，将链表尾部的数据丢弃。

注意：在写LRU算法之前一定要好好看看链表部分，单双链表！！！！！

根据单链表的数据节点规则，编写LRU算法。

要实现LRU算法，先编写我们自己的单链表：LinkList

我是参照双链表中的增删改查来下写的：

一、编写自定义的LinkList类（单链表形式）

1、首先编写一个类部类节点：节点命名为Node；T为泛型数据；next为下一个节点。

2、添加所需要的参数：size链表的长度；Node first：第一个节点。构造函授，一个带参数一个不带参数。

3、研究数据结构就是研究数据的增删改查；所以先写增加方法：

3.1、put()：从头部添加数据，越往后越靠近链表头；代码如下：

说明：new Node的时候，相当于已经把next节点给找出来了，就是first。

3.2、put(int index)从任意节点添加数据：

（1）首先检查脚标index是否越界

（2）命名两个节点，一个prev和一个current；用for循环找出index所在节点current；

（3）在prev和current之间插入一个新节点Node newNode = new Node（data,current），current节点就是newNode.next的节点。

（4）把prev.next指向newNode;size++。

4、实现删除方法：

4.1、public T remove()删除头部数据节点：

（1）判断整个节点是否为空；

（2）命名头部节点head=first节点；然后头部节点指向空：head.next=null；

（3）把第二个节点移到第一个节点：first = first.next; size--;

4.2、public T remove（int index）:删除任意位置的节点

（1）检查脚标index是否越界

（2）命名当前节点current，前一个节点prev；用for循环找出current节点和prev节点；

（3）因为是删除，所有prev.next节点指向current.next; current.next=null(表示current已经被剔除，促进GC回收);size--;

4.3、public T removeLast()：删除尾部数据

（1）判断节点first是否为空

（2）命名倒数第二个节点为prev，最后一个节点为last；用while循环找出最后一个节点last和前一个节点prev；

（3）因为这个不是循环单链表，所以prev.next=null 表明prev是最后一个节点；size--；

5、实现改方法：

5.1、public void set(int index,T data)：修改任意位置节点的数据

（1）判断脚标是否越界

（2）命名current节点；用for循环找出index下的节点current；

（3）修改current的数据：current.data = data;

6、查找方法：

6.1、public T get(int index):查找任意位置的数据

（1）检查脚标是否越界

（2）命名一个current节点，用for循环找出当前的节点current；

（3）返回current.data

好了，自定义的单链表LinkList已经完成！下面按照LRU算法规则编写

二、按照LRU规则编写LRU算法：

（1）新数据插入到链表头部；

（2）当缓存命中（即缓存数据被访问），数据要移到表头；

（3）当链表满的时候，将链表尾部的数据丢弃。

1、定义一个LRU算法类：LRULinkList 继承 LinkList;

1.1、编写一个默认内存长度：DEFAULT_MEMORY=5;再定义一个momerySize;来一个带参和不带参的构造方法。

2.1、按照规则：新添加的数据放到链表头部：public void lruPut()

（1）判断内存是否已满

（2）如果内存已满，先删除尾部数据，再添加数据到头部；如果未满，直接添加数据到头部

2.2、删除尾部数据：public T lruRemove()

（1）直接调用父类的removeLast()方法即可。

2.3、被访问的缓存数据，移动到链表头部：public T lruGet(int index)

（1）判断脚标是否越界

（2）定义一个前节点prev和一个当前节点current；用for循环找出当前节点current和前一个节点prev；

（3）移动current节点，要先将current移除当前位置，所以：prev.next=current.next 就是前一个节点的next指向当前节点的next;

（4）将current节点移到链表头部：current.next = first; 节点first要放在第一位：first=current；

写完之后看一下测试结果：

URL算法编写完毕，如果有错误请指正，需要源码的留下联系方式

原文作者：Android_Joey

原文地址：LRU算法详解以及实现（版权归原文作者所有，侵权留言联系删除）