LinkedList 简介
我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。
LinkedList 插入和删除元素的时间复杂度？
- 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
- 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
- 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。
LinkedList 为什么不能实现 RandomAccess 接口
RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口
LinkedList 源码分析
LinkedList 的类定义如下：
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{//...
}
LinkedList 继承了 AbstractSequentialList ，而 AbstractSequentialList 又继承于 AbstractList
阅读过 ArrayList 的源码我们就知道，ArrayList 同样继承了 AbstractList ， 所以 LinkedList 会有大部分方法和 ArrayList 相似。
插入元素
LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。
我们这里以 List 接口中相关的插入方法为例进行源码讲解，对应的是add() 方法。
add() 方法有两个版本：
add(E e)：用于在LinkedList的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
// 在链表尾部插入元素
public boolean add(E e) {linkLast(e);return true;
}// 在链表指定位置插入元素
public void add(int index, E element) {// 下标越界检查checkPositionIndex(index);// 判断 index 是不是链表尾部位置if (index == size)// 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可linkLast(element);else// 如果不是则调用 linkBefore 方法将其插入指定元素之前linkBefore(element, node(index));
}
// 将元素节点插入到链表尾部
void linkLast(E e) {// 将最后一个元素赋值（引用传递）给节点 lfinal Node<E> l = last;// 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空final Node<E> newNode = new Node<>(l, e, null);// 将 last 引用指向新节点last = newNode;// 判断尾节点是否为空// 如果 l 是null 意味着这是第一次添加元素if (l == null)// 如果是第一次添加，将first赋值为新节点，此时链表只有一个元素first = newNode;else// 如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的nextl.next = newNode;size++;modCount++;
}
// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {// assert succ != null;断言 succ不为 null// 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息final Node<E> pred = succ.prev;// 初始化节点，并指明前驱和后继节点final Node<E> newNode = new Node<>(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev = newNode;// 判断前驱节点是否为空，为空表示 succ 是第一个节点if (pred == null)// 新节点成为第一个节点first = newNode;else// succ 节点前驱的后继引用指向新节点pred.next = newNode;size++;modCount++;
}
获取元素
LinkedList获取元素相关的方法一共有 3 个：
getFirst()：获取链表的第一个元素。getLast()：获取链表的最后一个元素。get(int index)：获取链表指定位置的元素。
// 获取链表的第一个元素
public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;
}// 获取链表的最后一个元素
public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;
}// 获取链表指定位置的元素
public E get(int index) {// 下标越界检查，如果越界就抛异常checkElementIndex(index);// 返回链表中对应下标的元素return node(index).item;
}
这里的核心在于 node(int index) 这个方法：
// 返回指定下标的非空节点
Node<E> node(int index) {// 断言下标未越界// assert isElementIndex(index);// 如果index小于size的二分之一 从前开始查找（向后查找） 反之向前查找if (index < (size >> 1)) {Node<E> x = first;// 遍历，循环向后查找，直至 i == indexfor (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;}
}
