LinkedList就传说中的双向循环链表了。是List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
链表操作优点：1.因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可
缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。
但是在3，4W条数据下，JDK中的ArrayList何LinkedList在添加数据时的性能，其实几乎是没有差异的。
List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
注意，此实现不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须 保持外部同步。（结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));
此类的 iterator 和 listIterator 方法返回的迭代器是快速失败 的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何硬性保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
LinkedList的声明
[java] view plaincopyprint?
- publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>,Deque<E>/*这是双端队列接口，这个接口扩展了Queue接口，提供了更多的方法，比如push,pop等*/,Cloneable,java.io.Serializable
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>/*这是双端队列接口，这个接口扩展了Queue接口，提供了更多的方法，比如push,pop等*/, Cloneable, java.io.Serializable
所以LinkedList可以被用作Stack,Queue和Deque
来看一下链表结点的 定义
[java] view plaincopyprint?
- privatestaticclassEntry<E>{Eelement;Entry<E>next;Entry<E>previous;//由此可以看出LinkedList是一个双向链表Entry(Eelement,Entry<E>next,Entry<E>previous){this.element=element;this.next=next;this.previous=previous;}
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; //由此可以看出LinkedList是一个双向链表 Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; }
LinkedList中声明了下面两个实例变量：
//头结点，起标记作用，并不记录元素
private transient Entry<E> header = new Entry<E>(null,null, null);
//链表的大小 ，即链表中元素的个数
private transient int size = 0;
我们可以看到这两个 就是都被声明成了transient，所以在序列化的过程中会忽略它们，但是LinkedList提供的序列化方法writeObject(java.io.ObjectOutputStream s)中却序列化了size，并且将除header之外的所有结点都 写到序列化文件中了，那为什么要把size声明成transient呢，不解。。求解释。。
几个重要的方法：
[java] view plaincopyprint?
- /***Returnstheindexedentry.根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历*/privateEntry<E>entry(intindex){if(index<0||index>=size)thrownewIndexOutOfBoundsException("Index:"+index+",Size:"+size);Entry<E>e=header;if(index<(size>>1)){//如果较靠近有表头for(inti=0;i<=index;i++)e=e.next;}else{//较靠近表尾for(inti=size;i>index;i–)e=e.previous;}returne;}
/** * Returns the indexed entry.根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历 */ private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> 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;}
[java] view plaincopyprint?
- /***将元素e添加到entry结点之前*/privateEntry<E>addBefore(Ee,Entry<E>entry){Entry<E>newEntry=newEntry<E>(e,entry,entry.previous);newEntry.previous.next=newEntry;//将新结点与前后结点相连接newEntry.next.previous=newEntry;size++;modCount++;returnnewEntry;}/***删除给定的结点e*/privateEremove(Entry<E>e){if(e==header)thrownewNoSuchElementException();Eresult=e.element;e.previous.next=e.next;e.next.previous=e.previous;e.next=e.previous=null;e.element=null;size–;modCount++;returnresult;}/***从表头开始遍历，返回此元素在表中的第一个位置*/publicintindexOf(Objecto){intindex=0;if(o==null){//如果传入的元素是null，则不能调用eqauls方法进行比较for(Entrye=header.next;e!=header;e=e.next){if(e.element==null)returnindex;index++;}}else{for(Entrye=header.next;e!=header;e=e.next){if(o.equals(e.element))returnindex;index++;}}return-1;}/***默认的添加动作，可以看到这个方法是把新元素添加到表尾*/publicbooleanadd(Ee){addBefore(e,header);//加到头结点之前，即表尾returntrue;}/***默认的删除动作是删除链表的第一个元素，所以说在默认情况下，LinkedList其实扮*演的是一个队列的角色*/publicEremove(){returnremoveFirst();}/***返回第一个元素*/publicEpeek(){if(size==0)returnnull;returngetFirst();}
/** *将元素e添加到entry结点之前 */private Entry<E> addBefore(E e, Entry<E> entry) {Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry; //将新结点与前后结点相连接 newEntry.next.previous = newEntry;size++;modCount++;return newEntry; }/***删除给定的结点e*/ private E remove(Entry<E> e) {if (e == header) throw new NoSuchElementException(); E result = e.element;e.previous.next = e.next;e.next.previous = e.previous; e.next = e.previous = null; e.element = null;size--;modCount++; return result; }/** *从表头开始遍历，返回此元素在表中的第一个位置 */ public int indexOf(Object o) { int index = 0; if (o==null) { //如果传入的元素是null，则不能调用 eqauls方法进行比较 for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; }/***默认的添加动作，可以看到这个方法是把新元素添加 到表尾*/public boolean add(E e) {addBefore(e, header); //加到头结点之前 ，即表尾 return true; }/***默认的删除动作是删除链表的第一个元素，所以说在默认情况下，LinkedList其实扮*演的是一个队列的角色*/public E remove() { return removeFirst(); }/***返回第一个元素*/public E peek() { if (size==0) return null; return getFirst(); }
可以看出，如果表为空的时候 ，这个方法并不会抛出异常，而是返回null，而传统的（在Collections中声明的）方法则会抛出异常。相似的方法还有：poll,但请注意pop方法在表空的时候 会抛出异常。
还有一点请注意，如果先返回list的Iterator，之后 又对链表进行了添加删除修改操作，那么如果再使用返回的那个Iterator就会抛出ConcurrentModificationException。
最后看一下LinkedList是如何序列化和反序列化的，如果对这两个反序列化中用到的这两个回调方法有疑问的，可以看我的这篇博客http://blog.csdn.net/moreevan/article/details/6697777
[java] view plaincopyprint?
- /***Savethestateofthis<tt>LinkedList</tt>instancetoastream(that*is,serializeit).**@serialDataThesizeofthelist(thenumberofelementsit*contains)isemitted(int),followedbyallofits*elements(eachanObject)intheproperorder.*/privatevoidwriteObject(java.io.ObjectOutputStreams)throwsjava.io.IOException{//Writeoutanyhiddenserializationmagics.defaultWriteObject();//Writeoutsizes.writeInt(size);//Writeoutallelementsintheproperorder.for(Entrye=header.next;e!=header;e=e.next)s.writeObject(e.element);}/***Reconstitutethis<tt>LinkedList</tt>instancefromastream(thatis*deserializeit).*/privatevoidreadObject(java.io.ObjectInputStreams)throwsjava.io.IOException,ClassNotFoundException{//Readinanyhiddenserializationmagics.defaultReadObject();//Readinsizeintsize=s.readInt();//Initializeheaderheader=newEntry<E>(null,null,null);header.next=header.previous=header;//Readinallelementsintheproperorder.for(inti=0;i<size;i++)addBefore((E)s.readObject(),header);}
/** * Save the state of this <tt>LinkedList</tt> instance to a stream (that * is, serialize it). * * @serialData The size of the list (the number of elements it * contains) is emitted (int), followed by all of its * elements (each an Object) in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject(); // Write out size s.writeInt(size);// Write out all elements in the proper order. for (Entry e = header.next; e != header; e = e.next) s.writeObject(e.element); } /** * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject(); // Read in size int size = s.readInt(); // Initialize header header = new Entry<E>(null, null, null); header.next = header.previous = header;// Read in all elements in the proper order.for (int i=0; i<size; i++) addBefore((E)s.readObject(), header); }
综上 ，我们可以看出。LinkedList是一个双向链表，它可以被当成栈，队列或双端队列来使用。它也提供 了随机访问元素的方法，不过这个访问的时间复杂度并不像ArrayList是O（1），而是O（n）。它删除给定位置的元素
的效率其实并不比ArrayList高。但它删除特定元素的效率 要比ArrayList高。
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
