大话数据结构之链表（二）
上一篇《链表概念篇》中， 主要给小伙伴们讲述了什么是链表？ 为什么链表是线性结构？ 链表的操作是什么？ 链表操作的过程与原理是什么？相信认真读过的小伙伴们已经明白的掌握了链表的相关概念。 那么下面来回顾一下
1. 什么是链表？
链表是一种链式的数据结构， 两个节点之间使用链式连接， 比如 单链表的A的next是B， B的next是C, C的next是D，可以标识为A -> B -> C -> D。 双链表在单链表的基础上添加了前指向pre, 如A的next是B，则必然B的pre是A， 理解为A是B的前驱， B是A的后继。
2. 链表的操作流程
一般常用的操作也就是我们熟悉的增删改查。其中查和改很简单， 与数组不同的是，我们是通过头节点，不断的遍历相邻的下个节点，直到找到你想要的节点元素；既然找到了，那么修改节点的值就简单的不能再简单了。链表中稍微复杂些的操作就是增添与删除节点。 上一篇中我也给小伙伴们列了相应的步骤：
1） 首先找到相关的节点，即目标节点的前驱与后记
2） 断开原有的链接关系
3） 建立新的链接关系
如果还对链表的概念不清楚，建议回头查看上一篇《链表 概念篇》
链表在数据结构中算是比较重要的结构之一，希望大家真的把与链表相关的知识弄明白。 那么接下来，我们讲解一下LinkedList的源码。其实明白了常用操作的原理， 还是很好理解的。
LinkedList源码解读
首先，我们来看一下常用的操作
image.png
从上述可以看出，提供的常用接口，无非就是CRUD或者CRUD的变种； 那么如果你掌握了CRUD，至于他们的变种就可以一通百通了。如addFirst , addLast, add, addAll等都属于增加吧。
下面主要来说一下链表的增删改查。
1. 先来看一下最简单的 查
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
代码很少，我们不妨来看一下最核心的地方
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
for循环，但不是我们常用的for循环。 默认初始化是x = first, 从第一个节点开始； x =x.next, 不断查找下一个节点； 判断节点的值是否是我们传入的值，如果是，那么恭喜你，找到了！同样的步骤，我们可以返回在整个链表的位置index, 也可以返回找到的节点， 当前还可以返回目标节点的前驱结点和后继结点。 这也就满足了我们的查找与增删操作时需要的目标节点的前驱和后继了吧。
当然，如果你经常使用数据库Cursor遍历的话，你会发现真的很像。
2. 顺带着，我们看一下修改的操作
关于修改，我真的不想说了。当我们成功找到了想要修改的节点后，你还不会修改节点的值么？
3. 链表的核心操作之插入一个元素
链表提供的插入Api主要有两个， 那就是头插法和尾插法。 当然还有一些衍生的操作，不过掌握了这两种主要的核心方法，其他一搭眼，你就明白为什么了。
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
头插法，即将节点插入到头部。我们来想一下这个过程，现在已知一个链表，如下
A -> B -> C -> D
可以看出，A是first,也即头节点；如果我们想在头部插入一个节点E， 那么按照我们总结的步骤
E->A->B->C->D
- 目标节点是头节点，因此没有前驱，有一个后继A，是当前的first
- 插入头部或尾部，不涉及断链问题
- 建立新链接， E的next指向A， 如果是双链表的话，当然A的pre也指向E
再看代码
- 先找到了相关节点first， 保存起来
final Node<E> f = first;
- 根据数据，生成新的目标节点;新节点的next是f也就是first
- 插入后，新节点就是first了
first = newNode;
- 如果头节点是空，那么插入后，就只有一个节点newNode了，因此既是头，也是尾。如果头节点不是空，这里A的前驱指向newNode，前面在newNode创建时，已经指定了后继是f。 这时候，一条新的链就创建起来了。
从以上来看， LinkedList是个双链表，因为存在pre指针。双链表比单链表的高校在于： 单链表是单链，只能从头到尾找；双链表是双链表，既可以从头向后找，也可以从尾向前找。
再来看尾插法， 明白了头插法，那么尾插法就手到擒来了，你只要画一个图，就可以照着写出来。还是那个例子，ABCD插入E，这次是从尾部，那么
A -> B -> C->D
A->B->C->D->E
根据头插法的分析，涉及的前驱只有D， 没有后继。
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
与头插法的实现几乎是相同的，这里不做解释了。
头插法和尾插法相对比较简单， 因为只涉及一个元素前驱或后继， 那么来看一下中间插入是怎么做的？ 相比于以上两种，只是多了一层前驱或后继的断开与重链。
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
上述代码是在succ节点前面插入一个元素为e的新节点，linkAfter实现与之相似，这里重点说一下这个， 你可以试着自己写一下在后面插入的实现
当前的状况： succ.pre -> succ -> succ.next
插入后： succ.pre -> E -> succ -> succ.next
我们来分析一下：
- 还是找受影响的目标节点E的前驱与后继，分别是succ.pre以及succ
- 看图，插入E，我们需要断开succ.pre与succ的链；因为插入后，succ的前驱是E了，而不是以前的succ.pre
- 重新建立链， succ.pre与E之间， E与succ之间
根据以上分析，我们来看源码
1.找到并保存影响节点 succ.pre
final Node<E> pred = succ.prev;
2. 断开并重建succ与E的链
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
这里你就奇怪了，为啥断开和建链是在一起的呢？ 我们断开是通过设置next或pre为null来实现的，便于理解； 但是之后会在next或pre上添加新的关系， 这里把两个过程合并了。比如
我们应该先断开pre与succ的链，那么我们应该这么写
pred.next = null; // 断开前驱的后继关系
succ.pre = null; // 断开succ的前驱关系
然后建立新的链
succ.pre = E; // E就是newNode
E.next = succ;
E的链的建立是在构造中，new Node(前驱， 数据， 后继)。别说没有链到succ哈！
接下来我们把以下代码合并为一个
succ.pre = null;
succ.pre = E;
我们直接合并成
succ.pre = E;
到这里，你明白了吗？
好了，插入的解析到此结束了；接下来解析删除的代码。其实明白了插入，删除很容易理解，因为都是断链和建链的过程
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
还是先模拟一下过程，已知一个链表ABCD, 此时我想删除C， 那么过程是：
A - B - C - D
A - B - D
- 首先找到目标C以受影响的前驱B与后继D，并保存
- 断开C与B， C与D的关系
- 重新建立B与D的关系
看源码
pre.next = next;
可能比较绕， pre就是B， next就是D， 此时是删除C后，让B的后继指向D。同时，
next.prev = prev;
D的前驱指向B。 链的断开与建立就有了。
···
x.pre = null;
x.next = null;
···
这就断开C的所有链了，也就是说C是一个独立节点了。
本篇的意义，就是在理解理论的前提下，通过看系统的实现来验证理论，并加深印象，以及知道理论是如何用代码实现的。整个过程其实理解了理论后，还是很容易看懂的。
我一直在强调一个流程，至于断开与重建链的过程，并不一定是谁先谁后的；只是这样解释比较好理解；在代码中我们也看到了，断开与重建的过程是同时进行的，当然这要建立在你理解整个过程之后，因此建议你自己手写一遍这个过程，才能真正明白它究竟是怎么做的。
好了，通过这两篇文章，相信你已经理解了链表这种结构了。如果你觉得本文对你有帮助，不妨点个赞，谢谢！
