美团技术拷问：LinkedList 源码看过吗？
作者缄默沉静王二泉源公众号缄默沉静王二
一、LinkedList 的剖白
各人好，我是 LinkedList，和 ArrayList 是同门师兄弟，但我俩练的内功却完全不同。师兄练的是动态数组，我练的是链表。
问各人一个题目，知道我为什么要练链表这门内功吗？
举个例子来讲吧，假如你们手头要管理一推票据，大概有一张，也大概有一亿张。
该怎么办呢？
申请一个 10G 的大数组等着？那万一票据只有 100 张呢？
申请一个默认巨细的数组，随着数据量的增大扩容？要知道扩容是必要重新复制数组的，很耗时间。
关键是，数组还有一个毛病就是，假如现在有 500 万张票据，现在要从中间删除一个票据，就必要把 250 万张票据往前移动一格。
遇到这种情况的时候，我师兄几乎感情崩溃，难受的要命。师父不忍心看到师兄这样痛楚，于是打我进入师门那一天，就强迫我练链表这门内功，一开始我很不理解，畏惧师父偏爱，不把师门最厉害的内功教我。
直到有一天，我亲眼目睹师兄差点因为移动数据而走火入魔，我才明白师父的良苦用心。从此以后，我苦练“链表”这门内功，取得了显著的进步，师父和师兄都夸我有天赋。
链表这门内功大致分为三个条理：
[*]第一层叫做“单向链表”，我只有一个后指针，指向下一个数据；
[*]第二层叫做“双向链表”，我有两个指针，后指针指向下一个数据，前指针指向上一个数据。
[*]第三层叫做“二叉树”，把后指针去掉，换成左右指针。
但我现在的功力还达不到第三层，不外师父说我有这个潜力，练成神功是早晚的事。
二、LinkedList 的内功心法
好了，经过我这么样的一个剖白后，各人对我应该已经不陌生了。那么接下来，我给各人展示一下我的内功心法。
我的内功心法紧张是一个私有的静态内部类，叫 Node，也就是节点。
private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; }}它由三部分组成：
[*]节点上的元素
[*]下一个节点
[*]上一个节点
我画幅图给你们展示下吧。
https://p3.toutiaoimg.com/large/pgc-image/14334aff0ae341d3a79b59ce4a75051e
[*]对于第一个节点来说，prev 为 null；
[*]对于最后一个节点来说，next 为 null；
[*]别的的节点呢，prev 指向前一个，next 指向后一个。
我的内功心法就这么简单，着实我早已经牢记在心了。但师父叮嘱我，每天早上醒来的时候，每天晚上睡觉的时候，一定要默默地背诵一遍。虽然我有些厌烦，但我对师父的教导从来都是百依百顺。
03、LinkedList 的招式
和师兄 ArrayList 一样，我的招式也无外乎“增编削查”这 4 种。在此之前，我们都必须得初始化。
LinkedList list = new LinkedList();师兄在初始化的时候，默认巨细为 10，也可以指定巨细，依据要存储的元素数量来。我就不必要。
1）招式一：增
可以调用 add 方法添加元素：
list.add("缄默沉静王二");list.add("缄默沉静王三");list.add("缄默沉静王四");add 方法内部着实调用的是 linkLast 方法：
public boolean add(E e) { linkLast(e); return true;}linkLast，顾名思义，就是在链表的尾部链接：
void linkLast(E e) { final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}
[*]添加第一个元素的时候，first 和 last 都为 null。
[*]然后新建一个节点 newNode，它的 prev 和 next 也为 null。
[*]然后把 last 和 first 都赋值为 newNode。
此时还不能称之为链表，因为前后节点都是断裂的。
https://p26.toutiaoimg.com/large/pgc-image/9556d97f04464607b0e0ac2eaa7dc81a
[*]添加第二个元素的时候，first 和 last 都指向的是第一个节点。
[*]然后新建一个节点 newNode，它的 prev 指向的是第一个节点，next 为 null。
[*]然后把第一个节点的 next 赋值为 newNode。
此时的链表还不完整。
https://p3.toutiaoimg.com/large/pgc-image/0b61be4eaf1941019c773363738645c9
[*]添加第三个元素的时候，first 指向的是第一个节点，last 指向的是最后一个节点。
[*]然后新建一个节点 newNode，它的 prev 指向的是第二个节点，next 为 null。
[*]然后把第二个节点的 next 赋值为 newNode。
此时的链表已经完整了。
https://p3.toutiaoimg.com/large/pgc-image/53eb8c35a690475bbd7d10da29a2f440
我这个增的招式，还可以演化成另外两个：
[*]addFirst() 方法将元素添加到第一位；
[*]addLast() 方法将元素添加到末尾。
addFirst 内部着实调用的是 linkFirst：
public void addFirst(E e) { linkFirst(e);}linkFirst 负责把新的节点设为 first，并将新的 first 的 next 更新为之前的 first。
private void linkFirst(E e) { final Node f = first; final Node newNode = new Node(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++;}addLast 的内核着实和 addFirst 差不多，就交给各人自行理解了。
2）招式二：删
我这个删的招式还挺多的：
[*]remove()：删除第一个节点
[*]remove(int)：删除指定位置的节点
[*]remove(Object)：删除指定元素的节点
[*]removeFirst()：删除第一个节点
[*]removeLast()：删除最后一个节点
remove 内部调用的是 removeFirst，以是这两个招式的功效一样。
remove(int) 内部着实调用的是 unlink 方法。
public E remove(int index) { checkElementIndex(index); return unlink(node(index));}unlink 方法着实很好理解，就是更新当前节点的 next 和 prev，然后把当前节点上的元素设为 null。
E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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;}remove(Object) 内部也调用了 unlink 方法，只不外在此之前要先找到元素所在的节点：
public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false;}这内部就分为两种，一种是元素为 null 的时候，必须使用 == 来判定；一种是元素为非 null 的时候，要使用 equals 来判定。equals 是不能用来判 null 的，会抛出 NPE 错误。
removeFirst 内部调用的是 unlinkFirst 方法：
public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);}unlinkFirst 负责的就是把第一个节点毁尸灭迹，而且捎带把后一个节点的 prev 设为 null。
private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element;}3）招式三：改
可以调用 set() 方法来更新元素：
list.set(0, "缄默沉静王五");来看一下 set() 方法：
public E set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal;}首先对指定的下标进行检查，看是否越界；然后根据下标查找原有的节点：
Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}size >> 1：也就是右移一位，相称于除以 2。对于计算机来说，移位比除法运算服从更高，因为数据在计算机内部都是二进制存储的。
换句话说，node 方法会对下标进行一个初步判定，如果靠近前半截，就从下标 0 开始遍历；如果靠近后半截，就从末尾开始遍历。
找到指定下标的节点就简单了，直接把原有节点的元素替换成新的节点就 OK 了，prev 和 next 都不用改动。
4）招式四：查
我这个查的招式可以分为两种：
[*]indexOf(Object)：查找某个元素所在的位置
[*]get(int)：查找某个位置上的元素
indexOf 的内部分为两种，一种是元素为 null 的时候，必须使用 == 来判定；一种是元素为非 null 的时候，要使用 equals 来判定。因为 equals 是不能用来判 null 的，会抛出 NPE 错误。
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1;}get 方法的内核着实照旧 node 方法，这个之前已经说明过了，这里略过。
public E get(int index) { checkElementIndex(index); return node(index).item;}着实，查这个招式还可以演化为其他的一些，比如说：
[*]getFirst() 方法用于获取第一个元素；
[*]getLast() 方法用于获取最后一个元素；
[*]poll() 和 pollFirst() 方法用于删除并返回第一个元素（两个方法尽管名字不同，但方法体是完全相同的）；
[*]pollLast() 方法用于删除并返回最后一个元素；
[*]peekFirst() 方法用于返回但不删除第一个元素。
四、LinkedList 的挑战
说句着实话，我不是很喜欢和师兄 ArrayList 拿来比力，因为我们各自修炼的内功不同，没有孰高孰低。
虽然师兄经常喊我一声师弟，但我们之间着实挺和谐的。但我知道，在外人眼里，同门师兄弟，总要一较高下的。
比如说，我们俩在增编削查时候的时间复杂度。
也许这就是命运吧，从我进入师门的那天起，这种争论就不绝没有停息过。
无论外人怎么看待我们，在我眼里，师兄永久都是一哥，我敬重他，他也乐意掩护我。
页:
[1]