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