1、基本用法

ArrayList是一個(gè)泛型容器，新建ArrayList需要實(shí)例化泛型參數(shù)，比如：

ArrayList<Integer> intList = new ArrayList<Integer>();
ArrayList<String> strList = new ArrayList<String>();

ArrayList的主要方法有：

public boolean add(E e) //添加元素到末尾
public boolean isEmpty() //判斷是否為空
public int size() //獲取長度
public E get(int index) //訪問指定位置的元素
public int indexOf(Object o) //查找元素， 如果找到，返回索引位置，否則返回-1
public int lastIndexOf(Object o) //從后往前找
public boolean contains(Object o) //是否包含指定元素，依據(jù)是equals方法的返回值
public E remove(int index) //刪除指定位置的元素， 返回值為被刪對(duì)象
//刪除指定對(duì)象，只刪除第一個(gè)相同的對(duì)象，返回值表示是否刪除了元素
//如果o為null，則刪除值為null的元素
public boolean remove(Object o)
public void clear() //刪除所有元素
//在指定位置插入元素，index為0表示插入最前面，index為ArrayList的長度表示插到最后面
public void add(int index, E element)
public E set(int index, E element) //修改指定位置的元素內(nèi)容

這些方法簡單直接，就不多解釋了，我們看個(gè)簡單示例：

ArrayList<String> strList = new ArrayList<String>();
strList.add("老馬");
strList.add("編程");
for(int i=0; i<strList.size(); i++){
    System.out.println(strList.get(i));
}

2、基本原理

可以看出，ArrayList的基本用法是比較簡單的，它的基本原理也是比較簡單的。Array-List的內(nèi)部有一個(gè)數(shù)組elementData，一般會(huì)有一些預(yù)留的空間，有一個(gè)整數(shù)size記錄實(shí)際的元素個(gè)數(shù)（基于Java 7）?，如下所示：

private transient Object[] elementData;
private int size;

我們暫時(shí)可以忽略transient這個(gè)關(guān)鍵字。各種public方法內(nèi)部操作的基本都是這個(gè)數(shù)組和這個(gè)整數(shù)，elementData會(huì)隨著實(shí)際元素個(gè)數(shù)的增多而重新分配，而size則始終記錄實(shí)際的元素個(gè)數(shù)。

下面，我們具體來看下add和remove方法的實(shí)現(xiàn)。add方法的主要代碼為：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

它首先調(diào)用ensureCapacityInternal確保數(shù)組容量是夠的，ensureCapacityInternal的代碼是：

