双向链表和单向链表不同的是它有两个指针，一个指向前一个节点，一个指向后一个节点。
双向链表的节点类如下，比单向链表多了一个 pre 变量。
private class DoubleNode {
int val;// 节点中存储的数据。
DoubleNode pre;// 指向上一个节点的指针。
DoubleNode next;// 指向下一个节点的指针。
public DoubleNode(int val, DoubleNode pre, DoubleNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
双向链表的插入
双向链表的插入也分 3 种情况，分别是在头部插入，尾部插入和中间插入，原理都一样，我们画个图分析下在中间插入的步骤。
来看下代码：
// 在 node 节点之前插入一个新节点。
void addBefore(int val, DoubleNode node) {
DoubleNode pre = node.pre;
DoubleNode newNode = new DoubleNode(val, pre, node);
node.pre = newNode;
if (pre == null)// 在头节点之前插入。
head = newNode;
else
pre.next = newNode;
size++;
}
双向链表的删除
删除指定节点需要找到待删除的前一个和后一个节点，我们以删除中间节点画个图来看下删除步骤。
来看下最终代码：
private DoubleNode head;// 头节点。
private DoubleNode tail;// 尾节点。
private int size;// 链表的长度。
// 头部添加
private void addFirst(int val) {
DoubleNode oldNode = head;
DoubleNode newNode = new DoubleNode(val, null, oldNode);// 创建新的头节点。
head = newNode;// 更新头节点。
if (oldNode == null)// 如果之前链表为空，让 tail 也指向新的节点。
tail = newNode;
else
oldNode.pre = newNode;// 如果之前链表不为空，让之前链表的头节点的 pre 指针指向新节点。
size++;
}
// 尾部添加
private void addLast(int val) {
DoubleNode oldNode = tail;
DoubleNode newNode = new DoubleNode(val, oldNode, null);// 创建尾节点。
tail = newNode;// 更新尾节点。
if (oldNode == null)// 如果之前链表为空，让 head 也指向新的节点。
head = newNode;
else
oldNode.next = newNode;
size++;
}
// 在指定位置添加节点。
public void add(int index, int val) {
if (index < 0 || index > size)
throw new IllegalStateException("越界了……");
if (index == size)// 添加到尾部。
addLast(val);
else
addBefore(val, findNode(index));
}
// 查找节点。
DoubleNode findNode(int index) {
if (index < 0 || index >= size)
throw new IllegalStateException("越界了……");
if (index < (size >> 1)) {// 从前往后找。
DoubleNode x = head;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {// 从后往前找。
DoubleNode x = tail;
for (int i = size - 1; i > index; i--)
x = x.pre;
return x;
}
}
// 在 node 节点之前插入一个新节点。
void addBefore(int val, DoubleNode node) {
DoubleNode pre = node.pre;
DoubleNode newNode = new DoubleNode(val, pre, node);
node.pre = newNode;
if (pre == null)// 在头节点之前插入。
head = newNode;
else
pre.next = newNode;
size++;
}
// 删除头部节点
private int removeFirst() {
if (head == null)
throw new IllegalStateException("链表为空……");
int val = head.val;// 获取头部节点的值。
DoubleNode next = head.next;
head.val = -1;// 如果存储的是对象，这里要清理掉。
head.next = null; // gc
head = next;// 更新头部节点
if (next == null)// 全部删除了，让 tail 指向空。
tail = null;
else
head.pre = null;// 头节点的前一个指针指向空。
size--;
return val;
}
// 删除尾部节点
public int removeLast() {
if (tail == null)
throw new IllegalStateException("链表为空……");
int val = tail.val;// 获取尾部节点的值。
DoubleNode pre = tail.pre;// 尾部节点的前一个节点。
tail.val = -1;// 如果存储的是对象，这里要清理掉。
tail.pre = null; // GC
tail = pre;// 更新尾部节点。
if (pre == null)
head = null;// 链表为空，让 head 指向空。
else
tail.next = null;// 尾部节点的 next 指针指向空。
size--;
return val;
}
// 删除指定的节点。
int remove(DoubleNode x) {
int val = x.val;
DoubleNode next = x.next;
DoubleNode pre = x.pre;
if (pre == null) {// 删除的是头节点。
head = next;
} else {// 删除的不是头节点。
pre.next = next;
x.pre = null;
}
if (next == null) {// 删除的是尾节点。
tail = pre;
} else {// 删除的不是尾节点。
next.pre = pre;
x.next = null;
}
x.val = -1;// 清理数据。
size--;
return val;
}
// 获取头部节点值。
public int getFirst() {
if (head == null)
throw new NoSuchElementException();
return head.val;
}
// 获取尾部节点值。
public int getLast() {
if (tail == null)
throw new NoSuchElementException();
return tail.val;
}
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
