前言
LinkedList相对ArrayList来说可以使用频率可能相对较低，但是对于不同需求到情况下我们需要能够选择合适的集合，本文将结合JDK1.8源码从线程安全、数据结构、初始化、增删改查、特性总结等几个部分去分析LinkedList
线程安全
ArrayList是非线程安全的，不支持并发。我们可以从它的数据迭代器ArrayList$Itr中可以得知，当产生线程安全问题时会抛出抛出ConcurrentModificationException异常。内部是通过一个modCount变量记录集合的变化，在扩容与删除及清空等操作都会将modCount自增，以此来标记集合的改变。
如何实现线程安全
1.通过Colletions.synchronizedCollection获取线程安全的集合对象
2.使用并发库下的ConcurrentLinkedQueue或者ConcurrentLinkedDeque（读写分离）
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
...
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
数据结构
LinkedList采用双向链表对数据进行管理，通过指针形式的链接实现多个对象多有序排列，因此相对于ArrayList的数组形式来说，LinkedList的实现方式使得增删更加高效。而改查时由于需要遍历链表，所以相对低效。
初始化
提供了两个重载构造方法，除了默认的无参构造器外还可以指定初始集合内容。为什么比ArrayList少了个指定容量的构造方法呢？实际上，链表构成的LinkedList没有容量的概念，它做的只是将某些对象封装为node，而node之间通过指针指向来形成有序的集合。在指定初始集合时，实际就是调用addAll方法将所有元素进行添加操作，这个后续会讲到。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
增操作
增操作首先进行一些基本条件判断，指定的index是否越界。主要的实现即通过对节点元素对pre和next指针的指向来链接插入元素。
以下是add方法的分析：
void linkLast(E e) {
final Node<E> l = last; // 缓存此时的last
final Node<E> newNode = new Node<>(l, e, null); // 为元素生成node对象
last = newNode; // 指定新last
if (l == null) // 如果原本last为null那么表示之前没有任何元素
first = newNode; // 将first也指定为该元素
else
l.next = newNode; // 否则将原本的last.next指定为该元素
size++; // 数量递增
modCount++; // modCount递增（用于线程安全检测）
}
以下是addAll方法的分析：
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 越界检查
Object[] a = c.toArray(); // 将Collection转为数据，便于循环遍历
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ; // pred记录目标位置的前一个元素，succ用于记录目标位置
if (index == size) { // 如果目标位置为末尾
succ = null; // 目标位置为null
pred = last; // 目标位置前一个即为last
} else { // 否则目标位置为某个元素
succ = node(index); // 获取目标元素
pred = succ.prev; // 记录目标元素pred元素
}
for (Object o : a) { // 循环数组
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); // 为其生成node对象
if (pred == null) // 如果pred为null表示此前没有元素
first = newNode; // 指定为first
else
pred.next = newNode; // 指定为目标元素的next
pred = newNode; // 将pred赋值为该节点，为下个元素拼接做准备
}
if (succ == null) { // 如果succ为null表示在这之前没有任何元素，那么last指定为最后的pred即可
last = pred;
} else { // 否则将拼接后的末尾next指定为之前取得的目标位置succ
pred.next = succ;
succ.prev = pred; // 而succ的prev指定为pred
}
size += numNew; // 数量更新
modCount++; // modCount递增（用于线程安全检测）
return true; // 返回true表示添加成功
}
删操作
删除操作通过将目标位置的前后拼接到一起，从而使目标位置的元素脱离整个链表结构，以此达到删除操作的目的。
public boolean remove(Object o) {
// 区分元素是否为null，证明LinkedList支持添加null对象
if (o == null) {
// 通过从first到开始不断next的方法循环整个链表
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) { // 如果节点的值为null，则是我们要移除的目标
unlink(x); // 将目标从链表中unlink掉
return true; // 返回true 表示移除成功
}
}
} else { // 不为null元素的情况下
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false; // 没有找到指定元素，返回false
}
// unlink, 将指定元素从链表中移除
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; // 记录元素的value
final Node<E> next = x.next; // 记录指定元素next
final Node<E> prev = x.prev; // 记录指定元素prev
// 如果指定元素prev为null，表示目标元素为first
// 直接将first指定为目标元素的next即可
if (prev == null) {
first = next;
} else {
// 如果指定元素位于中间或者末尾
// 则指定其prev.next为目标元素的next，即将目标元素分隔开
prev.next = next;
x.prev = null; // 此处指定目标元素的prev为null是为了利于gc，避免泄漏
}
// 如果目标元素next为null表示它处于末尾，需要更新last
if (next == null) {
last = prev;
} else {
// 否则目标元素处于中间，需要更新其next的prev指向
next.prev = prev;
x.next = null; // 此处指定目标元素的prev为null是为了利于gc，避免泄漏
}
x.item = null; // 元素value置空
size--; // 更新数量
modCount++; // modCount递增（用于线程安全）
return element; // 返回被删除的对象
}
改操作
很简单，越界检查 - > 得到目标 - > 修改 - > 返回原值
public E set(int index, E element) {
checkElementIndex(index); // 越界检查
Node<E> x = node(index); // 得到目标对象节点
E oldVal = x.item; // 记录old value
x.item = element; // 修改为new value
return oldVal; // 返回old value
}
// 用于得到指定位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
// 此处进行简单的二分判断，决定链表遍历的方向，提升效率
if (index < (size >> 1)) { // 小于数量一半
Node<E> x = first; // 从头部开始遍历
for (int i = 0; i < index; i++) // 得到index节点
x = x.next;
return x;
} else { // 大于数量一半
Node<E> x = last; // 从尾部开始遍历
for (int i = size - 1; i > index; i--) // 得到index节点
x = x.prev;
return x;
}
}
查操作
很简单，越界检查 - > 得到目标节点返回对象
public E get(int index) {
checkElementIndex(index); // 越界检查
return node(index).item; // 同上分析
}
特性总结
1.数据结构为双向链表，增删快、改查慢
2.由于使用链表的结构，所以没有扩容操作
3.在查找元素时会进行区间折半，提升查找效率
