想写这个系列很久了,对自己也是个总结与提高。原来在学JAVA时,那些JAVA入门书籍会告诉你一些规律还有法则,但是用的时候我们一般很难想起来,因为我们用的少并且不知道为什么。知其所以然方能印象深刻并学以致用。
本篇文章针对JAVA中集合类LinkedList进行分析,通过代码解释Java中的Fail-fast设计思想,以及LinkedList底层实现和与ArrayList对比下的就业场景。
本文会通过QA的方式行文
本文基于JDK 11
是双向链表。LinkedList不光实现了List
接口,还实现了Deque
接口。
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
因为要实现双向链表,双向队列的机制,同时可以存储null值(也就是有额外的引用变量指向实际的节点数据),每个节点都是由三个引用组成:
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
这样,存储占用了更多空间。
add(E element)
还有addAll(Collection elements)
以外,还有addFisrt(E element)
和addLast(E element)
可以使用。由于LinkedList而外维护了指向头结点还有尾节点的指针,所以复杂度都是O(1)
/**
* Pointer to first node.
*/
//由于这些没必要序列化,所以加上transient
transient Node first;
/**
* Pointer to last node.
*/
transient Node last;
get(int index)
等所有涉及到下标操作的方法,由于需要遍历,复杂度都是O(N/2)
.实现遍历的核心方法是:Node node(int index) {
//看index是否大于size一半或者小于,决定从链表头遍历还是末尾遍历
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
add(E element)
类似,remove(E element)
也有对应的removeFirst()
和removeLast()
存在(对于空的链表会抛出NoSuchElementException),并且由于LinkedList而外维护了指向头结点还有尾节点的指针,所以复杂度都是O(1)
。但是remove(Object o)
的复杂度是O(N)
,因为是从开头遍历寻找第一个equals返回true的。同时还有removeFirstOccurrence(Object o)
(和remove等价)和removeLastOccurrence(Object o)
方法。public boolean removeLastOccurrence(Object o) {
//对于null的值,直接寻找为null的,否则通过调用equals判断是否相等
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
poll()
和pop()
效果相同,都是将队列第一个元素剔除并返回。不同的是,针对空链表,poll()
返回null,pop()
抛出NoSuchElementException异常(因为底层实现就是removeFirst()
)fail-fast指的是在可能的损害发生前,直接失败。在JAVA中的一种体现就是当某个集合的Iterator已经创建后,如果修改了集合,再访问Iterator进行遍历就会抛出ConcurrentModificationException
LinkedList和其它集合类似,通过modCount
这个field实现。
所有修改都会让modCount++
。生成的Iterator会记录这个modCount
,如果modCount
发生改变,抛出ConcurrentModificationException
:
private class ListItr implements ListIterator {
private Node lastReturned;
private Node next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
//举一个方法作为例子,其他省略...
public void forEachRemaining(Consumer action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
还有一些其他的扩展迭代器,例如Spliterator,也是fail-fast的
集合排序基本上都是基于这个方法:Collections.swap()
public static void swap(List list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
}
基本都是下标操作,所以,ArrayList更好
我们来看在末尾加元素的方法:
void linkLast(E e) {
//假设原始last为1,新加入两个节点2,3
final Node l = last;
final Node newNode = new Node<>(l, e, null);
//假设这里发生了线程切换,将会发生,1->2->null之后变成1->3->null的情况
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
//++都不是线程安全的,导致size误判
size++;
modCount++;
}
如果想实现线程安全的list:
List list = Collections.synchronizedList(new LinkedList(...));
获取并发安全LinkedList
在大部分场景(遍历,下标查找,排序等)下,ArrayList性能更佳并且占用存储空间小。只有下标插入删除这种场景,LinkedList更有优势。