List詳解（ArrayList、LinkedList、Vector）

List詳解

List 我們需要保留存儲(chǔ)順序，并且保留重復(fù)元素，使用List
ArrayList 查詢較多的時(shí)候使用ArrayList
LinkedList 存取較多的時(shí)候使用LinkedList
Vector 需要保證線程安全的時(shí)候使用Vector

  • Arraylist： Object數(shù)組

  • LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán))

  • Vector： Object數(shù)組

ArrayList

ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于 動(dòng)態(tài)數(shù)組。與Java中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)。

它繼承于AbstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

和Vector不同，ArrayList中的操作不是線程安全的！所以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。

繼承關(guān)系

? 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 {}

構(gòu)造函數(shù)

// 默認(rèn)構(gòu)造函數(shù)  
ArrayList()
// capacity是ArrayList的默認(rèn)容量大小。當(dāng)由于增加數(shù)據(jù)導(dǎo)致容量不足時(shí)，容量會(huì)添加上一次容量大小的一半。  
ArrayList(int capacity)
// 創(chuàng)建一個(gè)包含collection的ArrayList  ArrayList(Collection<? extends E> collection)

底層原理實(shí)現(xiàn)

ArrayList包含了兩個(gè)重要的對(duì)象：elementData 和 size。

transient Object[] elementData;
  • elementData 是"Object[]類型的數(shù)組"，它保存了添加到ArrayList中的元素。實(shí)際上，elementData是個(gè)動(dòng)態(tài)數(shù)組，我們能通過(guò)構(gòu)造函數(shù) ArrayList(int initialCapacity)來(lái)執(zhí)行它的初始容量為initialCapacity；如果通過(guò)不含參數(shù)的構(gòu)造函數(shù)ArrayList()來(lái)創(chuàng)建ArrayList，則elementData的容量默認(rèn)是10。elementData數(shù)組的大小會(huì)根據(jù)ArrayList容量的增長(zhǎng)而動(dòng)態(tài)的增長(zhǎng)。
private int size;
  • size 則是動(dòng)態(tài)數(shù)組的實(shí)際大小。

遍歷方式

  • 第一種，通過(guò)迭代器遍歷。
    Integer value = null;  Iterator iter = list.iterator();  while (iter.hasNext()) {  value = (Integer)iter.next();  }
  • 第二種，隨機(jī)訪問(wèn)，通過(guò)索引值去遍歷。 
    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時(shí)，使用隨機(jī)訪問(wèn)(即，通過(guò)索引序號(hào)訪問(wèn))效率最高，而使用迭代器的效率最低！

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 是一個(gè)繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。

LinkedList 是非同步的。

繼承關(guān)系

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 {}

構(gòu)造函數(shù)

// 默認(rèn)構(gòu)造函數(shù)  
LinkedList()
// 創(chuàng)建一個(gè)LinkedList，保護(hù)Collection中的全部元素。  LinkedList(Collection<? extends E> collection)

底層原理

LinkedList的本質(zhì)是雙向鏈表。 (01) LinkedList繼承于AbstractSequentialList，并且實(shí)現(xiàn)了Dequeue接口。 (02) LinkedList包含兩個(gè)重要的成員：header 和 size。 header是雙向鏈表的表頭，它是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的類Entry的實(shí)例。Entry中包含成員變量： previous, next, element。其中，previous是該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，next是該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，element是該節(jié)點(diǎn)所包含的值。 　　size是雙向鏈表中節(jié)點(diǎn)的個(gè)數(shù)。

遍歷方式

  • 第一種，通過(guò)迭代器遍歷。
for(Iterator iter = list.iterator(); iter.hasNext();)  iter.next();
  • 通過(guò)快速隨機(jī)訪問(wèn)遍歷LinkedList
int size = list.size();  for (int i=0; i<size; i++) {  list.get(i); }
  • 通過(guò)另外一種for循環(huán)來(lái)遍歷LinkedList
for (Integer integ:list) ;
  • 通過(guò)pollFirst()來(lái)遍歷LinkedList
while(list.pollFirst() != null)  ;
  • 通過(guò)pollLast()來(lái)遍歷LinkedList
while(list.pollLast() != null)  ;
  • 通過(guò)removeFirst()來(lái)遍歷LinkedList
try {  while(list.removeFirst() != null)  ;  } catch (NoSuchElementException e) {  }
  • 通過(guò)removeLast()來(lái)遍歷LinkedList
try {  while(list.removeLast() != null)  ;  } catch (NoSuchElementException e) {  }

遍歷LinkedList時(shí)，使用removeFist()或removeLast()效率最高。但用它們遍歷時(shí)，會(huì)刪除原始數(shù)據(jù)；若單純只讀取，而不刪除，應(yīng)該使用第3種遍歷方式。 無(wú)論如何，千萬(wàn)不要通過(guò)隨機(jī)訪問(wèn)去遍歷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 是矢量隊(duì)列，它是JDK1.0版本添加的類。繼承于AbstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable這些接口。

繼承關(guān)系

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 {}

構(gòu)造函數(shù)

Vector共有4個(gè)構(gòu)造函數(shù)  
// 默認(rèn)構(gòu)造函數(shù)  
Vector()
// capacity是Vector的默認(rèn)容量大小。當(dāng)由于增加數(shù)據(jù)導(dǎo)致容量增加時(shí)，每次容量會(huì)增加一倍。  
Vector(int capacity)
// capacity是Vector的默認(rèn)容量大小，capacityIncrement是每次Vector容量增加時(shí)的增量值。  
Vector(int capacity, int capacityIncrement)
// 創(chuàng)建一個(gè)包含collection的Vector  
Vector(Collection<? extends E> collection)

底層原理

Vector的數(shù)據(jù)結(jié)構(gòu)和ArrayList差不多，它包含了3個(gè)成員變量：elementData , elementCount， capacityIncrement。

(01) elementData 是"Object[]類型的數(shù)組"，它保存了添加到Vector中的元素。elementData是個(gè)動(dòng)態(tài)數(shù)組，如果初始化Vector時(shí)，沒(méi)指定動(dòng)態(tài)數(shù)組的>大小，則使用默認(rèn)大小10。隨著Vector中元素的增加，Vector的容量也會(huì)動(dòng)態(tài)增長(zhǎng)，capacityIncrement是與容量增長(zhǎng)相關(guān)的增長(zhǎng)系數(shù)，具體的增長(zhǎng)方式，請(qǐng)參考源碼分析中的ensureCapacity()函數(shù)。

(02) elementCount 是動(dòng)態(tài)數(shù)組的實(shí)際大小。

(03) capacityIncrement 是動(dòng)態(tài)數(shù)組的增長(zhǎng)系數(shù)。如果在創(chuàng)建Vector時(shí)，指定了capacityIncrement的大?。粍t，每次當(dāng)Vector中動(dòng)態(tài)數(shù)組容量增加時(shí)>，增加的大小都是capacityIncrement。

遍歷方式

  • 第一種，通過(guò)迭代器遍歷。
Integer value = null;  int size = vec.size();  for (int i=0; i<size; i++) {  value = (Integer)vec.get(i); }
  • 第二種，隨機(jī)訪問(wèn)，通過(guò)索引值去遍歷。
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();  }

總結(jié)：遍歷Vector，使用索引的隨機(jī)訪問(wèn)方式最快，使用迭代器最慢。

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()

參考文獻(xiàn)：

Java 集合系列目錄(Category)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容