上一篇文章Java集合源码分析-ArrayList分析了ArrayList的源码，这篇文章分析下LinkedList源码并进行一些对比和总结。
LinkedList类图
LinkedList类图
LinkedList的类图和上篇的ArrayList的类图很相似，只是支持随机访问的
RandomAccess改成了支持队列的Deque，其次多继承了一个类AbstractSequentialList。RandomAccess接口里面是空的，只是一个标记接口(Marker)，只要集合实现这个接口，就能支持快速随机访问。可以看下Collections类中的binarySearch方法：
public static <T> int binarySearch(List<? extends Comparable<? super T>> var0, T var1) {
return !(var0 instanceof RandomAccess) && var0.size() >= 5000 ? iteratorBinarySearch(var0, var1) : indexedBinarySearch(var0, var1);
}
由此可以看出，二分查找根据是否是RandomAccess接口来实行indexedBinarySerach(list,key)还是iteratorBinarySerach(list,key)方法，前者是ArrayList使用的二分查找，后者是LinkedList使用的二分查找，ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快。引用1
LinkedList数据结构
上面的类图中我们可以看到，LinkedList的成员变量很少且只有三个：代表节点个数的size、头结点first和尾节点last。Java中的LinkedList的数据结构是一个双向非循环链表，由内部类Node定义：
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
this.item = var2;
this.next = var3;
this.prev = var1;
}
}
数据结构
构造器
构造器很简单，只提供了两个，一个是无参构造器，一个是带有一个Collection参数的构造器：
public LinkedList() {
this.size = 0;
}
public LinkedList(Collection<? extends E> var1) {
this();
this.addAll(var1);
}
LinkedList核心操作
LinkedList核心操作包括：
size():intindexOf(val:Object):intget(pos:int):Eset(pos:int, val:E)add(val:E):booleanadd(pos:int, val:E)remove(val:int):Eremove(ob:Object):booleanclone():Object
size():int
public int size() {
return this.size;
}
indexOf(val:Object):int
public int indexOf(Object var1) {
int var2 = 0;
LinkedList.Node var3;
if (var1 == null) {
for(var3 = this.first; var3 != null; var3 = var3.next) {
if (var3.item == null) {
return var2;
}
++var2;
}
} else {
for(var3 = this.first; var3 != null; var3 = var3.next) {
if (var1.equals(var3.item)) {
return var2;
}
++var2;
}
}
return -1;
}
这个方法是从头结点开始遍历查找，还有一个对应的方法lastIndexOf(ob:Object):int是从尾节点开始遍历查找。
get(pos:int):E
public E get(int var1) {
this.checkElementIndex(var1);
return this.node(var1).item;
}
第二行是进行越界检查，第三行是一个for循环进行下标遍历查找。
set(pos:int, val:E)
public E set(int var1, E var2) {
this.checkElementIndex(var1);
LinkedList.Node var3 = this.node(var1);
Object var4 = var3.item;
var3.item = var2;
return var4;
}
和get方法类似，首先进行越界检查，然后进行下标遍历查找。
add(val:E):boolean
public boolean add(E var1) {
this.linkLast(var1);
return true;
}
LinkedList.Node<E> node(int var1) {
LinkedList.Node var2;
int var3;
if (var1 < this.size >> 1) {
var2 = this.first;
for(var3 = 0; var3 < var1; ++var3) {
var2 = var2.next;
}
return var2;
} else {
var2 = this.last;
for(var3 = this.size - 1; var3 > var1; --var3) {
var2 = var2.prev;
}
return var2;
}
}
void linkLast(E var1) {
LinkedList.Node var2 = this.last;
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
this.last = var3;
if (var2 == null) {
this.first = var3;
} else {
var2.next = var3;
}
++this.size;
++this.modCount;
}
这个是向尾部添加节点，不需要遍历。
add(pos:int, val:E)
public void add(int var1, E var2) {
this.checkPositionIndex(var1);
if (var1 == this.size) {
this.linkLast(var2);
} else {
this.linkBefore(var2, this.node(var1));
}
}
void linkBefore(E var1, LinkedList.Node<E> var2) {
LinkedList.Node var3 = var2.prev;
LinkedList.Node var4 = new LinkedList.Node(var3, var1, var2);
var2.prev = var4;
if (var3 == null) {
this.first = var4;
} else {
var3.next = var4;
}
++this.size;
++this.modCount;
}
这个是向指定位置插入节点，需要遍历。
remove(val:int):E
public E remove(int var1) {
this.checkElementIndex(var1);
return this.unlink(this.node(var1));
}
删除指定位置的节点。
remove(ob:Object):boolean
public boolean remove(Object var1) {
LinkedList.Node var2;
if (var1 == null) {
for(var2 = this.first; var2 != null; var2 = var2.next) {
if (var2.item == null) {
this.unlink(var2);
return true;
}
}
} else {
for(var2 = this.first; var2 != null; var2 = var2.next) {
if (var1.equals(var2.item)) {
this.unlink(var2);
return true;
}
}
}
return false;
}
删除指定节点。
clone():Object
public Object clone() {
LinkedList var1 = this.superClone();
var1.first = var1.last = null;
var1.size = 0;
var1.modCount = 0;
for(LinkedList.Node var2 = this.first; var2 != null; var2 = var2.next) {
var1.add(var2.item);
}
return var1;
}
克隆出一个新的LinkedList，注意是浅拷贝。
遍历与性能
和ArrayList一样，LinkedList也是使用三种遍历方式，而且LinkedList的迭代器也是fail-fast的，foreach遍历和Iterator遍历的时候进行增删等操作也会和ArrayList一样抛出ConcurrentModificationException异常，而下标遍历方式不存在这个问题。但是和ArrayList不同的是，LinkedList的下标遍历十分低效，get方法会从头遍历直到index下标，查找一个元素时间复杂度为O(n)，遍历的时间复杂度就达到了O(n2)，而foreach遍历和Iterator遍历的时间复杂度是O(N)。关于ArrayList和LinkedList的几种循环遍历方式及性能对比分析，这篇文章真是用了心，总结的非常好，非常值得一看。
ArrayList：
- 下标遍历最高效，foreach遍历和Iterator遍历性能略差，但是差距不是很明显；
- 访问数组中第 n 个数据的时间花费是 O(1)，但是要在数组中查找一个指定的数据则是 O(N)
- 当向数组中插入或者删除数据的时候，最好的情况是在数组的末尾进行操作，时间复杂度是 O(1) ，但是最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N)。
LinkedList：
- foreach遍历和Iterator遍历性能最高效，下标遍历十分低效，而且随着数据量的增大，下标遍历与foreach遍历和Iterator遍历性能差距巨大，因为时间复杂度是O(n2)
- 访问数据需要遍历链表，因此时间复杂度是O(N)
- 插入数据的时候，如果插入头结点或者尾节点，可以使用
addFirst()、push()和addLast()方法，那么不需要遍历链表，只需要修改指针，时间复杂度是O(1)，如果向指定位置插入数据的话，则需要遍历链表，时间复杂度是O(N)，总的来说时间复杂度是O(N)。 - 删除数据的时候，如果删除头结点或者尾节点，可以使用
removeFirst()和removeLast()方法，那么不需要遍历链表，只需要修改指针，时间复杂度是O(1)，如果删除指定位置或者删除指定节点的话，则需要遍历链表，时间复杂度是O(N)，总的来说时间复杂度是O(N)。
List集合总结
总结参考自：java集合系列——List集合总结（六）
List继承自Collection，是有序的列表。
实现类有ArrayList、LinkedList、Vector、Stack等
- ArrayList基于数组实现，可以动态的增加容量，每次增加后的容量是原来的1.5倍
- LinkedList是基于双向非循环链表实现
- Vector是基于数组实现的，是一个矢量队列，是线程安全的！
- Stack是基于数组实现的，是栈，它继承与Vector，特性是FILO（先进后出）！
使用场景：
应用中如果使用到队列，栈，链表，首先可以想到使用List。不同的场景下面使用不同的工具，效率才能更高！
- 当集合中对插入元素数据的速度要求不高，但是要求快速访问元素数据，则使用ArrayList！
- 当集合中对访问元素数据速度不做要求不高，但是对插入和删除元素数据速度要求高的情况，则使用LinkedList！
- 当集合中有多线程对集合元素进行操作时候，则使用Vector！但是现在Vector现在一般不再使用，如需在多线程下使用，可以用CopyOnWriteArrayList，在java.util.concurrent包下。
- 当集合中有需求是希望后保存的数据先读取出来，则使用Stack！
后面的文章会分析Java的Set集合源码。
最后附一张来自引文的微缩版Java集合框架图片：
微缩版Java集合框架
网友评论