private void ensureCapacityInternal(int minCapacity) {
    if(elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

它先判斷數(shù)組是不是空的，如果是空的，則首次至少要分配的大小為DEFAULT_CAPACITY,DEFAULT_CAPACITY的值為10，接下來調(diào)用ensureExplicitCapacity，主要代碼為：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if(minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount++是什么意思呢？modCount表示內(nèi)部的修改次數(shù)，modCount++當(dāng)然就是增加修改次數(shù)，為什么要記錄修改次數(shù)呢？我們待會(huì)解釋。

如果需要的長度大于當(dāng)前數(shù)組的長度，則調(diào)用grow方法，其主要代碼為：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //右移一位相當(dāng)于除2，所以，newCapacity相當(dāng)于oldCapacity的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果擴(kuò)展1.5倍還是小于minCapacity，就擴(kuò)展為minCapacity
    if(newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

代碼中已有注釋說明，不再贅述。我們?cè)賮砜磖emove方法的代碼：

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1; //計(jì)算要移動(dòng)的元素個(gè)數(shù)
    if(numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //將size減1，同時(shí)釋放引用以便原對(duì)象被垃圾回收
    return oldValue;
}

它也增加了modCount，然后計(jì)算要移動(dòng)的元素個(gè)數(shù)，從index往后的元素都往前移動(dòng)一位，實(shí)際調(diào)用System.arraycopy方法移動(dòng)元素。elementData[–size]= null；這行代碼將size減1，同時(shí)將最后一個(gè)位置設(shè)為null，設(shè)為null后不再引用原來對(duì)象，如果原來對(duì)象也不再被其他對(duì)象引用，就可以被垃圾回收。

其他方法大多是比較簡單的，我們就不贅述了。上面的代碼中，為便于理解，我們刪減了一些邊界情況處理的代碼，完整代碼要晦澀復(fù)雜一些，但接口一般都是簡單直接的，這就是使用容器類的好處，這也是計(jì)算機(jī)程序中的基本思維方式，封裝復(fù)雜操作，提供簡化接口。

3、迭代

理解了ArrayList的基本用法和原理，接下來，我們來看一個(gè)ArrayList的常見操作：迭代。我們看一個(gè)迭代操作的例子，循環(huán)打印ArrayList中的每個(gè)元素，ArrayList支持foreach語法：

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(123);
intList.add(456);
intList.add(789);
for(Integer a : intList){
    System.out.println(a);
}

當(dāng)然，這種循環(huán)也可以使用如下代碼實(shí)現(xiàn)：

for(int i=0; i<intList.size(); i++){
    System.out.println(intList.get(i));
}

不過，foreach看上去更為簡潔，而且它適用于各種容器，更為通用。

這種foreach語法背后是怎么實(shí)現(xiàn)的呢？其實(shí)，編譯器會(huì)將它轉(zhuǎn)換為類似如下代碼：

Iterator<Integer> it = intList.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

接下來，我們解釋其中的代碼。

3.1、 迭代器接口

ArrayList實(shí)現(xiàn)了Iterable接口，Iterable表示可迭代，Java7中的定義為：

public interface Iterable<T> {
    Iterator<T> iterator();
}

定義很簡單，就是要求實(shí)現(xiàn)iterator方法。iterator方法的聲明為：

        public Iterator<E> iterator()

它返回一個(gè)實(shí)現(xiàn)了Iterator接口的對(duì)象，Java 7中Iterator 接口的定義為：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

hasNext()判斷是否還有元素未訪問，next()返回下一個(gè)元素，remove()刪除最后返回的元素，只讀訪問的基本模式類似于：

Iterator<Integer> it = intList.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

我們待會(huì)再看迭代中間要?jiǎng)h除元素的情況。
只要對(duì)象實(shí)現(xiàn)了Iterable接口，就可以使用foreach語法，編譯器會(huì)轉(zhuǎn)換為調(diào)用Iterable和Iterator接口的方法。初次見到Iterable和Iterator，可能會(huì)比較容易混淆，我們?cè)俪吻逡幌拢?/p>

• Iterable表示對(duì)象可以被迭代，它有一個(gè)方法iterator()，返回Iterator對(duì)象，實(shí)際通過Iterator接口的方法進(jìn)行遍歷；
• 如果對(duì)象實(shí)現(xiàn)了Iterable，就可以使用foreach語法；
• 類可以不實(shí)現(xiàn)Iterable，也可以創(chuàng)建Iterator對(duì)象。

需要了解的是，Java 8對(duì)Iterable添加了默認(rèn)方法forEach和spliterator，對(duì)Iterator增加了默認(rèn)方法forEachRemaining和remove，具體可參見API文檔。

3.2、ListIterator

除了iterator(), ArrayList還提供了兩個(gè)返回Iterator接口的方法：

public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)

ListIterator擴(kuò)展了Iterator接口，增加了一些方法，向前遍歷、添加元素、修改元素、返回索引位置等，添加的方法有：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E e);
    void add(E e);
}

listIterator()方法返回的迭代器從0開始，而listIterator(int index)方法返回的迭代器從指定位置index開始。比如，從末尾往前遍歷，代碼為：

public void reverseTraverse(List<Integer> list){
    ListIterator<Integer> it = list.listIterator(list.size());
    while(it.hasPrevious()){
        System.out.println(it.previous());
    }
}

3.3、迭代的陷阱

關(guān)于迭代器，有一種常見的誤用，就是在迭代的中間調(diào)用容器的刪除方法。比如，要?jiǎng)h除一個(gè)整數(shù)ArrayList中所有小于100的數(shù)，直覺上，代碼可以這么寫：

public void remove(ArrayList<Integer> list){
    for(Integer a : list){
        if(a<=100){
            list.remove(a);
        }
    }
}

但運(yùn)行時(shí)會(huì)拋出異常：

