上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理，但是这种集合类型虽然可以随机访问数据，但是如果需要删除中间的元素就需要移动一半的元素的位置，效率低下。并且它内部是用数组来实现的，数组要求连续的存储空间，当数据量大的时候就极耗内存。本篇我们介绍使用链表实现的集合LinkedList，这种类型不需要连续的存储空间，删除数据方便，但是不支持随机访问并且查找效率低下，几乎是ArrayList的对立面。我们将从以下方面介绍此类型：
- 超接口和超类的基本方法及实现
- 内部组成细节
- add方法的源码解析
- remove方法的源码解析
- 低效的get方法
- LinkedList的应用场景
一、了解LinkedList的超接口
我们首先看到LinkedList实现了接口Deque，而这个接口又实现了Queue接口，那我们就从Queue接口看起。
public interface Queue<E> extends Collection<E> {
boolean add(E e);//添加元素
boolean offer(E e);//添加元素
E remove();//删除元素
E poll();//删除元素
E element();//返回头部元素
E peek();//返回头部元素
}
我们可以看到该接口中声明的每个操作都是由两个方法对应，那这两个方法之间有什么不同呢？调用两种方法的任意一种都是可以完成我们所需要的大部分功能，但是当处于特殊情况下，两者处理方式不一样。比如：当链表为空时，调用remove就会抛异常，而poll则是返回特殊值null，当链表满了，调用add就会抛异常，而offer就会false。（我们的LinkedList 是没有长度限制的，但是对于其他实现Queue的类可能会有长度限制，及可能会满员）。
看完了Queue我们看看看他的子接口Deque（双端队列）：
public interface Deque<E> extends Queue<E> {
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
.......
//由于方法比较多，此处为了不增加篇幅，列举一些说明问题即可
.......
}
我们可以很清晰的看到，Deque在继承Queue接口的前提下，扩展了N多方法，但是这些方法都是以XXfirst，XXlast形式的，这说明了，实现这个接口的类必须具有双端操作队列的能力。不在局限于从队头出，从队尾增加。当然，可能有些读者会有疑问，add方法和addlast方法实际上是相同的，为什么要声明addLast方法呢？没错，他们完成的功能的确一样，在LinkedList中也是这样实现的：
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
//实际上他们调用同样的方法来实现，只是返回了不同的类型
//博主也不知道为何这样设计，可能是为了封装性更好吧
所以，在LinkedList的内部方法中，有三对是具有一样功能的方法。
二、LinkedList的内部实现细节
之前我们也说过，既然实现了接口Deque 就一定是用双向链表来实现的，学过数据结构的读者就会发现这种结构灵活性很强。我们一起来看看：
/*为了节约篇幅，只截取部分代码*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient Node<E> first;
transient Node<E> last;
//成员内部类
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;
}
}
}
这就是，整个LinkedList的大体结构，一个成员内部类定义了每个节点的内容，数据值和一个指向前一个节点的prev指针和一个指向后一个节点的next指针。在整个LinkedList中，有一个头指针指向整个队列的头部，一个尾指针指向整个队列的尾部。整个队列的结构如下图：
三、add方法添加元素
了解了LinkedList内部的组成原理，我们接下来看看，怎么在任意位置添加结点元素，比较一下他优于ArrayList的地方是怎么实现的。
public boolean add(E e) {
linkLast(e);
return true;
}
//主要实现还是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++;
}
我们知道add方法是在队列尾部添加元素，还是很容易的。首先用变量 l 指向最后一个节点，然后创建一个节点将它的prev指向 l ，这样newnode成为最后一个节点，使用last指向它，接着使 l 的next指向newnode，这种直接添加在队列尾部的方式还是很好理解的，我们重点看看如何添加在队列的中间位置。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(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 = newNod
size++;
modCount++;
}
首先判断，指定的索引是否大于链表中节点个数size，如果index == size表示，将要添加在最后一个元素的后面，和上述一样，如果不是在最后位置添加元素，将数据域和node（index）（方法不具体看，就是返回索引值为index的结点）
四、remove删除结点
看完了添加，删除就显得简单些，无非分为两种，从头部删除，从中间删除，从头部删除和从尾部添加一样简单，从中间删除就是把此结点的前一个结点的next指向此结点的后一个结点，并把后一个结点的prev指向此节点的前一个结点，就是跳过此结点，最终将此结点null交给GC大人解决。为了篇幅，我们不再赘述。
五、低效的get方法
最后，和大家看看一个方法，我们知道链表是不支持随机访问的，如果你要查找某个结点的元素值，你必须要从头开始遍历直至找到那个元素结点（查找时，效率比ArrayList低下），但是我们的LinkedList 中提供有get（index）方法貌似有随机访问的能力。我们看看代码：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
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;
}
}
从源代码中我们可以清晰的看到，所谓的get方法也就是，调用node方法遍历整个链表，只是其中稍微做了点优化，如果index的值小于size/2从头部遍历，否则从尾部遍历。可见效率一样低下，所以我们以后写程序的时候，如果遇到数据量不大但是需要经常遍历查找的时候使用ArrayList而不是LinkedList，如果数据量非常的大，但是不是很经常的查找时使用LinkedList。
本文是作者查阅书籍和博客总结得来，如有错误，望大家指出！
