前言
上一篇我们分析了ArrayList这个用数组实现的List集合类，今天继续来分析一个跟它比较相似的List集合类——LinkedList，不过LinkedList的底层实现是链表，它们内部的实现还是有很大差异的。
1. 概览
类间关系图：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可以看到对比起 ArrayList，LinkedList并没有实现RandomAccess 接口，所以我们可以知道它并不支持随机访问。 接下来我们看看LinkedList的具体实现
每个链表存储了 first 和 last 指针分别指向头节点和尾节点：
//总节点数
transient int size = 0;
//头节点
transient Node<E> first;
//尾节点
transient Node<E> last;
可以发现LinkedList是基于双向链表实现的，使用 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;
}
}
下面是LinkedList的结构图：
2. 添加
添加新元素
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
添加到尾部或者插入到指定位置
//尾插到尾节点并将新节点设为尾节点
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++;
}
//将新节点插入到指定节点前面
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++;
}
3. 修改
public E set(int index, E element) {
// 检查index是否合法
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
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;
}
5. fail-fast机制
值得关注的是LinkedList在使用迭代器时也有 fail-fast 机制，在迭代的同时对LinkedList进行了结构上的操作就会触发，抛出ConcurrentModificationException异常。具体源码如下：
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
// fail-fast机制
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
6. 与 ArrayList 的比较
ArrayList的具体分析可以看一下我的上一篇文章：tech.souyunku.com684490…
- ArrayList 基于动态数组实现，LinkedList 基于双向链表实现；
- 都是线程不安全的集合；
- ArrayList 支持随机访问，LinkedList 不支持；
- LinkedList 在任意位置添加删除元素比 ArrayList 更快。
7. 总结
到这里算是我对Java集合类源码分析系列的第四篇文章了，从HashMap、ConcurrentHashMap到ArrayList，其实对这些集合类的源码分析，我大致分成几个步骤分析讲解：
1、 类的继承和实现关系
2、 内部的数据结构
3、 一些比较重要的增删改查方法
4、 这个容器的优缺点，多线程环境下是否安全等
5、 与相似容器的对比，适用场景等
总结起来也就是这些，剩下还有一些其它的容器我没分析到，但只要按上面这个思路去阅读源码并思考分析，就能够对这个容器有更加深刻的理解，而不是仅仅停留在知道如何使用的层次上。