List詳解
| List | 我們需要保留存儲順序胞皱，并且保留重復元素邪意，使用List | |
|---|---|---|
| ArrayList | 查詢較多的時候使用ArrayList | |
| LinkedList | 存取較多的時候使用LinkedList | |
| Vector | 需要保證線程安全的時候使用Vector |
Arraylist： Object數(shù)組
LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán))
Vector： Object數(shù)組
ArrayList
ArrayList 是一個數(shù)組隊列反砌，相當于 動態(tài)數(shù)組雾鬼。與Java中的數(shù)組相比，它的容量能動態(tài)增長宴树。
它繼承于AbstractList策菜，實現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口。
和Vector不同森渐，ArrayList中的操作不是線程安全的做入！所以，建議在單線程中才使用ArrayList同衣，而在多線程中可以選擇Vector或者CopyOnWriteArrayList竟块。
繼承關系
? java.util.AbstractCollection<E>
? java.util.AbstractList<E>
? java.util.ArrayList<E>
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
構造函數(shù)
// 默認構造函數(shù)
ArrayList()
// capacity是ArrayList的默認容量大小。當由于增加數(shù)據(jù)導致容量不足時耐齐，容量會添加上一次容量大小的一半浪秘。
ArrayList(int capacity)
// 創(chuàng)建一個包含collection的ArrayList ArrayList(Collection<? extends E> collection)
底層原理實現(xiàn)
ArrayList包含了兩個重要的對象：elementData 和 size。
transient Object[] elementData;
- elementData 是"Object[]類型的數(shù)組"埠况，它保存了添加到ArrayList中的元素耸携。實際上，elementData是個動態(tài)數(shù)組辕翰，我們能通過構造函數(shù) ArrayList(int initialCapacity)來執(zhí)行它的初始容量為initialCapacity夺衍；如果通過不含參數(shù)的構造函數(shù)ArrayList()來創(chuàng)建ArrayList，則elementData的容量默認是10喜命。elementData數(shù)組的大小會根據(jù)ArrayList容量的增長而動態(tài)的增長沟沙。
private int size;
- size 則是動態(tài)數(shù)組的實際大小河劝。
遍歷方式
- 第一種，通過迭代器遍歷矛紫。
Integer value = null; Iterator iter = list.iterator(); while (iter.hasNext()) { value = (Integer)iter.next(); }
- 第二種赎瞎，隨機訪問，通過索引值去遍歷颊咬。
Integer value = null; int size = list.size(); for (int i=0; i<size; i++) { value = (Integer)list.get(i); }
- 第三種务甥，for循環(huán)遍歷。
Integer value = null; for (Integer integ:list) { value = integ; }
遍歷ArrayList時喳篇，使用隨機訪問(即敞临，通過索引序號訪問)效率最高，而使用迭代器的效率最低杭隙！
API
// Collection中定義的API
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定義的API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
LinkedList
LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表哟绊。它也可以被當作堆棧、隊列或雙端隊列進行操作痰憎。
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 {}
構造函數(shù)
// 默認構造函數(shù)
LinkedList()
// 創(chuàng)建一個LinkedList，保護Collection中的全部元素铣耘。 LinkedList(Collection<? extends E> collection)
底層原理
LinkedList的本質(zhì)是雙向鏈表洽沟。 (01) LinkedList繼承于AbstractSequentialList，并且實現(xiàn)了Dequeue接口蜗细。 (02) LinkedList包含兩個重要的成員：header 和 size裆操。 header是雙向鏈表的表頭，它是雙向鏈表節(jié)點所對應的類Entry的實例炉媒。Entry中包含成員變量： previous, next, element踪区。其中，previous是該節(jié)點的上一個節(jié)點吊骤，next是該節(jié)點的下一個節(jié)點缎岗，element是該節(jié)點所包含的值。 size是雙向鏈表中節(jié)點的個數(shù)白粉。
遍歷方式
- 第一種传泊，通過迭代器遍歷。
for(Iterator iter = list.iterator(); iter.hasNext();) iter.next();
- 通過快速隨機訪問遍歷LinkedList
int size = list.size(); for (int i=0; i<size; i++) { list.get(i); }
- 通過另外一種for循環(huán)來遍歷LinkedList
for (Integer integ:list) ;
- 通過pollFirst()來遍歷LinkedList
while(list.pollFirst() != null) ;
- 通過pollLast()來遍歷LinkedList
while(list.pollLast() != null) ;
- 通過removeFirst()來遍歷LinkedList
try { while(list.removeFirst() != null) ; } catch (NoSuchElementException e) { }
- 通過removeLast()來遍歷LinkedList
try { while(list.removeLast() != null) ; } catch (NoSuchElementException e) { }
遍歷LinkedList時鸭巴，使用removeFist()或removeLast()效率最高眷细。但用它們遍歷時，會刪除原始數(shù)據(jù)鹃祖；若單純只讀取溪椎，而不刪除，應該使用第3種遍歷方式。 無論如何池磁，千萬不要通過隨機訪問去遍歷LinkedList奔害！
API
boolean add(E object)
void add(int location, E object)
boolean addAll(Collection<? extends E> collection)
boolean addAll(int location, Collection<? extends E> collection)
void addFirst(E object)
void addLast(E object)
void clear()
Object clone()
boolean contains(Object object)
Iterator<E> descendingIterator()
E element()
E get(int location)
E getFirst()
E getLast()
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
boolean offer(E o)
boolean offerFirst(E e)
boolean offerLast(E e)
E peek()
E peekFirst()
E peekLast()
E poll()
E pollFirst()
E pollLast()
E pop()
void push(E e)
E remove()
E remove(int location)
boolean remove(Object object)
E removeFirst()
boolean removeFirstOccurrence(Object o)
E removeLast()
boolean removeLastOccurrence(Object o)
E set(int location, E object)
int size()
<T> T[] toArray(T[] contents)
Object[] toArray()
Vector
Vector 是矢量隊列楷兽，它是JDK1.0版本添加的類地熄。繼承于AbstractList，實現(xiàn)了List, RandomAccess, Cloneable這些接口芯杀。
繼承關系
java.lang.Object
? java.util.AbstractCollection<E>
? java.util.AbstractList<E>
? java.util.Vector<E>
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
構造函數(shù)
Vector共有4個構造函數(shù)
// 默認構造函數(shù)
Vector()
// capacity是Vector的默認容量大小端考。當由于增加數(shù)據(jù)導致容量增加時，每次容量會增加一倍揭厚。
Vector(int capacity)
// capacity是Vector的默認容量大小却特，capacityIncrement是每次Vector容量增加時的增量值。
Vector(int capacity, int capacityIncrement)
// 創(chuàng)建一個包含collection的Vector
Vector(Collection<? extends E> collection)
底層原理
Vector的數(shù)據(jù)結構和ArrayList差不多筛圆，它包含了3個成員變量：elementData , elementCount裂明， capacityIncrement。
(01) elementData 是"Object[]類型的數(shù)組"太援，它保存了添加到Vector中的元素闽晦。elementData是個動態(tài)數(shù)組，如果初始化Vector時提岔，沒指定動態(tài)數(shù)組的>大小仙蛉，則使用默認大小10。隨著Vector中元素的增加碱蒙，Vector的容量也會動態(tài)增長荠瘪，capacityIncrement是與容量增長相關的增長系數(shù)，具體的增長方式赛惩，請參考源碼分析中的ensureCapacity()函數(shù)哀墓。
(02) elementCount 是動態(tài)數(shù)組的實際大小。
(03) capacityIncrement 是動態(tài)數(shù)組的增長系數(shù)喷兼。如果在創(chuàng)建Vector時篮绰，指定了capacityIncrement的大小褒搔；則阶牍，每次當Vector中動態(tài)數(shù)組容量增加時>，增加的大小都是capacityIncrement星瘾。
遍歷方式
- 第一種走孽，通過迭代器遍歷。
Integer value = null; int size = vec.size(); for (int i=0; i<size; i++) { value = (Integer)vec.get(i); }
- 第二種琳状，隨機訪問磕瓷，通過索引值去遍歷。
Integer value = null; int size = vec.size(); for (int i=0; i<size; i++) { value = (Integer)vec.get(i); }
- 第三種，另一種for循環(huán)困食。
Integer value = null; for (Integer integ:vec) { value = integ; }
- 第四種边翁，Enumeration遍歷。
Integer value = null; Enumeration enu = vec.elements(); while (enu.hasMoreElements()) { value = (Integer)enu.nextElement(); }
總結：遍歷Vector硕盹，使用索引的隨機訪問方式最快符匾，使用迭代器最慢。
API
synchronized boolean add(E object)
void add(int location, E object)
synchronized boolean addAll(Collection<? extends E> collection)
synchronized boolean addAll(int location, Collection<? extends E> collection)
synchronized void addElement(E object)
synchronized int capacity()
void clear()
synchronized Object clone()
boolean contains(Object object)
synchronized boolean containsAll(Collection<?> collection)
synchronized void copyInto(Object[] elements)
synchronized E elementAt(int location)
Enumeration<E> elements()
synchronized void ensureCapacity(int minimumCapacity)
synchronized boolean equals(Object object)
synchronized E firstElement()
E get(int location)
synchronized int hashCode()
synchronized int indexOf(Object object, int location)
int indexOf(Object object)
synchronized void insertElementAt(E object, int location)
synchronized boolean isEmpty()
synchronized E lastElement()
synchronized int lastIndexOf(Object object, int location)
synchronized int lastIndexOf(Object object)
synchronized E remove(int location)
boolean remove(Object object)
synchronized boolean removeAll(Collection<?> collection)
synchronized void removeAllElements()
synchronized boolean removeElement(Object object)
synchronized void removeElementAt(int location)
synchronized boolean retainAll(Collection<?> collection)
synchronized E set(int location, E object)
synchronized void setElementAt(E object, int location)
synchronized void setSize(int length)
synchronized int size()
synchronized List<E> subList(int start, int end)
synchronized <T> T[] toArray(T[] contents)
synchronized Object[] toArray()
synchronized String toString()
synchronized void trimToSize()
參考文獻：
