大厂之路的第二篇 双链表即LinkedList
上一篇，我们分析了ArrayList,我们分析了它的底层数据结构，也从源码角度分析了它的一些常用函数。那么，这一节，我们同样从源码的角度来看一下LinkedList的底层数据结构以及它的一些常用函数。
开篇我们就说到了LinkedList是一个双链表，所谓双链表就是说它的链条是有两个方向的，通过一个元素我们既可以找到它的上一个元素也可以找到它的下一个元素。如果遍历的话，我们既可以从链表的头部向后进行遍历，也可以从尾部向头部进行遍历。
ok，话不多说，直接进入到源码来验证这一点。
LinkedList的数据结构--双链表
进入到LinkedList的源码中，我们可以很容易的找到这样两个成员变量:transient Node<E> first;和transient Node<E> last;，它们的类型都是Node。那么，Node的数据结构又是怎样的呢？看下面：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node是LinkedList中的一个静态内部类，我们可以看到它有三个成员属性:item,next和prev。见名知意，我们可以很容易的猜想到这三个变量分别代表着什么：item用于存储当前节点的数据，next用于指向下一个节点的引用,而prev则指向上一个节点。我们暂且可以这么猜想，后面在LinkedList的常用函数的源码分析中，我们会去验证这一点。
ok，那么我们现在就进入到LinkedList的常用函数的源码分析中去吧！
同样，我们先来看 LinkedList的构造函数。
LinkedList的构造函数
LinkedList只有两个构造函数：一个是无参构造，另一个是传入一个集合的有参构造。
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
首先看这个无参构造，基本什么都没干，也就是说只是new出了一个LinkedList的实例，成员变量first和last都为null。
我们再来看后面这个构造函数:它的参数只有一个，一个集合，传入这个集合以后它做了哪些事情呢？我们到addAll这个函数里去看一看:
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
我们假设要添加的集合中有两个元素,然后我们来逐句分析addAll这个函数。
首先，检查index的合法性，显然是合法的。
然后，将传入的collection转化为一个数组。
接着，因为index和size都为0，所以就命中第一个if语句，从而使得succ和pred都为null。
随后，进入到foreach这个循环当中。因为我们集合中只有两个元素，所以这个循环只会走两次，我们每一次都来实际分析一下。
首先，先构造出一个Node节点
- 第一次时，因为
pred为null，所以会走if代码块，所以会将构造出来的第一个Node节点赋给first，然后再将其赋给pred，所以在下一次循环的时候pred不再为null。- 第二次的时候，因为
pred不再为null，所以命中else代码块，因为pred指向的是first引用，所以first的next指针就指向了新生成的Node节点。而新生成的Node节点在构造的时候就将其prev指针指向了pred也就是first节点。随后再将pred指向了最后这个节点。
最后，走出foreach循环以后，因为succ在此过程中，没有被赋值，所以仍然为null，也就命中了if语句，将last指向了最后生成的那个节点，并给size重新赋值。
这样，整个构造函数就走完了。
不难发现，走完整个构造，first,last,以及size都被赋值了，而且形成了一条双向链表。
下面，我们接着分析LinkedList的一些常用函数。
LinkedList add系列函数
1.向尾部添加元素
由于LinkedList既实现了List接口，又实现了Deque接口，而这两个接口又有不同的add函数,所以LinkedList有两个不同的add函数都实现了向尾部添加元素。而这两个函数唯一的区别就是有没有返回值。
public boolean add(E e) {
//实现自AbstractList
linkLast(e);
return true;
}
public void addLast(E e) {
//实现自Deque
linkLast(e);
}
所以，我们主要要看的就是linkLast这个函数。
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++;
}
首先，先拿到last的引用，然后在构造的Node节点的时候将其prev指针指向last节点，然后将新节点赋给last。
其次，判断当前链表的first是否为null，也就是链表是不是为null，如果是则将新构造的节点同时赋给first，否则将当前链表的last的next指针指向新构造的节点，其实就是一个重新连接链表的过程。
最后，给size加1.
2.向指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先，还是检查索引的合法性。
第二步，判断索引是不是等于size,如果是的话，那么操作其实就等同于向尾部添加元素，这个操作我们前面已经分析过了，就不再赘述。
第三步，如果index不等于size,那么就走linkBefore这个函数.
这个步骤可以划分成两步：
1.node(index)找到要往哪一个节点前面插入
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
由于LinkedList是双向链表，所以先判断index是处于链表的前半段还是后半段，如果是前半段则从头部开始遍历，反之从后尾部开始遍历，这样也提高了性能。
- 然后才是真正的插入操作:
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++;
}
第一步，找到要插入的节点的上一个节点，记为pred。
第二步，以要插入的元素为数据构造新节点，并将其prev指针指向pred节点。
第三步，将要插入节点的prev指针指向新构造的节点。
第四步，判断pred节点是否为空。如果为空则说明我们要插入的位置其实是链表头部，那么就将新节点赋给first，否则将pred节点的next指针指向我们新构造的节点。
最后，将size的值加1。
总的来说这个过程其实就是一个链表的断开以及重新连接的过程。感兴趣的朋友可以自己在纸上画出这个过程。
3.向头部添加元素
public void addFirst(E e) {
linkFirst(e);
}
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++;
}
这个其实就更简单了。
首先，找到first节点，并用一个临时变量f存储。
其次，以要插入的数据构造出一个新的节点，并将其next指针指向老的first节点。
然后，重新给first节点赋值，将新构造的节点赋给first。
最后，判断老的first节点是不是为null,如果是则说明之前的链表中没有数据：将last同样指向新生成的节点;否则将老的first节点的prev指针指向新插入的节点。
当然，最后要给size重新赋值。
3.向链表中插入集合
分为两种情况:1.向尾部插入集合 2.向指定位置插入集合。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
其实主要就是要看addAll这个函数，这个函数我们在分析LinkedList的构造函数的时候其实已经解析过了，所以我们也不再重复的去分析了。
按照增删改查的顺序，那么我们下面就分析remove系列函数
LinkedList remove系列函数
1.移除头部节点
移除头部节点的函数有两个:其实最终都是走了removeFirst这个函数
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
主要是分析unlinkFirst这个函数
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> 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;
}
这个函数的过程其实很好理解：
1.首先获取到老的first节点的下一个节点，也就是移除老的first后的新的first节点。
2.将老的first节点的element以及next都置为null帮助gc能够快速回收
3.将老的first节点的下一个节点赋给first，如果为空则说明整个链表在first移除之后就空了，所以也将last置为null;否则，将新的first节点的prev置为null，实际上就是彻底断开新的first节点与老的first节点之间的连接。
4.最后重新给size赋值，以及将移除节点对应的element返回。
2.移除尾部节点
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
可以看到，移除尾部节点跟移除头部节点其实是一个很相似的过程，移除头部节点的话其实是将头部节点的下一个节点置为头部节点，而移除尾部节点则是将尾部节点的前一个节点置为尾部节点。所以我们也不再去分析这个过程了。
3.移除指定位置的节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
这个过程可以分为两个步骤:
1.先找到要移除的那个节点:根据判断index属于链表的前半段还是后半段来决定是从头部开始遍历还是尾部开始遍历，找到对应的节点。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
2.然后走unlink函数:
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;
}
我们来重点分析一下这个unlink函数，其实这个函数跟linkBefore其实是差不了太多的，都是一个断链以及给各节点指针重新指定指向的过程。
1.获得要移除节点的上一个节点和下一个节点，即prev和next
2.判断prev是否为null,如果是则将next赋给first；否则将prev的next指针指向next,并将要移除的节点的prev指针置空。
3.判断next是否为null,如果是则将prev赋给last；否则将next的prev指针指向prev,并将要移除的节点的next指针置空。
4.最后将要移除节点的item置空，帮助gc快速回收。并重新给size赋值。
4.从头部开始遍历移除第一个数据等于指定元素的节点
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
这两个方法最终都是走的上面那个函数，而上面那个函数主要走的还是走的unlink函数。unlink函数我们上面已经详细分析过了，所以我们在这就不再分析了。
5.从尾部开始遍历移除第一个数据等于指定元素的节点
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
这里我们发现，同样这个函数的核心还是走unlink函数，这就是上面我们为什么要重点分析unlink函数的原因。
ok,remove系列函数我们就分析到这了。
LinkedList set系列函数
set系列函数比较可怜，就只有一个函数:
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
首先，还是验证index的合法性
其次，还是通过node函数来找到指定节点。
最后，替换指定节点的item,并将老的item返回。
set函数相对来说比较简单。
LinkedList get系列函数
get系列函数也比较简单，如果是查找头部和尾部函数速度也是相当的快。
如果是查找指定位置的元素数据，则同样是通过node函数来去遍历查找。
所以说，node函数也是LinkedList中的一个比较重要的函数.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
这三个函数比较简单，我们就不详细去展开了。
前面我们有提到过，LinkedList有实现Deque接口，而Deque接口有什么特性呢？
Deque是一个双端队列。我们知道队列的特性就是先进先出:从队尾进，从对头出。而双端队列则是可以从两端插入和从两端弹出的一种特殊队列。
因为 LinkedList实现了Deque接口，所以它同样实现了Deque所特有的一些方法:peek,peekFirst, peekLast,poll,pollFirst,pollLast,pop,push等一系列方法。这些方法其实是跟我们所分析的方法有重合的，所以在这里就不再去分析了。
好了，今天关于LinkedList的源码我们就分析到这里了。
下一篇，我们将对ArrayList和LinkedList做一个总结，分析两个各自的优缺点以及它们的异同和各自的适合的应用场景。
网友评论