1.List簡介
List接口是Java對線性表（邏輯上的）的特征的抽象莹菱。
2.List接口的實現(xiàn)
2.1ArrayList
最常用的List集合實現(xiàn)凿渊，是一種動態(tài)可增長基于數(shù)組的有序集合。
2.1.1基本特征
①數(shù)據(jù)存儲是基于數(shù)組實現(xiàn)的（默認數(shù)組大小為10）蕊梧；
②添加數(shù)據(jù)時，會首先檢測是否超過數(shù)組容量，如果超過了則需要對數(shù)組進行擴容（擴容采用Arrays.copyOf（）方法音榜，代價很高避免擴容這樣的操作）；
③刪除數(shù)據(jù)時捧弃，需要將刪除點+1位置開始到數(shù)組末尾的數(shù)據(jù)全部向前移動一位赠叼。
④獲取數(shù)據(jù)很快擦囊，根據(jù)數(shù)組下標可以直接獲取。
⑤此實現(xiàn)不是線程安全的嘴办；
2.1.2 ArrayList的實現(xiàn)
2.1.2.1 屬性
private transient Object[] elementData;//存儲元素 transient標識的屬性在序列化時并不會被序列化
private int size;//數(shù)組內(nèi)元素的數(shù)量
2.1.2.2 常用API及特殊API
tip1：因為底層是基于數(shù)組的瞬场，那么自然的在末尾增加移除元素是較容易的，在指定位置插入移除元素就相對的消耗時間了.
tip2：因為底層是基于數(shù)組的涧郊，按下標取元素時間復雜度就是常數(shù)了
2.1.2.2.1 add()系列
public boolean add(E e);//在末尾加入元素
public void add(int index, E element) ;//在指定位置插入元素,包括當前位置元素在內(nèi)以后的元素向右移動（index加1）贯被。
public boolean addAll(int index, Collection<? extends E> c);//在末尾增加元素列表
public boolean addAll(int index, Collection<? extends E> c);//在指定位置插入元素列表
2.1.2.2.2 remove()系列
public boolean remove(Object o);//根據(jù)指針去除元素
public boolean remove(int index);//根據(jù)游標去除元素
public boolean removeAll(Collection<?> c);//去除c內(nèi)包含的元素
2.1.2.2.3 set()系列
public E set(int index, E element);//替換指定位置的元素
2.1.2.2.4 get()系列
public E get(int index);//返回制定位置的元素
2.1.2.2.5 subList(int fromIndex, int toIndex)
public List<E> subList(int fromIndex, int toIndex);
//返回當前List中對于(fromIndex,toIndex)部分的引用
注意：和String.subString()完全不一樣，例如：
ArrayList<Object> objs1= new ArrayList<Object>(100);
objs1.subList(0, 5).clear();//objs1 中下標為0,1,2,3,4的數(shù)據(jù)會變成null妆艘；
2.1.2.2.5 trimToSize()彤灶；
public void trimToSize();//將List的capacity削減到和size大小一致；
2.2LinkedList
LinkedList是List接口基于雙向鏈表的實現(xiàn)批旺，基于鏈表使得LinkedList在插入和刪除時更優(yōu)于ArrayList幌陕，而隨機訪問則比ArrayList遜色些。
2.2.1數(shù)據(jù)結(jié)構(gòu)
2.2.2數(shù)據(jù)結(jié)構(gòu)的代碼描述
transient Node<E> first;//LinkedList的首指針
transient Node<E> last;//LinkedList的尾指針
private static class Node<E> {//節(jié)點
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;
}
}
2.2.2常用API及其實現(xiàn)
2.2.2.1 add()系列：
public boolean 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);//構(gòu)造新節(jié)點
last = newNode;//設(shè)置新節(jié)點為最后的節(jié)點
if (l == null)//如果為新構(gòu)造的空鏈表苞轿，則把首指針也設(shè)置為尾指針
first = newNode;
else
l.next = newNode;//進行鏈接
size++;//元素數(shù)量增加
modCount++;//fast-fail 機制支持
}
objs2.add(index, element)；//在指定下標插入元素,涉及到雙向列表的遍歷
public void add(int index, E element) {
checkPositionIndex(index);//檢測是否查過元素數(shù)量
if (index == size)//如果是在末尾插入逗物，則直接追加
linkLast(element);
else
linkBefore(element, node(index));//在指定位置插入元素
}
//雙向鏈表的遍歷
Node<E> node(int index) {
if (index < (size >> 1)) {//在index小于size的一半時搬卒，從first向后遍歷
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//在index大于size的一半時，從last向前遍歷
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//插入元素e在succ前面
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++;
}
public void addFirst(E e)翎卓；//首部添加
public void addLast(E e);//尾部添加
public boolean addAll(Collection<? extends E> c)契邀；//末尾鏈接集合
public boolean addAll(int index, Collection<? extends E> c)；//在指定位置插入集合失暴，也涉及到index的遍歷坯门，可參考上面兩個來寫，遍歷找到index位置節(jié)點然后循環(huán)追加逗扒，然后鏈接上古戴。
2.2.2.2 clear（）：
public void clear()；//置空雙向鏈表,同時置空每個節(jié)點的首尾指針矩肩，盡管置空節(jié)點的首尾指針比不必要的但是
-helps a generational GC if the discarded nodes inhabit more than one generation
-is sure to free memory even if there is a reachable Iterator
也就是避免 ‘在這個List的某些特定的節(jié)點仍有外部引用指向時现恼，導致的其他節(jié)點不可被清理’ 涉及到分代GC的原理
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
2.2.2.2 clone()鏈表的克隆：
克隆鏈表后把原鏈表的數(shù)據(jù)遍歷加入
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
2.2.2.3 descendingIterator()反向遍歷迭代器：
2.2.2.4 remove()：刪除元素
遍歷查找元素然后將前后兩個節(jié)點鏈接起來即可黍檩。
2.2.3 關(guān)于LinkedList的遍歷性能問題
參看這篇文章 http://blog.csdn.net/u010853261/article/details/54143917
不要使用for循環(huán)叉袍，還是用迭代器吧
2.3Vector
ArrayList的線程安全版本，方法上增加synchronized 實現(xiàn)刽酱。
3.fast-fail機制
在AbstractList類中有modCount這么一個字段喳逛，擴展類ArrayList、LinkedList以及Vector中 在對自身的元素進行更改時均會modCount++操作棵里；
Thread a,b 兩個線程對同一個List實例 listTest通過迭代器迭代（迭代期對象持有一個在自身被創(chuàng)建時listTest的modCount的值）润文，如果a線程進行修改導致了modCount++操作姐呐，b線程在的迭代器modCount未進行改變，則b線程迭代會導致 ConcurrentModificationException();而Java并不保證一定能觸發(fā)转唉，所以還是不要在多線程環(huán)境中使用這些實現(xiàn)或者自己在外部提供同步機制
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
