双向链表的插入及删除图解

第一步：首先找到插入位置，节点 s 将插入到节点 p 之前

第二步：将节点 s 的前驱指向节点 p 的前驱，即 s->prior = p->prior

第三步：将节点 p 的前驱的后继指向节点 s 即 p->prior->next = s

第四步：将节点 s 的后继指向节点 p 即 s->next = p

第五步：将节点 p 的前驱指向节点 s 即 p->prior = s

第一步：找到即将被删除的节点 p

第二步：将 p 的前驱的后继指向 p 的后继，即 p->prior->next = p->next

第三步：将 p 的后继的前驱指向 p 的前驱，即 p->next->prior = p->prior

第四步：删除节点 p 即 delete p

顾名思义，双向链表跟单链表和循环列表最大的差别，就是同时拥有前驱指针和后驱指针，基于这一个特性，查询某结点的前一个结点，时间复杂度可以达到O(1)，非常高效。双向链表的存取时间复杂度是O(n)，增删时间复杂度为O(1)，跟其他链表没啥区别。

双向链表表示意图：

所以双向链表的结点定义如下：

class Node{

Object data//元素值

Node pre//前驱指针

Node next//后驱指针

}

对于双向链表做增删 *** 作，有一定的顺序要求，顺序不对，很可能会造成空指针异常。

双向链表增加结点示意图：

双向链表删除结点示意图：

将不常被访问的数据进行淘汰，来保证有限空间的使用，在计算机cache当中广为应用，因为cache的大小有限，为了尽可能多的命中热数据，就可以将冷数据进行淘汰，充分利用内存空间。

-》put进数据时，将其放于链尾，因为链尾的数据最不容易被淘汰，并且插入之前需要判断一下空间是否已满，如果满了，就需要将链头的数据淘汰掉。

-》get数据时，如果未在cache中命中，就返回-1，来模拟cache未命中的现象，如果命中，将该数据从当前位置删除，并移至链尾。

之前也提到过，双向链表同其他链表一样，存取时间复杂度都是O(n)，因为都是需要遍历链表才行，增删 *** 作的时间复杂度都是O(1)。实现LRU的过程，如果是put *** 作，那么针对双向链表的 *** 作只有删除第一个结点，然后添加尾结点，时间复杂度为O(1)，如果是get *** 作，需要先遍历查找到对应的结点，然后在进行增删 *** 作，前者时间复杂度为O(n)，后者时间复杂度为O(1)，所以加起来还是O(n)。

后续为大家介绍一种实现LRU算法，并且时间复杂度为O(1)的实现方式。

LRU算法的原理与实现

---