java.util.ConcurrentModificationException

發(fā)生了并發(fā)修改異常，為什么呢？因?yàn)榈鲀?nèi)部會(huì)維護(hù)一些索引位置相關(guān)的數(shù)據(jù)，要求在迭代過程中，容器不能發(fā)生結(jié)構(gòu)性變化，否則這些索引位置就失效了。所謂結(jié)構(gòu)性變化就是添加、插入和刪除元素，只是修改元素內(nèi)容不算結(jié)構(gòu)性變化。

如何避免異常呢？可以使用迭代器的remove方法，如下所示：

public static void remove(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        if(it.next()<=100){
            it.remove();
        }
    }
}

迭代器如何知道發(fā)生了結(jié)構(gòu)性變化，并拋出異常？它自己的remove方法為何又可以使用呢？我們需要看下迭代器實(shí)現(xiàn)的原理。

3.4、迭代器實(shí)現(xiàn)的原理

我們來看下ArrayList中iterator方法的實(shí)現(xiàn)，代碼為：

public Iterator<E> iterator() {
    return new Itr();
}

新建了一個(gè)Itr對(duì)象，Itr是一個(gè)成員內(nèi)部類，實(shí)現(xiàn)了Iterator接口，聲明為：

private class Itr implements Iterator<E>

它有三個(gè)實(shí)例成員變量，為：

int cursor;        //下一個(gè)要返回的元素位置
int lastRet = -1; //最后一個(gè)返回的索引位置，如果沒有，為-1
int expectedModCount = modCount;

cursor表示下一個(gè)要返回的元素位置，lastRet表示最后一個(gè)返回的索引位置，expected-ModCount表示期望的修改次數(shù)，初始化為外部類當(dāng)前的修改次數(shù)modCount，回顧一下，成員內(nèi)部類可以直接訪問外部類的實(shí)例變量。每次發(fā)生結(jié)構(gòu)性變化的時(shí)候modCount都會(huì)增加，而每次迭代器操作的時(shí)候都會(huì)檢查expectedModCount是否與modCount相同，這樣就能檢測出結(jié)構(gòu)性變化。

我們來具體看下，它是如何實(shí)現(xiàn)Iterator接口中的每個(gè)方法的，先看hasNext()，代碼為：

public boolean hasNext() {
    return cursor ! = size;
}

cursor與size比較，比較直接，看next方法：

