一、双向链表原理
顾名思义，双向链表跟单链表和循环列表最大的差别，就是同时拥有前驱指针和后驱指针，基于这一个特性，查询某结点的前一个结点，时间复杂度可以达到O(1)，非常高效。双向链表的存取时间复杂度是O(n)，增删时间复杂度为O(1)，跟其他链表没啥区别。
双向链表表示意图：
双向链表.jpg
所以双向链表的结点定义如下：
class Node{
Object data; //元素值
Node pre; //前驱指针
Node next; //后驱指针
}
对于双向链表做增删操作，有一定的顺序要求，顺序不对，很可能会造成空指针异常。
双向链表增加结点示意图：
双向链表增加结点示意图.png
双向链表删除结点示意图：
双向链表删除结点示意图.png
二、双向链表的实现-java
public class DoubleLinkedList {
/**
* 单向或者循环链表访问下一个结点的时间复杂度都是O(1)，但是访问上个结点的时间复杂度是O(n)
* 所以设计出了双向链表，相比于单向链表，除了有next指针，还有pre指针，可以实现访问上个结点
* 和下个结点的时间复杂度都是O(1)
*
* LinkedHashMap底层都是HashMap+双向链表实现
*/
/**
* 双向链表一般具有以下功能：
* 1.InitDoubleLinkedList() 初始化操作，建立一个空的双向链表
* 2.DoubleLinkedListEmpty() 判断双向链表是否为空，为空则返回true，非空返回false
* 3.DoubleLinkedListInsert(T elem) 在双向链表末尾插入数据，不需要手动指定位置
* 4.DoubleLinkedListInsertWithIndex(int index,T elem) 在双向链表脚标为index处插入新元素
* 5.DoubleLinkedListDelete() 删除双向链表尾部元素，并返回其值
* 6.DoubleLinkedListDeleteWithIndex(int index) 删除指定位置的元素结点，并返回其值
* 7.DoubleLinkedListDeleteWithElem(Object elem) 删除指定元素结点，并返回其值
* 8.DoubleLinkedListLenth() 返回双向链表的长度
* 9.toString() 打印双向链表的所有元素值，用逗号分隔
*/
int doubleLinkedNodeLength = 0; //假设头结点不占用大小
DoubleLinkedNode head = null;
public DoubleLinkedList(){
head = new DoubleLinkedNode(); // 创建一个双向链表的头结点
head.pre = head.next = head; // 初始化一个空的双向链表，头结点的前驱和后继都指向头结点本身
}
class DoubleLinkedNode{
// 定义一个双向链表的结点
Object nodeData = null;
DoubleLinkedNode pre = null;
DoubleLinkedNode next = null;
}
//实现DoubleLinkedListEmpty功能
public Boolean DoubleLinkedListEmpty(){
return doubleLinkedNodeLength == 0?true:false;
}
//实现DoubleLinkedListInsert功能
public Boolean DoubleLinkedListInsert(Object elem){
DoubleLinkedNode insertLinkedNode = null;
if (head.next == head){
//表示是一个空的双向链表
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.pre = head;
insertLinkedNode.next = head;
head.next = insertLinkedNode;
head.pre = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.next = head;
insertLinkedNode.pre = head.pre;
head.pre.next = insertLinkedNode;
head.pre = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}
//实现DoubleLinkedListInsertWithIndex功能
public Boolean DoubleLinkedListInsertWithIndex(int index,Object elem){
DoubleLinkedNode insertLinkedNode = null;
if (index <= 0 || index > doubleLinkedNodeLength+1){
return false;
}
if (index == 1){
//表示要插入头结点后面的位置
if (doubleLinkedNodeLength == 0){
//表示双向链表为空
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.pre = head;
insertLinkedNode.next = head;
head.next = insertLinkedNode;
head.pre = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}else{
//表示双向链表非空
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.next = head.next;
insertLinkedNode.pre = head;
head.next.pre = insertLinkedNode;
head.next = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}
}
if (index == doubleLinkedNodeLength+1){
// 表示需要插入到双向链表的最后一个位置，需要修改head.pre
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.next = head;
insertLinkedNode.pre = head.pre;
head.pre.next = insertLinkedNode;
head.pre = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}
int currIndex = 1;
DoubleLinkedNode currLinkedNode = head.next;
while (currIndex != index){
currIndex++;
currLinkedNode = currLinkedNode.next;
}
insertLinkedNode = new DoubleLinkedNode();
insertLinkedNode.nodeData = elem;
insertLinkedNode.next = currLinkedNode;
insertLinkedNode.pre = currLinkedNode.pre;
currLinkedNode.pre.next = insertLinkedNode;
currLinkedNode.pre = insertLinkedNode;
doubleLinkedNodeLength++;
return true;
}
//实现DoubleLinkedListDelete功能
public Object DoubleLinkedListDelete(){
DoubleLinkedNode rearLinkedNode = null; //待删除的尾部结点
Object elem = null;
if (doubleLinkedNodeLength == 0){return -1;}
rearLinkedNode = head.pre;
elem = rearLinkedNode.nodeData;
rearLinkedNode.pre.next = rearLinkedNode.next;
rearLinkedNode.next.pre = rearLinkedNode.pre;
rearLinkedNode.pre = rearLinkedNode.next = null;
doubleLinkedNodeLength--;
return elem;
}
//实现DoubleLinkedListDeleteWithIndex功能
public Object DoubleLinkedListDeleteWithIndex(int index){
DoubleLinkedNode LinkedNode = null;
Object elem = null;
if (doubleLinkedNodeLength == 0){return -1;}
if (index <= 0 || index > doubleLinkedNodeLength){return -1;}
int currindex = 1;
DoubleLinkedNode currLinkedNode = head.next;
while (currindex != index){
currindex++;
currLinkedNode = currLinkedNode.next;
}
elem = currLinkedNode.nodeData;
currLinkedNode.pre.next = currLinkedNode.next;
currLinkedNode.next.pre = currLinkedNode.pre;
currLinkedNode.pre = currLinkedNode.next = null;
doubleLinkedNodeLength--;
return elem;
}
//实现DoubleLinkedListDeleteWithElem功能
public Object DoubleLinkedListDeleteWithElem(Object elem){
DoubleLinkedNode LinkedNode = head.next;
Object deleteElem = null;
if (doubleLinkedNodeLength == 0){return -1;}
while (LinkedNode != head){
if (!(LinkedNode.nodeData.equals(elem))){
LinkedNode = LinkedNode.next;
continue;
}else{
break;
}
}
if (LinkedNode == head){return -1;} //表示未找到对应的元素结点
deleteElem = LinkedNode.nodeData;
LinkedNode.pre.next = LinkedNode.next;
LinkedNode.next.pre = LinkedNode.pre;
LinkedNode.pre = LinkedNode.next = null;
doubleLinkedNodeLength--;
return deleteElem;
}
//实现DoubleLinkedListLenth功能
public int DoubleLinkedListLenth(){
return doubleLinkedNodeLength;
}
//实现toString功能
public String toString(){
if (doubleLinkedNodeLength == 0){return "";}
DoubleLinkedNode doubleLinkedNode = head.next;
StringBuffer stringBuffer = new StringBuffer();
for (;doubleLinkedNode != head;doubleLinkedNode = doubleLinkedNode.next){
if (doubleLinkedNode.next != head){
stringBuffer.append(doubleLinkedNode.nodeData);
stringBuffer.append(",");
}else{
stringBuffer.append(doubleLinkedNode.nodeData);
}
}
return stringBuffer.toString();
}
public static void main(String[] args) {
}
}
三、用双向链表来实现LRU算法
3.1LRU(最近最少使用)算法
将不常被访问的数据进行淘汰，来保证有限空间的使用，在计算机cache当中广为应用，因为cache的大小有限，为了尽可能多的命中热数据，就可以将冷数据进行淘汰，充分利用内存空间。
3.2LRU核心思想
-》put进数据时，将其放于链尾，因为链尾的数据最不容易被淘汰，并且插入之前需要判断一下空间是否已满，如果满了，就需要将链头的数据淘汰掉。
-》get数据时，如果未在cache中命中，就返回-1，来模拟cache未命中的现象，如果命中，将该数据从当前位置删除，并移至链尾。
3.3使用双向链表来实现以下LRU算法
public class LeastRecentlyUsed {
/**
* 使用双向链表来实现LRU
* -》put方法
* -》get方法
*/
private DoubleLinkedList doubleLinkedList = null;
private int maxSize; // 内存大小
private int currSize; // 当前双向链表的大小
public LeastRecentlyUsed(int maxSize){
// 初始化LRU算法类的时候，生成一个双向链表
doubleLinkedList = new DoubleLinkedList();
this.maxSize = maxSize;
}
//实现put方法
public Boolean put(Object elem){
// get the doubleLinkedList currently size
currSize = doubleLinkedList.DoubleLinkedListLenth();
if (currSize == maxSize){
// 表示cache目前已处于待溢出状态
//先删除头结点后面的第一个结点数据，在插入数据
doubleLinkedList.DoubleLinkedListDeleteWithIndex(1);
//在双向链表的尾部添加数据
return doubleLinkedList.DoubleLinkedListInsert(elem);
}else{
//在双向链表的尾部添加数据
return doubleLinkedList.DoubleLinkedListInsert(elem);
}
}
//实现get方法
public Boolean get(Object elem){
// 直接删除该元素结点，如果存在返回该元素值，如果不存在返回-1
doubleLinkedList.DoubleLinkedListDeleteWithElem(elem);
// 在链表尾部插入该数据
doubleLinkedList.DoubleLinkedListInsert(elem);
return true;
}
//实现toString功能，方便进行测试使用
public String toString(){
return doubleLinkedList.toString();
}
public static void main(String[] args) {
}
}
3.4使用双向链表实现LRU算法复杂度分析
之前也提到过，双向链表同其他链表一样，存取时间复杂度都是O(n)，因为都是需要遍历链表才行，增删操作的时间复杂度都是O(1)。实现LRU的过程，如果是put操作，那么针对双向链表的操作只有删除第一个结点，然后添加尾结点，时间复杂度为O(1)，如果是get操作，需要先遍历查找到对应的结点，然后在进行增删操作，前者时间复杂度为O(n)，后者时间复杂度为O(1)，所以加起来还是O(n)。
后续为大家介绍一种实现LRU算法，并且时间复杂度为O(1)的实现方式。
LRU算法的原理与实现
网友评论