依赖关系

LinkedList 继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

依赖关系图

java.lang.Object    ↳     java.util.AbstractCollection<E>          ↳     java.util.AbstractList<E>                ↳     java.util.AbstractSequentialList<E>                      ↳     java.util.LinkedList<E>  public class LinkedList<E>     extends AbstractSequentialList<E>     implements List<E>, Deque<E>, Cloneable, java.io.Serializable 

API

LinkedList api

属性

// 实际元素个数 transient int size = 0; // 头节点 transient Node<E> first; // 尾节点 transient Node<E> last; //注意，头节点、尾节点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

内部类

内部类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;     } }

add(E e)添加元素到尾部

public boolean add(E e) {     linkLast(e);     return true; }  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++; }

add(E e)添加元素到尾部图解

add(int index,E e)添加元素到指定位置

public void add(int index, E element) {     checkPositionIndex(index); //检查索引是否处于[0-size]之间      if (index == size)//添加在链表尾部         linkLast(element);     else//添加在链表中间         linkBefore(element, node(index)); }  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++; } 

add(int index,E e)添加元素到指定位置图解

addAll添加集合到指定位置图解

删除和添加相反不做多余解释了。

总结

1、LinkedList 实际上是通过双向链表去实现的，增删效率高，索引效率低。它包含一个非常重要的内部类：Node。Node是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
2、从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
3、LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
4、由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

遍历效率对比实例

import java.util.List; import java.util.Iterator; import java.util.LinkedList; import java.util.NoSuchElementException;  /*  * @desc 测试LinkedList的几种遍历方式和效率  */ public class LinkedListThruTest {     public static void main(String[] args) {         // 通过Iterator遍历LinkedList         iteratorLinkedListThruIterator(getLinkedList()) ;                  // 通过快速随机访问遍历LinkedList         iteratorLinkedListThruForeach(getLinkedList()) ;          // 通过for循环的变种来访问遍历LinkedList         iteratorThroughFor2(getLinkedList()) ;          // 通过PollFirst()遍历LinkedList         iteratorThroughPollFirst(getLinkedList()) ;          // 通过PollLast()遍历LinkedList         iteratorThroughPollLast(getLinkedList()) ;          // 通过removeFirst()遍历LinkedList         iteratorThroughRemoveFirst(getLinkedList()) ;          // 通过removeLast()遍历LinkedList         iteratorThroughRemoveLast(getLinkedList()) ;     }          private static LinkedList getLinkedList() {         LinkedList llist = new LinkedList();         for (int i=0; i<100000; i++)             llist.addLast(i);          return llist;     }     /**      * 通过快迭代器遍历LinkedList      */     private static void iteratorLinkedListThruIterator(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();                  for(Iterator iter = list.iterator(); iter.hasNext();)             iter.next();          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");     }      /**      * 通过快速随机访问遍历LinkedList      */     private static void iteratorLinkedListThruForeach(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();                  int size = list.size();         for (int i=0; i<size; i++) {             list.get(i);                 }         // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorLinkedListThruForeach：" + interval+" ms");     }      /**      * 通过另外一种for循环来遍历LinkedList      */     private static void iteratorThroughFor2(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();                  for (Integer integ:list)              ;          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorThroughFor2：" + interval+" ms");     }      /**      * 通过pollFirst()来遍历LinkedList      */     private static void iteratorThroughPollFirst(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();         while(list.pollFirst() != null)             ;          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorThroughPollFirst：" + interval+" ms");     }      /**      * 通过pollLast()来遍历LinkedList      */     private static void iteratorThroughPollLast(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();         while(list.pollLast() != null)             ;          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorThroughPollLast：" + interval+" ms");     }      /**      * 通过removeFirst()来遍历LinkedList      */     private static void iteratorThroughRemoveFirst(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();         try {             while(list.removeFirst() != null)                 ;         } catch (NoSuchElementException e) {         }          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");     }      /**      * 通过removeLast()来遍历LinkedList      */     private static void iteratorThroughRemoveLast(LinkedList<Integer> list) {         if (list == null)             return ;          // 记录开始时间         long start = System.currentTimeMillis();         try {             while(list.removeLast() != null)                 ;         } catch (NoSuchElementException e) {         }          // 记录结束时间         long end = System.currentTimeMillis();         long interval = end - start;         System.out.println("iteratorThroughRemoveLast：" + interval+" ms");     }  }

输出结果

iteratorLinkedListThruIterator：8 ms iteratorLinkedListThruForeach：3724 ms iteratorThroughFor2：5 ms iteratorThroughPollFirst：8 ms iteratorThroughPollLast：6 ms iteratorThroughRemoveFirst：2 ms iteratorThroughRemoveLast：2 ms

由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。
无论如何，千万不要通过随机访问去遍历LinkedList！