public E next() {
    checkForComodification();
    int i = cursor;
    if(i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if(i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

首先調(diào)用了checkForComodification，它的代碼為：

final void checkForComodification() {
    if(modCount ! = expectedModCount)
        throw new ConcurrentModificationException();
}

所以，next前面部分主要就是在檢查是否發(fā)生了結(jié)構(gòu)性變化，如果沒有變化，就更新cursor和lastRet的值，以保持其語義，然后返回對(duì)應(yīng)的元素。remove的代碼為：

public void remove() {
    if(lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

它調(diào)用了ArrayList的remove方法，但同時(shí)更新了cursor、lastRet和expectedModCount的值，所以它可以正確刪除。不過，需要注意的是，調(diào)用remove方法前必須先調(diào)用next，比如，通過迭代器刪除所有元素，直覺上，可以這么寫：

public static void removeAll(ArrayList<Integer> list){
   Iterator<Integer> it = list.iterator();
   while(it.hasNext()){
       it.remove();
   }
}

實(shí)際運(yùn)行，會(huì)拋出異常java.lang.IllegalStateException，正確寫法是：

public static void removeAll(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        it.next();
        it.remove();
    }
}

當(dāng)然，如果只是要?jiǎng)h除所有元素，ArrayList有現(xiàn)成的方法clear()。

listIterator()的實(shí)現(xiàn)使用了另一個(gè)內(nèi)部類ListItr，它繼承自Itr，基本思路類似，我們就不贅述了。

3.5、迭代器的好處

為什么要通過迭代器這種方式訪問元素呢？直接使用size()/get(index)語法不也可以嗎？在一些場景下，確實(shí)沒有什么差別，兩者都可以。不過，foreach語法更為簡潔一些，更重要的是，迭代器語法更為通用，它適用于各種容器類。

此外，迭代器表示的是一種關(guān)注點(diǎn)分離的思想，將數(shù)據(jù)的實(shí)際組織方式與數(shù)據(jù)的迭代遍歷相分離，是一種常見的設(shè)計(jì)模式。需要訪問容器元素的代碼只需要一個(gè)Iterator接口的引用，不需要關(guān)注數(shù)據(jù)的實(shí)際組織方式，可以使用一致和統(tǒng)一的方式進(jìn)行訪問。

而提供Iterator接口的代碼了解數(shù)據(jù)的組織方式，可以提供高效的實(shí)現(xiàn)。在ArrayList中， size/get(index)語法與迭代器性能是差不多的，但在后續(xù)介紹的其他容器中，則不一定，比如LinkedList，迭代器性能就要高很多。

從封裝的思路上講，迭代器封裝了各種數(shù)據(jù)組織方式的迭代操作，提供了簡單和一致的接口。

4、ArrayList實(shí)現(xiàn)的接口

4.1、Coolection

Collection表示一個(gè)數(shù)據(jù)集合，數(shù)據(jù)間沒有位置或順序的概念，Java 7中的接口定義為：

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<? > c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<? > c);
    boolean retainAll(Collection<? > c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

這些方法中，除了兩個(gè)toArray方法和幾個(gè)xxxAll()方法外，其他我們已經(jīng)介紹過了。toArray方法我們待會(huì)再介紹。這幾個(gè)xxxAll()方法的含義基本也是可以顧名思義的， addAll表示添加，removeAll表示刪除，containsAll表示檢查是否包含了參數(shù)容器中的所有元素，只有全包含才返回true, retainAll表示只保留參數(shù)容器中的元素，其他元素會(huì)進(jìn)行刪除。Java 8對(duì)Collection接口添加了幾個(gè)默認(rèn)方法，包括removeIf、stream、spliterator等，具體可參見API文檔。

抽象類AbstractCollection對(duì)這幾個(gè)方法都提供了默認(rèn)實(shí)現(xiàn)，實(shí)現(xiàn)的方式就是利用迭代器方法逐個(gè)操作。比如，我們看removeAll方法，代碼為：

public boolean removeAll(Collection<? > c) {
    boolean modified = false;
    Iterator<? > it = iterator();
    while(it.hasNext()) {
        if(c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

代碼比較簡單，就不解釋了。ArrayList繼承了AbstractList，而AbstractList又繼承了AbstractCollection, ArrayList對(duì)其中一些方法進(jìn)行了重寫，以提供更為高效的實(shí)現(xiàn)，具體不再介紹。

4.2、List

List表示有順序或位置的數(shù)據(jù)集合，它擴(kuò)展了Collection，增加的主要方法有（Java 7）?：

boolean addAll(int index, Collection<? extends E> c);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);

這些方法都與位置有關(guān)，容易理解，就不介紹了。Java 8對(duì)List接口增加了幾個(gè)默認(rèn)方法，包括sort、replaceAll和spliterator; Java 9增加了多個(gè)重載的of方法，可以根據(jù)一個(gè)或多個(gè)元素生成一個(gè)不變的List，具體就不介紹了，可參看API文檔。

4.3、RandomAccess

RandomAccess的定義為：

        public interface RandomAccess {
        }

沒有定義任何代碼。這有什么用呢？這種沒有任何代碼的接口在Java中被稱為標(biāo)記接口，用于聲明類的一種屬性。

這里，實(shí)現(xiàn)了RandomAccess接口的類表示可以隨機(jī)訪問，可隨機(jī)訪問就是具備類似數(shù)組那樣的特性，數(shù)據(jù)在內(nèi)存是連續(xù)存放的，根據(jù)索引值就可以直接定位到具體的元素，訪問效率很高。

有沒有聲明RandomAccess有什么關(guān)系呢？主要用于一些通用的算法代碼中，它可以根據(jù)這個(gè)聲明而選擇效率更高的實(shí)現(xiàn)。比如，Collections類中有一個(gè)方法binarySearch，在List中進(jìn)行二分查找，它的實(shí)現(xiàn)代碼就根據(jù)list是否實(shí)現(xiàn)了RandomAccess而采用不同的實(shí)現(xiàn)機(jī)制，如下所示：

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if(list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

5、ArrayList的其他方法

ArrayList中還有一些其他方法，包括構(gòu)造方法、與數(shù)組的相互轉(zhuǎn)換、容量大小控制等，我們來看下。ArrayList還有兩個(gè)構(gòu)造方法：

public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)

第一個(gè)方法以指定的大小initialCapacity初始化內(nèi)部的數(shù)組大小，代碼為：

this.elementData = new Object[initialCapacity];

在事先知道元素長度的情況下，或者，預(yù)先知道長度上限的情況下，使用這個(gè)構(gòu)造方法可以避免重新分配和復(fù)制數(shù)組。第二個(gè)構(gòu)造方法以一個(gè)已有的Collection構(gòu)建，數(shù)據(jù)會(huì)新復(fù)制一份。

ArrayList中有兩個(gè)方法可以返回?cái)?shù)組：

public Object[] toArray()
public <T> T[] toArray(T[] a)

第一個(gè)方法返回是Object數(shù)組，代碼為：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

第二個(gè)方法返回對(duì)應(yīng)類型的數(shù)組，如果參數(shù)數(shù)組長度足以容納所有元素，就使用該數(shù)組，否則就新建一個(gè)數(shù)組，比如：

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(123);
intList.add(456);
intList.add(789);
Integer[] arrA = new Integer[3];
intList.toArray(arrA);
Integer[] arrB = intList.toArray(new Integer[0]);
System.out.println(Arrays.equals(arrA, arrB));

輸出為true，表示兩種方式都是可以的。

Arrays中有一個(gè)靜態(tài)方法asList可以返回對(duì)應(yīng)的List，如下所示：

Integer[] a = {1,2,3};
List<Integer> list = Arrays.asList(a);

需要注意的是，這個(gè)方法返回的List，它的實(shí)現(xiàn)類并不是本節(jié)介紹的ArrayList，而是Arrays類的一個(gè)內(nèi)部類，在這個(gè)內(nèi)部類的實(shí)現(xiàn)中，內(nèi)部用的數(shù)組就是傳入的數(shù)組，沒有拷貝，也不會(huì)動(dòng)態(tài)改變大小，所以對(duì)數(shù)組的修改也會(huì)反映到List中，對(duì)List調(diào)用add、remove方法會(huì)拋出異常。

要使用ArrayList完整的方法，應(yīng)該新建一個(gè)ArrayList，如下所示：

List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));

ArrayList還提供了兩個(gè)public方法，可以控制內(nèi)部使用的數(shù)組大小，一個(gè)是：

public void ensureCapacity(int minCapacity)

它可以確保數(shù)組的大小至少為minCapacity，如果不夠，會(huì)進(jìn)行擴(kuò)展。如果已經(jīng)預(yù)知ArrayList需要比較大的容量，調(diào)用這個(gè)方法可以減少ArrayList內(nèi)部分配和擴(kuò)展的次數(shù)。

另一個(gè)方法是：

public void trimToSize()

它會(huì)重新分配一個(gè)數(shù)組，大小剛好為實(shí)際內(nèi)容的長度。調(diào)用這個(gè)方法可以節(jié)省數(shù)組占用的空間。

6、ArrayList特點(diǎn)分析

對(duì)于ArrayList，它的特點(diǎn)是內(nèi)部采用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，這決定了以下幾點(diǎn)。

1. 可以隨機(jī)訪問，按照索引位置進(jìn)行訪問效率很高，用算法描述中的術(shù)語，效率是O(1)，簡單說就是可以一步到位。
2. 除非數(shù)組已排序，否則按照內(nèi)容查找元素效率比較低，具體是O(N), N為數(shù)組內(nèi)容長度，也就是說，性能與數(shù)組長度成正比。
3. 添加元素的效率還可以，重新分配和復(fù)制數(shù)組的開銷被平攤了，具體來說，添加N個(gè)元素的效率為O(N)。
4. 插入和刪除元素的效率比較低，因?yàn)樾枰苿?dòng)元素，具體為O(N)。

總結(jié)

到此這篇關(guān)于Java中ArrayList用法的文章就介紹到這了,更多相關(guān)Java ArrayList用法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論