重温：数据结构与算法 - 开篇
重温：数据结构与算法 - 复杂度分析(一)
重温：数据结构与算法 - 复杂度分析(二)
重温：数据结构与算法 - 数组
前章提到链表也属于线性表结构。
可想而知，链表在内存中存储的形式也是类似于一条直线进行延伸的。
从内存图中可看出，链表数据结构的内存分配情况并不连续，作为线性表结构的关键就在于每个数据结点都是由 数据块 和 指针块 组成。
- 数据块 ： 用于存储真正的数据
- 指针块 ： 用于存储下一个结点的内存首地址
例如上图Node1结点中的指针块存储的就是Node2的首地址1003（这里假设一个结点仅占用1个字节）
单向链表
单链表的方向是固定的，指针始终指向下一个结点，当没有结点时，最后一个结点称之尾结点，它的指针块会存储null；而第一个结点称之首结点，只要知道首结点，就可以获取到该链表中任意结点数据。
链表的插入与删除
与数组一样，链表也支持插入、删除、查询操作。我们知道数组的插入、删除操作需要大量的数据迁移工作，时间复杂度为：O(n)。而在链表中插入和删除结点就非常简单。
插入操作
如果需要在Node1和Node2中间插入Node8结点，只需要两步：
- ①修改Node1的指针块存储Node8的首地址；
- ②再让Node8的指针块存储原Node1指针块中取出的地址。
通过上面操作，在没有进行位移数据的情况下， 插入操作的时间复杂度为：O(1)。
删除操作
同理，删除Node2结点也只需两步：
- ①修改Node1的指针块存储Node3的首地址；
- ②清空Node2的指针块。
So. 删除操作的时间复杂度也是：O(1)。
查询操作
有利就有弊，与数组恰恰相反，链表因为不是连续的内存块，就无法通过寻址公式计算出每个结点的首地址，所以查询一个结点就必须从链表的首结点挨个查询下去，直到找到为止，即时间复杂度为：O(n)。
循环链表
循环列表是一种特殊单向链表，它的尾结点指针块不再存储null，而是指向首结点的首地址。
这种链表的优点在处理环型数据时更加合适，比如著名的：约瑟夫问题。
约瑟夫环
N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个人时游戏结束，求人员被杀掉的顺序。
例如：N=6，M=5，被杀掉的顺序是：5 -> 4 -> 6 -> 2 -> 3 , 最终幸运者： 1。
首先，创建一个Node类，该类的数据块存储人员编号，next指向下一个人员结点；
class Node {
public int data; // 人员编号
public Node next; // 下一个人结点
public Node(int data) {
this.data = data;
}
}
再创建人员，并组成环；
// 1、创建结点，并组成环
Node firstNode = new Node(1);
Node preNode = firstNode;
for (int i = 1; i < n; i++) {
Node temp = new Node(i + 1);
preNode.next = temp;
preNode = temp;
}
preNode.next = firstNode;
最后开始报数，只要报到m-1的人，它的下一位就出局，代码如下：
// 2、开始报数
Node node = firstNode;
while (node != node.next) {
for (int i = 1; i < m-1; i++) {
node = node.next;
}
//当报数到m-1时，下一个人员就是出局者
Node outNode = node.next;
System.out.println("出局：" + outNode.data);
//报数m-1的人指向 m+1人员
node.next = outNode.next;
outNode.next = null;
//准备下一轮
node = node.next;
}
System.out.println("幸运者：" + node.data);
输出：
出局：5
出局：4
出局：6
出局：2
出局：3
幸运者：1
时间复杂度：O(m * n)
双向链表
和单向链表不同，双向链表有两个指针块，一个和单向链表一样指向下一个结点的next指针，一个是指向上一个结点的pre指针。
了解单向链表的数据结构后，双向链表就不难理解，与单项链表相比，双向链表的优缺点如下：
缺点
首先，由于每个结点比单向链表都多一个指针块，内存占用肯定大于单向链表。
优点
前驱指针的存在，当需要获取前结点需求时，时间复杂度就仅仅为O(1)，而单向链表就不得不重新从首结点遍历，时间复杂度为O(n)，这种设计我们称之为：用空间换时间。
关于实际情况中的双链表操作的优点
- 之前提到单向链表的删除操作时间复杂度是O(1)，但实际开发中的删除需求可能会是删除某个结点（Node对象）。这时，单链表就无法将上结点和下结点直接连接起来（没有前驱指针），就必须重头遍历链表找到上结点，单向链表删除操作时间复杂度就变为：O(n)；而双向链表就不存在这个问题，依旧可以保持高效的时间复杂度：O(1)。
同理，当要插入结点在某个结点前时，单向链表依旧无法获取上结点进行连接，所以插入操作时间复杂度变为：O(n)；而双向链表依旧为：O(1)。
如果链表数据是有序的，在查询上虽然两者时间复杂度都是O(n)，但实际上双向链表可以支持更快查询。双向链表可以把每次查询到的结点记录下来，当下次查询值大于当前就可以继续向后查询，反之向前查询，从而节省大部分时间。
LinkedList底层就是通过双向链表实现。
双向循环链表
跟循环链表一样，把双向链表的首尾相连起来，将双向和循环的优缺点结合起来就是：双向循环链表
链表 VS 数组
时间复杂度对比
- 数组 插入 O(n)
- 链表 插入 O(1)
- 数组 删除 O(n)
- 链表 删除 O(1)
- 数组 查询 O(1)
- 链表 查询 O(n)
链表和数组的对比不能局限于时间复杂度，在特定的场景下选择适合的数据结构，才能编写出高效的算法。
数组的缺点是内存大小连续且固定，比如在内存仅剩100K，但并不连续，那么在创建一个100K的数组时就会导致“内存不足（out of memory）”，而链表就可以正常创建。
反过来说，正因为数组是连续的内存区域，有利于CPU的缓存机制，可以提前预读到CPU中，提高访问效率；而链表中的数据由于都是单内存区，就无法提前预读。并且如果过多的对链表结点进行插入、删除操作，可能会导致JVM频繁的GC，产生更多的内存碎片。
LRU淘汰算法
LRU淘汰算法属于缓存策略一种，一般缓存策略分为三种：
- 1、先进先出策略 FIFO
- 2、最少使用策略 LFU
- 3、最近最少使用策略 LRU
了解过链表后，可以很容易的使用双向链表实现一个最近最少使用策略的LRU缓存机制，步奏如下：
- 我们将需缓存的数据倒序存入链表中（先进的在末尾）
- 当有新数据到来时，遍历缓存数据：
- 已在缓存中： 就将该结点在原先位置删除，再插入到首结点
- 不在缓存中：
- 缓存大小充足，就将该数据插入首结点
- 缓存大小不充足，删除尾结点，再插入首结点
这样设计的缓存策略，由于每次存储数据都要检查结点是否存在，所以时间复杂度为O(n)。
以下为缓存Data类型数据的LRU淘汰算法实现：
// Data 数据类
class Data {
public String id;
public int data;
public Data(String id, int data) {
this.id = id;
this.data = data;
}
public void print() {
System.out.print("{id : '" + id + "' , data : " + data + "}");
}
}
双向链表：
// 结点类
class Node {
public Node pre;
public Data data;
public Node next;
public Node(Data data) {
this.data = data;
}
}
LruCache实现类：
// Lru缓存策略容器
class LruCache {
private Node first;
private int size;
private int maxSize;
public LruCache(int maxSize) {
this.maxSize = maxSize;
}
public void add(Data data) {
//校验数据是否合法
if (data.id == null) return;
//查询结点是否已经缓存
Node tempNode = first;
Node last = null;
while (tempNode != null) {
if (tempNode.data.id.equals(data.id)) {
if (tempNode.pre != null) {
tempNode.pre.next = tempNode.next;
}
//已缓存，移动到头部位置
tempNode.next = first;
first.pre = tempNode;
first = tempNode;
first.pre = null;
return;
} else {
//未缓存，记录尾结点
if (tempNode.next != null) {
tempNode = tempNode.next;
} else {
last = tempNode;
break;
}
}
}
//超过初始化大小，删除尾结点
if (size + 1 > maxSize && last != null) {
last.pre.next = null;
size--;
}
//添加新结点到头部
Node newNode = new Node(data);
newNode.pre = null;
newNode.next = first;
if (first != null) {
first.pre = newNode;
}
first = newNode;
size++;
}
public Data get(String id) {
Node tempNode = first;
while (tempNode != null) {
if (tempNode.data.id.equals(id)) {
return tempNode.data;
}
tempNode = tempNode.next;
}
return null;
}
public void print() {
Node tempNode = first;
while (tempNode != null) {
System.out.print(tempNode.data.data + "\t");
tempNode = tempNode.next;
}
System.out.println();
}
}
测试：创建一个大小为3的缓存空间，并存入一组数据，查看存储情况
LruCache cache = new LruCache(3);
Data data1 = new Data("1", 111);
Data data2 = new Data("2", 222);
Data data3 = new Data("3", 333);
Data data4 = new Data("4", 444);
cache.add(data1);
cache.add(data2);
cache.add(data3);
// 数据空间已满，添加data4会移除data1
cache.add(data4);
// 重复添加data2，data2将移至首结点
cache.add(data2);
cache.print();
Data data = cache.get("3");
data.print();
输出：
222 444 333
{id : '3' , data : 333}