List在數(shù)據(jù)結(jié)構(gòu)中表現(xiàn)為是線性表的方式，其元素以線性方式存儲，集合中允許存放重復(fù)的對象，List接口主要的實現(xiàn)類有
ArrayList
ArrayList其實就是一組長度可變的數(shù)組，當(dāng)實例化了一個ArrayList，該數(shù)據(jù)也被實例化了，當(dāng)向集合中添加對象時，數(shù)組的大小也隨著改變，這樣它所帶來的有優(yōu)點是快速的隨機訪問，即使訪問每個元素所帶來的性能問題也是很小的，但缺點就是想其中添加或刪除對象速度慢，當(dāng)你創(chuàng)建的數(shù)組是不確定其容量，所以當(dāng)我們改變這個數(shù)組時就必須在內(nèi)存中做很多的處理，如你想要數(shù)組中任意兩個元素中間添加對象，那么在內(nèi)存中數(shù)組要移動所有后面的對象。
LinkedList
LinkedList是通過節(jié)點的連接實現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)，向linkedList中插入或刪除元素的速度是特別快，而隨機訪問的速度相對較慢，這個是由于鏈表本身的性質(zhì)造成的，在鏈表中，每個節(jié)點都包含了前一個節(jié)點的引用，后一個節(jié)點的引用和節(jié)點存儲值，當(dāng)一個新節(jié)點插入式，只需要修改其中相關(guān)的前后關(guān)系節(jié)點引用即可，刪除節(jié)點也是一樣。操作對象只需要改變節(jié)點的鏈接，新節(jié)點可以存放在內(nèi)存的任何位置，但也就是因為如此LinkedList雖然存在get()方法，但是這個方法通過遍歷節(jié)點來定位所以速度很慢。LinkedList還單獨具addFrist(),addLast(),getFrist(),getLast(),removeFirst(),removeLast()方法，這些方法使得LinkedList可以作為堆棧，隊列，和雙隊列來使用。
說白了，ArrayList和LinkedList就是數(shù)據(jù)結(jié)構(gòu)中的順序存儲表和鏈?zhǔn)酱鎯Ρ怼?br />
ArrayList構(gòu)造原理
上面已經(jīng)清楚ArrayList和LinkedList就是數(shù)據(jù)結(jié)構(gòu)的順序表和鏈表(不清楚的翻翻數(shù)據(jù)結(jié)構(gòu)的書)，下面簡單分析一下它們的實現(xiàn)方式。
下表是摘自sum提供的ArrayList的api文檔
ArrayList()
構(gòu)造一個初始容量為 10 的空列表。
ArrayList(Collection<? extends E> c)
構(gòu)造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
ArrayList(int initialCapacity)
構(gòu)造一個具有指定初始容量的空列表。
第一個構(gòu)造函數(shù)是沒有默認構(gòu)建了一個初始容量10的空列表，第二個構(gòu)造函數(shù)是制定collection元素的列表，第三個構(gòu)造函數(shù)是由用戶指定構(gòu)造的列表初始化容量多少，如果使用第一個構(gòu)造函數(shù)則表示默認調(diào)用該參數(shù)為initialCapacity=10來構(gòu)造一個列表對象。
ArrayList源碼稍微進行分析
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
public int size() {
return size;
}
}
可以發(fā)現(xiàn)ArrayList中包含兩個主要的屬性
private transient Object[] elementData;
private int size;
其中elementData[]是列表的實現(xiàn)的核心數(shù)組，我們使用該數(shù)組來存放集合中的數(shù)據(jù)，而我們的構(gòu)造函數(shù)所傳遞的initialCapacity參數(shù)是構(gòu)建該數(shù)組的長度。
在看看size的實現(xiàn)形式，它的作用是返回size的屬性值的大小，我們再看看另外一個構(gòu)造函數(shù)public ArrayList(Collection<? extends E> c)，該構(gòu)造函數(shù)的作用是把另外一個容器對象中的元素放入當(dāng)點的List對象中。首先是通過調(diào)用另外一個容器對象c的size()來設(shè)置當(dāng)前List對象的size屬性的長度大小。接下來就似乎對elementData[]數(shù)組進行初始化，最后通過Arrays.copyOf(U[] original, int newLength, Class<? extends T[]> newType)方法把當(dāng)前容器中的對象都存放進新的數(shù)組elementData，主要就完成了一個列表的創(chuàng)建。
ArrayList容量擴充
還有一個問題就是我們所建立的ArrayList是使用數(shù)組來實現(xiàn)的，但數(shù)組的長度一旦被初始化就不能改變，而我們在給此列表對象添加元素時卻沒有受到長度的限制，所以，ArrayList的elementData屬性一定是存在一個動態(tài)擴充容量的機制，下面把相關(guān)的部分源碼貼出來再做研究
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
protected transient int modCount = 0;
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
看看public boolean add(E e)方法，可以發(fā)現(xiàn)在添加一個元素到容器中的時候，我們會先通過ensureCapacity(size + 1)判斷該數(shù)組是否需要擴充。
public void ensureCapacity(int minCapacity)這個方法是用來判斷當(dāng)前的數(shù)組是否需要擴充，并且該擴充多少。modCount++; 表示當(dāng)前的對象對elementData數(shù)組進行了多少次擴充，清空和移除等操作，相當(dāng)于是一個對當(dāng)前List對象的一個操作記錄數(shù)。
int oldCapacity = elementData.length; 初始化oldCapacity，表示為當(dāng)前elementData數(shù)組的長度。
if (minCapacity > oldCapacity) 判斷minCapacity和oldCapacity誰大，來決定是否需要擴充。
int newCapacity = (oldCapacity * 3)/2 + 1; 擴充的策列是判斷(oldCapacity * 3)/2 + 1和minCapacity兩者之間誰更大，取更大的數(shù)作為擴充后數(shù)組的initialCapacity值，然后使用數(shù)組拷貝的方式，把以前的數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組對象中
如果minCapacity 小于 oldCapacity 就不需要再擴充。
ArrayList刪除元素
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
在看看ArrayList移除元素是怎么實現(xiàn)的，首先判斷需要刪除的index是否在elementData數(shù)組的下標(biāo)內(nèi)，如不存在則拋出IndexOutOfBoundsException。
modCount++; 與擴充元素一個，刪除元素也記下來操作數(shù)。
E oldValue = (E) elementData[index]; 獲取需要刪除元素的對象。
int numMoved = size - index - 1; 獲取需要被刪除元素的下標(biāo)，刪除該元素后，數(shù)組需要在此元素下標(biāo)后的所有對象進行內(nèi)存的移動。
System.arraycopy(elementData, index+1, elementData, index,numMoved);對numMoved后面的所有對象通過copy的方式進行內(nèi)存的移動重新構(gòu)建數(shù)組。
說完ArrayList的實現(xiàn)，再說說linkedList
構(gòu)建雙鏈表(LinkedList)
LinkedList是類似于C語言的雙鏈表，雙鏈表比單鏈表多了一個域，這個雙鏈表就有了三個域，一個域來用存儲數(shù)據(jù)元素，一個用來指向后續(xù)節(jié)點，另一個是指向結(jié)點的直接前驅(qū)節(jié)點。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
public LinkedList() {
header.next = header.previous = header;
}
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類中，定義了三個屬性，分別為E element 表示數(shù)據(jù)與，Entry<E> next為后續(xù)指針域，Entry<E> previous為前驅(qū)指針域。
在LinkedList中定義了一個重要的屬性header，頭結(jié)點，不會納入鏈表的總元素,該節(jié)點的previous是指向最后節(jié)點，next是指向第一節(jié)點。
構(gòu)造函數(shù)LinkedList() 構(gòu)造一個空列表。將header的前驅(qū)指針域和后續(xù)指針域都指向了自己,看到這里可以發(fā)現(xiàn)，next和previous就是一個引用，其實也相等于C里面的指針，不過C不會處理空指針，直接放操作系統(tǒng)處理了，java就直接拋出NullPointerException，根本不讓它破壞系統(tǒng)的機會。
LinkedList元素變動
上面說到了LinkedList的新增和刪除的效率比ArrayList的高，實際上在 鏈表操作這些方法時，只需要改變2個節(jié)點各自的前驅(qū)指針和后續(xù)指針域，而ArrayList是需要移動很多的元素。
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;
}
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;
}
相比ArrayList的add()方法，LinkedList實現(xiàn)起來非常簡單，主要是兩行代碼：
newEntry.previous.next = newEntry;將上一節(jié)點的后續(xù)節(jié)點指向新增的節(jié)點
newEntry.next.previous = newEntry;頭節(jié)點的前驅(qū)節(jié)點指向新增節(jié)點，size和modCount自增記錄。
同樣remove的實現(xiàn)也非常簡單
e.previous.next = e.next;該節(jié)點的后一節(jié)點的后去節(jié)點指向該節(jié)點的后驅(qū)節(jié)點，
e.next.previous = e.previous;該節(jié)點的后一節(jié)點的前驅(qū)節(jié)點指向該節(jié)點的前驅(qū)節(jié)點。
e.next = e.previous = null;把該節(jié)點的前驅(qū)節(jié)點和后驅(qū)節(jié)點全部指向null。
e.element = null;把該節(jié)點的數(shù)據(jù)域設(shè)置為null。
隨機訪問
相比順序表，鏈表的隨機訪問效率要低得多(理論說法，不是絕對)，ArrayList可以根據(jù)索引號進行隨機訪問，而LinkedList則不要遍歷訪問。
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;
}
上列的代碼是對一個鏈表的遍歷，其中包含了一個算法，如果給的索引號小于總節(jié)點數(shù)的一半，則在鏈表的前半部分第一個節(jié)點完進行遍歷，如果給的索引號大于總節(jié)點數(shù)的一半，則從最后一個節(jié)點往前進行遍歷直到索引號。
最后
總結(jié)一下ArrayList和LinkedList的各自特點
1.ArrayList是基于線性表的順序存儲表，LinkedList是基本線性表的鏈表存儲表。
2.對于新增和刪除元素，LinkedList比較占有優(yōu)勢，只需要變前后2個節(jié)點，而ArrayList要移動數(shù)據(jù)。
3.對于隨機訪問來說，ArrayList比較占有優(yōu)勢，可以根據(jù)索引號快速訪問，而LinkedList則需要遍歷集合的元素來定位。
4.而對于迭代操作(iterate)和查找操作(indexOf)，兩者是差不多。
不過上面都是基于理論，具體問題還是要根據(jù)事實進行分析，如ArrayList刪除的元素剛好是隊列的最后一個元素，那么是無需要移動數(shù)據(jù)的，大體我們可以認為需要隨機訪問較多的那么比較適合用ArrayList，如果是插入和刪除(如消息隊列)較多的那么就需要考慮LinkedList。
上面主要是參考了jdk源碼，數(shù)據(jù)結(jié)構(gòu)和一些相關(guān)資料本著好記性不如爛博客的精神記錄下來，希望朋友們?nèi)绻l(fā)覺哪里不對請指出來，虛心請教
----------------------------------------
by 陳于喆
QQ:34174409
Mail: dongbule@163.com