说明: 源码分析基于 JDK1.8
LinkedList简介
LinkedList是一个实现了List接口和Deque接口的双端链表容器。LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列(Queue)的特性，同时又可以看作是一个栈(Stack)；LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法。
补充: 关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。AbstractSequenceList提供了List接口骨干性的实现以减少了实现受“连续访问”数据存储（如链表）支持的此接口所需的工作。对于随机访问数据（如数组），则应该优先使用抽象类AbstractList。
LinkedList实现List接口，能对它进行队列操作。
LinkedList实现Deque接口，即能将LinkedList当作双端队列使用。
LinkedList实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList不是线程安全的。
LinkedList定义的字段如下:
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Size代表的是链表中存储的元素个数，而first和last分别代表链表的头节点和尾节点。 其中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;
}
}
Node是链表的节点类，其中的三个属性item、next、prev分别代表了节点的存储属性值、前继节点和后继节点。
源码解析
增加
将元素添加到链表尾部:
/**
* 将一个元素添加至list尾部
*/
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
在指定位置添加元素:
/**
* 在指定位置添加元素
*/
public void add(int index, E element) {
// 检查index是否越界
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
linkBefore方法需要给定两个参数，一个插入节点的值，一个指定的node，所以我们又调用了Node(index)去找到index对应的node:
void linkBefore(E e, Node<E> succ) {
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++;
}
将元素添加到链表头部:
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++;
}
将集合从指定位置开始插入:
/**
* 添加一个集合元素到list中
*/
public boolean addAll(Collection<? extends E> c) {
// 将集合元素添加到list最后的尾部
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;
}
由上述代码可见，LinkedList在表尾添加元素，只要直接修改相关节点的前后继节点信息，而无需移动其他元素的位置，因此执行添加操作时效率很高。此外，LinkedList也是非线程安全的。
看似代码逻辑比较复杂，其实核心就是双向链表的存储结构，核心逻辑：
- 将元素转换为链表节点；
- 增加该节点的前后引用（即prev和next分别指向哪一个节点）；
- 前后节点对该节点的引用（前节点的next指向该节点，后节点的prev指向该节点）。
删除
remove() ,removeFirst(),pop(): 删除头节点
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E pop() {
return removeFirst();
}
removeLast(),pollLast(): 删除尾节点
区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
remove(Object o): 删除指定元素
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;
}
unlink(Node x) 方法：
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;
}
remove(int index)：删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
获取
get()方法的主体还是调用了node(int index)方法。
/**
* 查找指定索引位置的元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
为了优化查询效率，LinkedList采用了一次简单的二分，判断index和size中间位置的距离，采取从后向前还是从前向后遍历。
到这里我们明白，基于双向链表实现的LinkedList，通过索引Index的操作时低效的，index所对应的元素越靠近中间所费时间越长。而向链表两端插入和删除元素则是非常高效的（如果不是两端的话，都需要对链表进行遍历查找）。
设置
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
只要修改该节点上的元素。
是否包含
public boolean contains(Object o) {
return indexOf(o) != -1;
}
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;
}
indexOf查询元素位于容器的索引位置，都是需要对链表进行遍历操作，当然也就是低效了。
总结
- LinkedList实际上是通过双向链表去实现的。
- 从LinkedList的实现方式中可以发现，它不存在容量不足的问题。
- LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
- 与ArrayList的比较:
- ArrayList 基于动态数组实现，LinkedList 基于双向链表实现；
- ArrayList 支持随机访问，LinkedList 不支持；
- LinkedList 在任意位置添加删除元素更快。
参考文献:
- Eckel B. Java 编程思想 [M]. 机械工业出版社, 2002.
- Java Collection Framework
- Java集合框架源码解读
