public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable
List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
LinkedList就是一个链表，其底层使用了双向链表来实现。
LinkedList的两个构造函数实现：
Entry作为节点，构造函数创建了一个空的双向链表。而带参数的构造函数则先调用了不带参数的构造函数，然后将传过来的集合里的元素都添加到链表里。
private transient Entryheader = new Entry (null, null, null); private transient int size = 0; /** * Constructs an empty list. */ public LinkedList() { header.next = header.previous = header; } /** * 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 c) { this(); addAll(c); }
Entry作为链表节点，其实现如下：
Entry作为LinkedList的一个内部类实现。Entry实现了Node功能，element存放数据信息，next指向下一个节点，previous指向前一个节点。其构造函数中实现了数据赋值，和节点指向。
private static class Entry{ E element; Entry next; Entry previous; Entry(E element, Entry next, Entry previous) { this.element = element; this.next = next; this.previous = previous; } }
LinkedList的add方法：
LinkedList的add方法调用了addBefore方法，并将header传入。在addBefore中先创建了一个Entry节点，然后修改指针指向。完全都是双向链表的操作。而在指定位置添加也是调用addBefore方法，只是没有直接传递header节点，而是传递了要添加位置的节点。
/** * Appends the specified element to the end of this list. * *This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return true (as specified by {@link Collection#add}) */ public boolean add(E e) { addBefore(e, header); return true; } /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } private Entry
addBefore(E e, Entry entry) { Entry newEntry = new Entry (e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
获取数据元素：
LinkedList适合挨个遍历元素，即使指定了位置查询，也需要挨个遍历，因为它只知道链表的头header位置，要通过header去寻找其他节点，比如下面的getFirst和getLast方法是最简单的，直接使用header就可以找到。但指定位置的get方法则需要调用entry定位节点的方法来实现，上面添加元素到指定位置时也需要调用entry方法来找到指定位置的节点。entry方法也是通过header来挨个遍历寻找节点。
public E get(int index) { return entry(index).element; } public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; } public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; } /** * Returns the indexed entry. */ private Entry entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }