一.LinkedList 数据结构
1.1 数据结构
LinkedList 底层数据结构是一个双向链表，整体构造如下图所示：
注意事项：
- 链表每个节点叫做 Node，Node 有 prev 属性，代表前一个节点的地位，next 属性，代表后一个节点的位 置
- first 是双向链表的头节点，它的前一个节点是 null。
- last 是双向链表的尾节点，它的后一个节点是 null；
- 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
- 因为是个双向链表，是没有大小限度的。
1.2 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;
}
}
二. 源码剖析
2.1 LinkedList 类正文解析
- 应用“双向链表”来实现 List 与 Deque 接口。实现了所有 List 接口中的办法，并且容许寄存所有元素，包含 Null。
- 所有的操作都可通过双向链表实现。通过从结尾或者结尾遍历汇合，去靠近要操作的那个元素。
- 是非线程平安的，多线程状况下，举荐应用线程安全类：Collections#synchronizedList
- 加强 for 循环，或者应用迭代器迭代过程中，如果数组大小被扭转，会疾速失败，抛出异样。
2.2 新增
源码解析：
新增节点时，咱们能够抉择追加到链表头部，还是追加到链表尾部，add 办法默认是从尾部开始追加，addFirst 方
法是从头部开始追加：
增加：
/**
* 将元素增加到链表尾部，等于 addFirst
*/
public boolean add(E e) {linkLast(e);
return true;
}
从尾部减少：
/**
* 从尾部开始追加节点
*/
void linkLast(E e) {
// 把尾节点数据暂存
final Node<E> l = last;
// 新建新的节点，初始化入参含意：// l 是新节点的前一个节点，以后值是尾节点值
// e 示意以后新增节点，以后新增节点后一个节点是 null
final Node<E> newNode = new Node<>(l, e, null);
// 将新建节点追加到尾部
last = newNode;
// 如果链表为空 l 是尾节点，尾节点为空，链表即空，头部和尾部是同一个节点，都是新建的节点
if (l == null)
first = newNode;
else
// 否则把前尾节点的下一个节点，指向以后尾节点。l.next = newNode;
// 大小和版本更改
size++;
modCount++;
}
从头部减少：
/**
* 从头部开始追加节点
*/
private void linkFirst(E e) {
// 把头节点数据暂存
final Node<E> f = first;
// 新建新的节点，初始化入参含意：// l 是新节点的前一个节点，以后值是尾节点值
// f 示意以后新增节点，以后新增节点后一个节点是 null
final Node<E> newNode = new Node<>(null, e, f);
// 将新建节点追加到头部
first = newNode;
// 如果链表为空 f 是头节点，头节点为空，链表即空，头部和尾部是同一个节点，都是新建的节点
if (f == null)
last = newNode;
else
// 上一个头节点的前一个节点指向以后节点
f.prev = newNode;
size++;
modCount++;
}
注意事项：
- 头部追加节点和尾部追加节点，只是前者是挪动头节点的 prev 指向，后者是挪动尾节点的 next 指向，两者区别不大。
2.3 删除实现
源码解析：
LinkedList 节点删除的形式和追加相似，咱们能够抉择从头部删除，也能够抉择从尾部删除，删除操作会把节点的值，前后指
向节点都置为 null。
从头部删除：
/**
* 从头部开始删除节点
*/
private E unlinkFirst(Node<E> f) {
// 拿出头节点的值，作为办法的返回值
final E element = f.item;
// 拿出头节点的下一个节点
final Node<E> next = f.next;
// 帮忙 GC 回收头节点
f.item = null;
f.next = null;
// 头节点的下一个节点成为头节点
first = next;
// 如果 next 为空，表明链表为空
if (next == null)
last = null;
else
// 链表不为空，头节点的前一个节点指向 null
next.prev = null;
// 批改链表大小和版本
size--;
modCount++;
return element;
}
从尾部删除：
/**
* 和从头部删除基本一致
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
注意事项：
- 前后指向节点都置为 null，是为了帮忙 GC 进行回收；
- 从源码中咱们能够理解到，链表构造的节点新增、删除仅仅把前后节点的指向批改了，所以 LinkedList 新增和删除度很快。
2.4 实现查问
查问：
/**
* 依据链表索引地位查问节点
*/
Node<E> node(int index) {
// 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。if (index < (size >> 1)) {
Node<E> x = first;
// 直到 for 循环到 index 的前一个 node 进行
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 处于队列的后半局部，从尾开始找
Node<E> x = last;
// 直到 for 循环到 index 的后一个 node 进行
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
注意事项：
LinkedList 并没有采纳从头循环到尾的做法，而是采取了二分法，首先看 index 是在链表的前半部分，还是后半局部。如果是前半部分，就从头开始寻找，反之亦然。通过这种形式，使循环的次数 至多升高了一半，进步了查找的性能。
三. 工夫复杂度
get() 获取第几个元素，顺次遍历，复杂度 O(n)
add(E) 增加到开端，复杂度 O(1)
add(index, E) 增加第几个元素后，须要先查找到第几个元素，间接指针指向操作，复杂度 O(n)（这个比拟容易想错）
remove（）删除元素，间接指针指向操作，复杂度 O(1)
四. 线程平安
4.1 线程平安问题
只有当 LinkedList 作为共享变量时，才会有线程平安问题，当 LinkedList 是办法内的局部变量时，是没有线程平安的问题的。
LinkedList 有线程平安问题的起因，是因为 LinkedList 本身的 size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被笼罩的状况。
类正文中举荐应用 Collections#synchronizedList 来保障线程平安，SynchronizedList 是通过在每个办法下面加上锁来实现，尽管实现了线程平安，然而性能大大降低，具体实现源码：
public boolean add(E e) {synchronized (mutex) {return c.add(e);}
}
咱们也能够应用 ConcurrentLinkedQueue 来保障线程平安,
五. 总结
LinkedList 的底层是链表构造 , 实用于适宜于常常新增和删除的场景,
欢送关注公众号：前程有光，支付一线大厂 Java 面试题总结 + 各知识点学习思维导 + 一份 300 页 pdf 文档的 Java 外围知识点总结！这些材料的内容都是面试时面试官必问的知识点，篇章包含了很多知识点，其中包含了有基础知识、Java 汇合、JVM、多线程并发、spring 原理、微服务、Netty 与 RPC、Kafka、日记、设计模式、Java 算法、数据库、Zookeeper、分布式缓存、数据结构等等。