??????? LinkedList是List 接口的链接列表实现。实现List接口所有可选的列表操作，并且允许添加任何元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法（如：getFirst、removeLast等）。这些操作允许将链接列表用作堆栈、队列或双端队列。
??????? LinkedList还实现了 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
??????? 注意，LinkedList不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须保持外部同步。（结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));
?
??????? LinkedList的 iterator 和 listIterator 方法返回的迭代器是快速失败（fail-fast）的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。
??????? 所谓fail-fast是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
??????? 例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
??????? 同样的我们从LinkedList的源码深入来分析LinkedList的结构及应用场景：
?
??????? 1.LinkedList的成员变量
??????? 与ArrayList相同LinkedList依旧只有两个成员变量：
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0; //列表大小
??????? 既然LinkedList是一个链表实现，那么header必然就是这个链表的头部，其中Entry即为节点对象。
??????? size与ArrayList实现一样是这个列表的大小（元素个数）。
?
??????? 2.Entry节点元素
??????? 与ArrayList不同，LinkedList的内部是利用Entry这个内部类来实现的，下面是Entry源代码：
private static class Entry<E> {
//当前元素
E element;
//下一个元素
Entry<E> next;
//上一个元素
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
??????? Entry类只定义了三个属性：previous（前一个元素）、element（当前元素）、next（后一个元素）。这样获取到当前位置节点元素后就可以很容易的找到它之前和之后的两个节点，这样在不同的Entry间就建立了联系，从而就实现了双向的链表结构。
List list=new LinkedList();??????? 实例化时会调用LinkedList的默认构造方法：
/**
* 构建一个空的list实例
*/
public LinkedList() {
header.next = header.previous = header;
}
??????? 默认构造方法不接受任何参数，只是将header节点的前一节点和后一节点都设置为自身，这样整个链表其实就只有header一个节点，用于表示一个空的链表。
list.add("元素一");
/**
* 添加指定元素至此list尾部
*/
public boolean add(E e) {
addBefore(e, header);
return true;
}
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;
}
???????? add方法中并没有实际处理的逻辑，而是调用的另一个私有方法addBefore(e, header)，其中E e参数为要添加的元素，Entry<E> entry为header。
/**
* 返回指定位置元素
*/
public E get(int index) {
return entry(index).element;
}
/**
* 返回指定位置元素
*/
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;
}
?/**
* 移除指定位置元素
*/
public E remove(int index) {
return remove(entry(index));
}
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;
}
??????? remove方法调用了两个相关其他方法，一个是根据index返回指定位置元素的Entry<E> entry(int index)方法，另一个是删除指定元素的方法E remove(Entry<E> e)。
E pop()
从此列表所表示的堆栈处弹出一个元素。
void push(E e)
将元素推入此列表所表示的堆栈。
LinkedList list = new LinkedList();
list.push("栈帧1");
list.push("栈帧2");
list.push("栈帧3");
list.push("栈帧4");
for (int i = 0, j = list.size(); i < j; i++) {
System.out.println("entry:"+list.pop());
System.out.println("size :"+list.size());
}
//打印结果
entry:栈帧4
size :3
entry:栈帧3
size :2
entry:栈帧2
size :1
entry:栈帧1
size :0
boolean offer(E e)
将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
E peek()
获取但不移除此队列的头；如果此队列为空，则返回 null。
E poll()
获取并移除此队列的头，如果此队列为空，则返回 null。
??????? 所以我们可以利用这几个相关方法结合LinkedList来实现一个队列结构：LinkedList list = new LinkedList();
list.offer("成员1");
list.offer("成员2");
list.offer("成员3");
list.offer("成员4");
for (int i = 0, j = list.size(); i < j; i++) {
System.out.println("entry:" + list.peek());
System.out.println("size :" + list.size());
}
for (int i = 0, j = list.size(); i < j; i++) {
System.out.println("entry:" + list.poll());
System.out.println("size :" + list.size());
}
// 打印结果
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :3
entry:成员2
size :2
entry:成员3
size :1
entry:成员4
size :0
原文：http://286.iteye.com/blog/2181299