（一）ArrayList与LinkedList
前篇讲到利用Object数组实现存储的ArrayList，本篇讲解另一类常用的List实现类LinkedList。相较于ArrayList，LinkedList采用的链表的形式存储。在学习数据结构时，链表的几个特性如：①空间分配灵活，不需要像初始化数组一样指定大小且有空间浪费的可能，链表通过前驱和后继指针连接各个节点。
②对于在中间插入的操作，数组需要将目标位置之后的所有元素依次向后移动一位，而链表只需要改动相应节点的前驱和后继指针即可。效率明显高于数组。
③遍历情况下，数组的优势显现，可以直接通过下标访问元素。而链表只能从端节点依次遍历，效率低于数组方式实现。
LinkedList同样具有以上特性，存储效率和空间使用率方面优于ArrayList，而在元素访问方面不及ArrayList。
（二）LinkedList源码分析（JDK版本1.8）
依旧从类定义讲起
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
和ArrayList类似，实现AbstractSequentialList抽象类，该类和AbstractList类似，继承自AbstractList，不过是有一些LinkedList链表专用的方法。同样的支持序列化和克隆，也具有队列的特性。Deque接口继承Queue接口，提供了队列操作相关的方法定义。
LinkedList中的重要属性
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
size不用说，肯定是当前集合的规模。first和last是两个Node类型的对象，分别是链表的首尾节点。Node类是LinkedList的静态内部类，是链表节点的类，定义如下：
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;
}
}
包含当前节点的值，和其前驱和后继节点。
ArrayList有三种构造方法，而LinkedList只有两种，如下：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
就是这样，感觉很不走心对吧。咱们追踪第二个构造函数：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
继续追踪：
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //查看index是否<0 或 >size
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;
}
通过将传入集合先转化为数组然后将数组元素以节点的方式依次添加到链表尾部的过程。同时更新size的值。
LinkedList类的常用方法
还是以add()为例吧，也好和ArrayList的add()方法做做对比。看过之前的文章应该了解ArrayList的add()方法每次都需要调用ensureSize()函数，经过扩容，复制，插入等业务执行才将元素加入到集合中。这是由于数组的大小不可变的弊端造成的。
public boolean add(E e) {
linkLast(e);
return true;
}
由于LinkedList采用链表的方式，空间上很是自由，不需要检验是否需要扩容，函数中的linkLast(e)能猜出来是将新节点加入链表尾部。
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++;
}
就是在链表的尾部创建新的Node节点，然后加入节点，更新last指向和size的过程。同样，LinkedList中还有linkFirst()方法，只是加到链表头而已。由此可见，插入操作LinkedList在实现难度和效率上明显优于ArrayList。
那么get()操作呢？
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
主要关注node函数，这里按照下标获取对应位置的元素：
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;
}
}
首先判断节点靠近头部还是尾部，然后再从头或尾部依次向前或向后遍历。而ArrayList的Object数组直接通过下标返回，效率高于LinkedList的get操作。
LinkedList的方法不止于此，很多都表现出链表操作的特点。感兴趣的读者可以自行阅读，JDK 1.8中LinkedList类的源码不超过1300行，而且不难。如果面试过程中被问到集合，那么List方面讲到这两个类这些点，就已经很不错了，说个舞蹈十分钟不成问题，注意时间，因为还有Set和Map没说，而且Map很可能是面试的重点。在之后的文章会一一讲解。
