说明：本文基于jdk1.7源码
LinkedList 是一个双向链表，它也可以被当作栈、队列(Queue)或双端队列(Deque)进行操作。LinkedList随机访问效率低，但随机插入和删除效率高。
LinkedList是基于链表实现的，链表中节点定义如下。
Node
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; } }
每个节点由prev指针，next指针，item元素组成。
属性
//元素个数 transient int size = 0; //头节点 transient Node<E> first; //尾节点 transient Node<E> last;
构造器
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
add方法
LinkedList基于index的操作需要先通过node(index)定位index处的节点，然后再进行相应的操作。
以add(int index,E element)为例：
/** * 在指定位置插入元素 */ public void add(int index, E element) { checkPositionIndex(index); //如果尾部插入 if (index == size) linkLast(element); else //先定位到index处的节点，再将element插入到该节点前 linkBefore(element, node(index)); } Node<E> node(int index) { // assert isElementIndex(index); // 若index<size/2，在链表前半段查找，从前往后 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else {// 若index>=size/2在链表后半段查找，从后往前 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 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++; }
node(int index)方法在定位index时，使用了二分查找思想，只不过只是二分了一次。通过将index与size/2比较，可得知index在链表的前半段还是后半段，然后在那半段中继续使用for循环依次查找。
定位到位置后，只需要将对应的链断开，将新节点重新链接到链表中就完成了插入。而相比ArrayList，在插入时，需要进行元素的移位操作。所以我们常说链表适合快速的插入和删除操作，正是少了移动元素的过程，因此相比效率较高。
总结
LinkedList底层使用链表实现。插入和移除操作速度快，随机访问速度慢。
1.为什么LinkedList插入和删除操作速度快？
与ArrayList相比，LinkedList插入和删除操作速度快是因为少了元素的移动过程，只需要将该断开的链断开，该连接的链链接上即可。
2.为什么LinkedList随机访问速度慢？
随机访问速度慢是因为LinkedList不像ArrayList有下标index可以直接定位元素，而是要先通过二分确定index在链表前半段还是后半段，然后再在对应的那半段中通过for循环定位。