一.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、分布式缓存、数据结构等等。