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