LinkedList源码分析--基于JDK1.8
LinkedList的UML图：
LinkedList真正用来存储元素的数据结构-> Node类
Node类是LinkedList中的私有内部类，LinkedList中通过Node来存储集合中的元素
- E：节点的值
- Node next: 当前节点的后一个节点的引用（可以理解为指向当前节点的后一个节点的指针）
- Node 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; }}LinkedList的元素
//LinkedList节点个数，用来记录LinkedList的大小transient int size = 0;/** * 指向第一个节点的指针。用来表示LinkedList的头结点 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */transient Node<E> first;/** * 指向最后一个节点的指针。用来表示LinkedList的尾结点 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */transient Node<E> last;LinkedList的构造函数（两个）
ArrayList的构造函数有三个，比LinkedList多提供了一个设置初始化容量来初始化类。LinkedList没有提供该方法，原因：因为LinkedList底层是通过链表实现的，每添加新元素的时候，都是通过链接新的节点实现的，也就是说它的容量是随着元素的个数的变化而动态变化的。而ArrayList底层是通过数组来存储新添加的元素的，所以我们可以为ArrayList设置初始容量（也就是设置数组的大小）
/** * 空参构造 */public LinkedList() {}/** * 构造包含指定集合元素的列表，按照集合的迭代器返回元素的顺序 * 传入一个结合作为参数初始化LinkedList。 * * @param c 将其元素放置在此列表中的集合 * @throws NullPointerException 如果指定的集合为空 */public LinkedList(Collection<? extends E> c) { this(); addAll(c);}LinkedList的构造函数（带参数）
在LinkedList带集合参数的构造函数中有一个重要的方法addAll(int index, Collection),这块儿的方法有点绕，如果没看懂，建议手画一遍。
/** * 通过调用addAll(int index, Collection<? extends E> c)添加 集合 */public boolean addAll(Collection<? extends E> c) { return addAll(size, c);}/** * checkPositionIndex(index); 检查传入的参数是否合法 */public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); // 将集合转换为数组 Object[] a = c.toArray(); // numNew 存储数组的长度 int numNew = a.length; // 如果 c：待添加的集合为null，直接返回false，不进行后面的操作 if (numNew == 0) return false; // pred：指代 待添加节点的前一个节点 // succ：指的是待添加节点的位置 Node<E> pred, succ; // 如果index==size，说明此时需要添加LinkedList的集合中每一个元素都是在LinkedList最后面。所以把succ设置为null, pred指向尾结点 // 否则的话succ指向插入待插入位置的节点。这里用到了node(index)方法，pred指向succ节点的前一个节点 if (index == size) { // 新添加的元素的位置是位于LinkedList最后一个元素的后面，也就是在LinkedList尾部追加元素 succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } /** * 遍历数组中的每一个元素。在每次遍历的时候，都新建一个节点，该节点的值存储数组a中遍历的值，该节点的prev存储pred节点，next设置为null。 * 接着判断该节点的前一个节点是否为空，如果为空的话，则把当前节点设置为头结点 * 否则的话就把当前节点的前一个节点的next值设置为当前节点。最后把pred指向当前节点，方便后续节点的添加 */ for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } /** * 当succ为null时，也就是新添加的节点位于LinkedList集合的最后一个元素的后面。 * 上面的for遍历的a的所有元素，此时的pred指向的是Linked中的最后一个元素，所以把last指向pred指向的节点 * 当不为空的时候，表明在LinkedList集合中添加的元素，需要把pred的next指向succ上，succ的prev指向pred */ if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } // 重新设置集合的大小 size += numNew; // 修改的次数-自增。 modCount++; return true;}LinkedList中的一些辅助方法
- linkFirst(E e){};把参数中的元素作为链表的第一个元素
/** * 链接e作为第一个元素。 */private void linkFirst(E e) { final Node<E> f = first;// LinkedList中的第一个元素first赋给 f // 组建新的node，新添加的元素的succ（后指针指向给 f） final Node<E> newNode = new Node<>(null, e, f); // 将新插入的节点e，赋给first first = newNode; // 如果 f== null ;说明是空链表，把新节点设置为尾结点 if (f == null) last = newNode; else f.prev = newNode; size++; modCount++;}- linkLast(E e){};把参数中的元素作为链表的最后一个元素
/** * 链接e作为最后一个元素。 */void linkLast(E e) { // 获取尾部元素 final Node<E> l = last; // 以尾部元素为前继结点创建一个新节点 final Node<E> newNode = new Node<>(l, e, null); // 更新尾部节点为需要插入的节点 last = newNode; if (l == null) //如果为空链表的情况：同时更新first节点为需要插入的节点。（也就是说，该节点即是头结点也是尾节点last） first = newNode; else // 不是空链表的情况：将原来的尾部节点（现在是倒是第二个节点）的next指向需要插入的节点 l.next = newNode; size++; // 更新链表大小和修改次数，插入完毕 modCount++;}- linkBefore(E e,Node succ);在非空节点succ之前插入元素 e
/** * 将元素e插入到非空节点succ之前。 */void linkBefore(E e, Node<E> succ) { // assert succ != null; // 创建一个pred变量指向succ节点的前一个节点 final Node<E> pred = succ.prev; // 创建一个新节点，他的prev设置为我们新建的pred变量，后节点设置为succ final Node<E> newNode = new Node<>(pred, e, succ); // succ的上节点（prev）指向新建的节点 succ.prev = newNode; // 判断succ的前节点是否为null，为null，则把新节点设置为链表的头结点 if (pred == null) first = newNode; else // 不为空把，succ的前一个节点的next指向新节点 pred.next = newNode; size++; modCount++;}- unlinkFirst( Node f ){};删除LinkedList中的第一个节点。（该节点不为空，返回删除节点的值）。这是一个私有方法，我们不能够调用，
assert f == first && f != null;参数f是头结点，而且f不能为null
/** * 解除非空第一个节点f的链接。 */private E unlinkFirst(Node<E> f) { // assert f == first && f != null; // 定义一个变量element，值为待删除节点的值。 final E element = f.item; // 定义变量next，值为：待删除的节点的下一个节点 final Node<E> next = f.next; // f节点的值设置为空 f.item = null; f.next = null; // help GC // 将变量next设置为头节点 first = next; // 判断f的下一个节点是否为空，为空：把last设置为空 if (next == null) last = null; else // 不为空，将next的前节点设置为空。next为头结点 next.prev = null; size--; modCount++; return element;}- unlinkLast(Node l){};删除LinkedList的最后一个节点（该节点不为空，并返回删除节点对应的值）
/** * Unlinks non-null last node l. */private E unlinkLast(Node<E> l) { // assert l == last && l != null; // 创建变量element，值为:待删除的节点的值 final E element = l.item; // 创建变量 prev：值为：待删除的节点的前节点 final Node<E> prev = l.prev; // 待删除的节点的值赋空 l.item = null; l.prev = null; // help GC // 将last指向 新建的节点 prev last = prev; // 判断待删除的节点的前节点是否为空，为空：该链表则为空链表，将头结点first赋null值 if (prev == null) first = null; else // 不为空，将待删除的前节点的next指向 null prev.next = null; size--; modCount++; return element;//返回删除的节点的值}- unlink(Node e);删除一个节点，该节点不为空
/** * Unlinks non-null node x. */E unlink(Node<E> x) { // assert x != null; // 变量 element：值：要删除的节点的值 final E element = x.item; // 新建变量：next，值：要删除的节点的下一个节点 final Node<E> next = x.next; // 新建变量：prev，值：要删除的节点的上一个节点 final Node<E> prev = x.prev; // 判断要删除的节点的上一个节点为空，为空：则删除的是头结点，将first指向新建的next if (prev == null) { first = next; } else { // 不为空：将要删除的节点的上一个节点的next指向要删除的节点的下一个节点 prev.next = next; x.prev = null; } // 判断要删除的节点的下一个节点是否为空，为空：则删除的尾结点，将last指向prev，也就是指向要删除的节点的上一个节点 if (next == null) { last = prev; } else { // 不为空，将要删除的节点的下一个节点的上节点指向-》要删除的节点的上个节点 next.prev = prev; x.next = null; } // 这一步就把要删除的节点赋了空值，有助于gc回收 x.item = null; size--; modCount++; return element;}- Node node(int index); 计算指定索引上的节点，并返回。 这里LinkedList不是从头开始进行遍历，而是先比较一下index更靠近链表的头结点还是尾结点，然后进行遍历，获取对应index的节点
/** * 返回指定元素索引处的（非空）节点。 */Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (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; }}以上是一些辅助方法，在LinkedList的add，get,remove等方法中都会使用到相应的方法。
LinkedList中的contains(Object o);
public boolean contains(Object o) { return indexOf(o) != -1;}public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1;}indexOf(Object o)方法中分两种情况，
首先判断传入的参数 o 是不是空，
- 为空：for循环进行查找，找第一个节点的item的值==null的，找到返回对应的下标，没有则返回-1
- 不为空，for循环进行查找，找第一个节点的item的值与o相等的，找到返回对应的下标，没有返回-1；
个人认为看懂了上面的方法，其他的方法都简单明了。