文章目录：
1.看看关于LinkedList源码开头的注释
* Doubly-linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
* elements (including {@code null}).
*
* <p>All of the operations perform as could be expected for a doubly-linked
* list. Operations that index into the list will traverse the list from
* the beginning or the end, whichever is closer to the specified index.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a linked list concurrently, and at least
* one of the threads modifies the list structurally, it <i>must</i> be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more elements; merely setting the value of
* an element is not a structural modification.) This is typically
* accomplished by synchronizing on some object that naturally
* encapsulates the list.
从这段注释中，我们可以得知 LinkedList 是通过一个双向链表来实现的，它允许插入所有元素，包括 null，同时，它是线程不同步的。
· LinkedList集合底层结构是带头尾指针的双向链表。
· LinkedList是非线程安全的。
· LinkedList集合中存储元素的特点：有序可重复，元素带有下标，从0开始，以1递增。
· LinkedList集合的优点：在指定位置插入/删除元素的效率较高；缺点：查找元素的效率不如ArrayList。
如果对双向链表这个数据结构很熟悉的话，学习 LinkedList 就没什么难度了。下面是双向链表的结构：
双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个 first 指针，指向头节点；和 last 指针，指向尾节点。
2.LinkedList中的属性
//双向链表中结点个数 transient int size = 0; //指向头结点的指针 transient Node<E> first; //指向尾结点的指针 transient Node<E> last;
关于LinkedList中的Node节点结构，它其实是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域 item，一个后置指针 next，一个前置指针 prev。
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; } }
3.LinkedList中的方法
3.1 push、offer方法
push、offer方法内部都是调用的相应的add方法，所以直接看下面的add方法源码解析。
public void push(E e) { addFirst(e); } public boolean offer(E e) { return add(e); } public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; }
3.2 添加元素的一系列add方法
在LinkedList集合源码中，添加元素很多时候都会用到 add、addFirst、addLast 这几个，而查看源码发现，这几个方法的内部实际上都调用了 linkFirst、linkLast 、linkBefore 这三个方法。
public boolean add(E e) { linkLast(e); return true; } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); }
所以下面着重来说一下 linkFirst、linkLast 、linkBefore 这三个方法。
3.3 linkFirst方法
对于链表这种数据结构来说，添加元素的操作无非就是在表头/表尾插入元素，又或者是在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。
而linkFirst表面上翻译就是链表首位，也就是在表头添加元素，其源码及添加元素分析过程如下：
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
当我们向双向链表的表头插入一个结点 e 时，这个结点的前驱指针肯定是 null，那么在插入之后，这个 e 结点的后继指针是什么呢？（在e插入之前，原先的表头结点就是表头结点，在e插入到原表头的前面成为了新的表头之后，此时原表头结点不就是当前e结点的后继结点了吗？所以e结点的后继指针自然也就指向了原表头结点，所以这里e的后继指针就是最初链表的头指针first），所以要在插入之前先获取到头指针 f = first，然后将头指针对应的结点修改为新插入的结点e（newNode），对应源码的前三行。
而这个if判断的是：如果在插入之前链表的头指针为空（换句话说，当前链表中没有元素，e结点插入之后只有这一个元素），那么此时e结点肯定既是头结点、也是尾结点啊，所以这里将 last 尾结点修改为刚刚插入的 e 结点。
下面的else是说：当前链表中有多个元素了话，当你在某个结点x之前新插入一个结点e，那么结点x的后继部分肯定没有变化，变化的是它的前驱部分，前驱指针所指内容就变成了新插入的结点e，即 f.prev = newNode。
3.4 linkLast方法
这个方法和 linkFirst 差不多的，无非是一个在表头插入元素，一个在表尾插入元素。
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
首先插入之前，先获取一下原表尾结点的内容（l = last），然后插入新的结点e，这个结点e的后继指针肯定是 null（因为此时它成了链表的表尾结点），而它的前驱指针指向的就应该是上一个表尾结点 l，所以新表尾结点e的内容就是（l，e，null）。然后更新双向链表的尾指针 last 为新插入的结点newNode。
下面的if判断的是：如果在插入之前获取的尾指针 l 为空（也就是说当前链表中没有元素），那么新插入一个元素之后，这个元素肯定既是头结点、也是尾结点，所以这里将它的头指针也更新为 newNode。
else说的是：当插入之前链表中有多个元素，那么在表尾新插入一个元素之后，还要最终修改一下原表尾结点的后继指针，让它指向新的表尾结点。
3.5 linkBefore方法
上面两个方法分别都是在表头、表尾插入元素，那么现在该说一下在中间某个随机位置插入元素的方法了，源码如下：
void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
对应源码来说，这里要插入的结点就是 e，e要插入到 succ 结点的前面，同时位于 pred 结点的后面，而在插入之前（succ的前驱就是pred），所以先获取到这个前驱结点 pred，然后修改e结点的内容（pred，e，succ），那么此时 succ 的前驱就变成了 e，所以更新 succ 的前驱指针指向 newNode。
if判断的是：如果插入之前succ结点的前驱指针pred为空，也就是说此时succ是表头结点，那么e插入之后，它就成了新的表头结点，所以这里让first头指针指向newNode。
else则是说插入之前链表中有多个元素，那么在succ指定结点的前面插入新的结点之后，还要修改succ原前驱节点pred的后继指针，使其指向刚插入的e结点newNode。
3.6 移除元素的一系列remove方法
在LinkedList集合源码中，移除元素很多时候都会用到 remove、removeFirst、removeLast 这几个，而查看源码发现，这几个方法的内部实际上都调用了 unlinkFirst、unlinkLast 、unlink 这三个方法。unlink方法中的node方法是对链表进行遍历的。
public E remove() { return removeFirst(); } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
所以下面着重来说一下 unlinkFirst、unlinkLast 、unlink 这三个方法。
