本文主要参考自以下文章，包含内容的转载，在此表示感谢：
Java集合：LinkedList详解java集合之LinkedList详解介绍数据结构–LinkedList的相关概念及操作。
LinkedList 和 ArrayList 一样，不是同步容器。所以需要外部做同步操作，或者直接用 Collections.synchronizedList 方法包一下：
List list = Collections.synchronizedList(new LinkedList(...));
此时list是线程安全类，自身提供的方法也是线程安全的。当然list进行其他非原子操作仍需自己同步。
LinkedList继承了AbstractSequentialList并实现了List接口，Deque接口，Cloneable接口，Serializable接口，因此它有List的特性(add,remove,etc.)支持队列操作，可复制，可序列化。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.SerializableLinkedList底层基于双向链表，并且使用了size属性来记录链表的长度(结点的数量)。其基本的数据结构如下：
LinkedList提供了三种构造器
方法 说明 LinkedList()构造一个空链表。LinkedList(Collection c)构造一个包含指定 collection 的元素的列表。这些元素是按照该 collection 的迭代器返回它们的顺序排列的。LinkedList(Collection c)调用了无参构造方法，并调用了addAll()。
addAll()的主要作用是：将指定集合的所有元素添加到当前列表的尾部，按照指定集合的顺序插入，如果在操作正在进行时修改指定的集合，则此操作的行为是不确定的。此处说明了LinkedList不是线程安全的。
/** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }类似HashMap、ArrayList等，LinkedList也维护了modCount变量来实现fail-fast机制，其记录了数组的修改次数，在LinkedList的所有涉及结构变化的方法中都增加modCount的值。 该变量迭代器等方面体现。
//检查链表是否修改，根据expectedModCount和modCount判断 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }因此在使用迭代器迭代过程中，不允许对链表结构做修改（如插入新节点），否则会抛出异常 java.util.ConcurrentModificationException。
add(E e)：调用linkLast方法将元素添加到尾部（linkLast方法详解见下文）
public boolean add(E e) { linkLast(e); // 调用linkLast方法, 将节点添加到尾部 return true; }add(int index, E element)：
检查index是否越界比较index与size，如果index==size，则代表插入位置为链表尾部，调用linkLast()（linkLast方法详解见下文），否则调用linkBefore()（LinkBefore方法详解见下文） public void add(int index, E element) { // 在index位置插入节点，节点值为element checkPositionIndex(index); if (index == size) linkLast(element);// 如果索引为size，即将element插入链表尾部 else // 否则，将element插入原index位置节点的前面，即：将element插入index位置，将原index位置节点移到index+1的位置 linkBefore(element, node(index)); // 将element插入index位置 }
remove(Object o)：
判断o是否为null，如果o为null，则遍历链表寻找item属性为空的节点，并调用unlink方法将该节点移除（unlink方法详解见下文）如果o不为null, 则遍历链表寻找item属性跟o相同的节点，并调用unlink方法将该节点移除（unlink方法详解见下文） public boolean remove(Object o) { if (o == null) { // 如果o为空, 则遍历链表寻找item属性为空的节点, 并调用unlink方法将该节点移除 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { // 如果o不为空, 则遍历链表寻找item属性跟o相同的节点, 并调用unlink方法将该节点移除 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }remove(int index)：
检查index是否越界调用unlink方法，移除index位置的节点（unlink方法详解见下文） public E remove(int index) { // 移除index位置的节点 checkElementIndex(index); // 检查index是否越界 return unlink(node(index)); // 移除index位置的节点 }
清除链表的所有节点：
从first节点开始，遍历将所有节点的属性清空将first节点和last节点设为null public void clear() { // 清除链表的所有节点 // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { // 从头结点开始遍历将所有节点的属性清空 Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; // 将头结点和尾节点设为null size = 0; modCount++; }
返回副本，浅拷贝，与ArrayList.clone()相似。
//返回副本，浅拷贝，与ArrayList.clone()相似 public Object clone() { LinkedList<E> clone = superClone(); //将clone构造成一个空的双向循环链表 // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node<E> x = first; x != null; x = x.next) clone.add(x.item); //浅拷贝，节点还是同一份引用 return clone; }
链表转换为数组主要是进行拷贝工作，跟上述clone()方法类似，同样也是浅拷贝。
返回一个数组，使用运行时确定类型，该数组包含在这个列表中的所有元素（从第一到最后一个元素）：
调用时，需要先传入一个想要的类型的空数组，称为参数数组。如果参数数组容量比链表节点数少，重新申请一个容量足够的数组（大小为size)，再进行拷贝；否则覆盖参数数组前size位，且第size位赋null，剩余不变。返回此参数数组。 //返回一个数组，使用运行时确定类型，该数组包含在这个列表中的所有元素（从第一到最后一个元素） //如果参数数组容量比链表节点数少，则返回链表数组；否则覆盖参数数组前size位，且第size位赋null，剩余不变。 @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { //如果参数数组容量不够，则重新申请容量足够的数组 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; //遍历依次覆盖 for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }由于LinkedList实现了Deque接口，而Deque继承了Queue，因此LinkedList也可以进行队列操作，包括：
// 队列操作，获取表头节点的值，表头为空返回null public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } // 队列操作，获取表头节点的值，表头为空抛出异常 public E element() { return getFirst(); } // 队列操作，获取表头节点的值，并删除表头节点，表头为空返回null public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 队列操作，获取表头节点的值，并删除表头节点，表头为空抛出异常 public E remove() { return removeFirst(); } // 队列操作，将指定的元素添加为此列表的尾部（最后一个元素）。 public boolean offer(E e) { return add(e); }由于LinkedList实现了Deque接口，因此可用于双向队列
// 双向队列操作，链表首部插入新节点 public boolean offerFirst(E e) { addFirst(e); return true; } // 双向队列操作，链表尾部插入新节点 public boolean offerLast(E e) { addLast(e); return true; } // 双向队列操作，获取链表头节点值 public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } // 双向队列操作，获取尾节点值 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } // 双向队列操作，获取表头节点的值，并删除表头节点，表头为空返回null public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // 双向队列操作，获取表尾节点的值，并删除表尾节点，表尾为空返回null public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }其中ListItr是LinkedList的一个内部类，实现了ListIterator接口，是个支持双向的迭代器。
listIterator(int index)：
// 返回从指定位置开始的ListIterator迭代器 public ListIterator<E> listIterator(int index) { checkPositionIndex(index); //检查位置合法性 return new ListItr(index); }利用上面实现的双向迭代器类ListItr，可轻易的实现逆向的迭代器。
descendingIterator()：
// 返回一个迭代器在此双端队列以逆向顺序的元素 public Iterator<E> descendingIterator() { return new DescendingIterator(); } // DescendingIterator的实现，从后往前的迭代 private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); //获得链表尾部的ListItr public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }java8新增方法，类似Iiterator， 可以理解为 Iterator 的 Split 版本：
使用 Iterator 的时候，我们可以顺序地遍历容器中的元素，使用 Spliterator 的时候，我们可以将元素分割成多份，分别交于不于的线程去遍历，以提高效率。使用 Spliterator 每次可以处理某个元素集合中的一个元素 — 不是从 Spliterator 中获取元素，而是使用 tryAdvance() 或 forEachRemaining() 方法对元素应用操作。但 Spliterator 还可以用于估计其中保存的元素数量，而且还可以像细胞分裂一样变为一分为二。这些新增加的能力让流并行处理代码可以很方便地将工作分布到多个可用线程上完成。
LinkedList详解可以看我的另一篇文章：Java集合：ArrayList详解
ArrayList底层基于动态数组实现(扩容1.5倍，拷贝数组)，LinkedList底层基于链表实现对于随机访问（get/set方法），ArrayList通过index直接定位到数组对应位置的节点，而LinkedList需要从头结点或尾节点开始遍历，直到寻找到目标节点，因此在效率上ArrayList优于LinkedList对于插入和删除（add/remove方法），ArrayList需要移动目标节点后面的节点（使用System.arraycopy方法移动节点），而LinkedList只需修改目标节点前后节点的next或prev属性即可，因此在效率上LinkedList优于ArrayList。（然而对于插入和删除来说，首先是需要进行查找操作，大体上相当于随机访问，那么如果考虑到这部分，LinkedList未必就优于ArrayList。因此，在选择上，如果你是插入，需要综合考虑再选择）从内存的角度来说，LinkedList更适用于存储较少元素。因为LinkedList里面不仅维护了待插入的元素，还维护了Node的前置Node和后继Node，如果一个LinkedList中的Node非常多，那么LinkedList将比ArrayList更耗费一些内存；并且在访问上，太多的元素会导致查找效率低下。
介绍了LinkedList的基本原理，并介绍了其构造方法和提供的操作，最后对比了ArrayList。
