## 双向链表
* 之前的单向链表只能通过 Node 中 next 属性从头遍历链表，完成搜索
* 双向链表中的 Node 增加 prev 属性，指向该节点上一个节点
* 双向链表查找元素可以从 first 或 last 两个方向开始查找，故而可以提高效率
* Java 官方 LinkedList 就是双向链表
## 实现双向链表
相比单向链表，双向链表需要重写查找节点、添加节点、删除节点、清空链表四个方法
### 1. 属性
增加 last 指向尾节点，Node 中增加 prev 指向前一个节点
```java
public class LinkedList {
// 当前链表元素的数量
private int size;
// 链表的头节点
private Node first;
// 链表的尾节点
private Node last;
// 未查找到元素下标的返回值
private static final int MINUS_ONE = -1;
// 节点内部类
private static class Node {
// 前驱节点
Node prev;
// 后继节点
Node next;
// 存储的数据元素
E element;
// 构造器
Node(Node prev, E element, Node next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}
```
### 2. 构造器
```java
// 构造器
LinkedList() {
first = null;
last = null;
size = 0;
}
```
### 3. 查找节点
判断要查找的位置是在链表前半段还是后半段，选择**从前向后**还是**从后向前**查找
```java
// 查找节点
private Node getNode(int index) {
checkRange(index);
if(index < (size>>1)) {
// 目标index小于长度的中间值，从前往后找
Node node = first;
for(int i=0;i node = last;
for(int i=size-1;i>index;i--) {
node = node.prev;
}
return node;
}
}
```
### 4. 添加元素
* 向链表**尾部**追加元素
* 空链表
* 非空链表
* 向**非尾部**插入元素
* 插入到第一个位置
* 其他位置
```java
// 添加元素
public void add(int index,E ele) {
checkRangeForAdd(index);
// 向最后添加元素
if(index==size) {
Node oldLast = last;
last = new Node<>(oldLast,ele,null);
// 如果链表是空的，添加的元素是第一个元素
if(oldLast==null) {
first = last;
}else {
oldLast.next = last;
}
}else {
// 插入位置原节点成为新节点的后继
Node next = getNode(index);
// 插入位置原节点的前驱成为新节点的前驱
Node prev = next.prev;
// 创建新节点
Node node = new Node<>(prev,ele,next);
// 设置 next 的 prev
next.prev = node;
// 如果插入到第一个位置，也就是说 index==0
if(prev==null) {
first = node;
}else {
prev.next = node;
}
}
size ++;
}
// 向尾部添加元素
public void add(E ele) {
add(size,ele);
}
```
### 5. 删除元素
删除元素，将前驱的 next 指向后继，后继的 prev 指向前驱，如果是头节点 (prev==null) 或尾节点 (next==null) 需要特殊处理
```java
// 删除元素
public E remove(int index) {
checkRange(index);
Node node = getNode(index);
Node prev = node.prev;
Node next = node.next;
if(prev==null) {
first = next;
}else {
prev.next = next;
}
if(next==null) {
last = prev;
}else {
next.prev = prev;
}
size --;
return node.element;
}
```
### 6. 清空链表
只需要把 first 和 last 置空，size 置 0 即可，JDK 源码中还依次置空了 Node，因为迭代器可能引用着其中某个节点，导致其他节点被简介引用，无法被回收
```java
// 清空链表
public void clear() {
first = null;
last = null;
size = 0;
}
```
## 双向链表 vs 动态数组
* 动态数组：开辟、销毁内存的次数少，可能造成内存空间浪费
* 双向链表：开辟、销毁内存的次数多，但不会有内存空间浪费
### 如和选择两种数据结构
* 频繁尾部添加、删除：二者皆可
* 频繁头部添加、删除：双向链表
* 频繁任意位置添加、删除：双向链表
* 频繁查询（随机访问）：动态数组
## 参考
* [恋上数据结构与算法（第一季）](https://ke.qq.com/course/385223)
* [小码哥《恋上数据结构与算法》笔记（三）：双向链表](https://juejin.im/post/5df9c8256fb9a016214cd3de)
数据结构 | 双向链表 LinkedList
