ArrayList

ArrayList就是傳說(shuō)中的動(dòng)態(tài)數(shù)組加匈，就是Array的復(fù)雜版本忘嫉，它提供了如下一些好處：動(dòng)態(tài)的增加和減少元素渴频、靈活的設(shè)置數(shù)組的大小.

ArrayList的定義：

public class ArrayList<E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

從ArrayList<E>可以看出它是支持泛型的胯陋，它繼承自AbstractList夯尽，實(shí)現(xiàn)了List冶忱、RandomAccess尾菇、Cloneable、java.io.Serializable接口囚枪。

• AbstractList提供了List接口的默認(rèn)實(shí)現(xiàn)（個(gè)別方法為抽象方法）派诬。
• List接口定義了列表必須實(shí)現(xiàn)的方法。
• RandomAccess是一個(gè)標(biāo)記接口链沼，接口內(nèi)沒(méi)有定義任何內(nèi)容默赂。
• 實(shí)現(xiàn)了Cloneable接口的類，可以調(diào)用Object.clone方法返回該對(duì)象的淺拷貝括勺。
• 通過(guò)實(shí)現(xiàn) java.io.Serializable 接口以啟用其序列化功能缆八。未實(shí)現(xiàn)此接口的類將無(wú)法使其任何狀態(tài)序列化或反序列化。序列化接口沒(méi)有方法或字段疾捍，僅用于標(biāo)識(shí)可序列化的語(yǔ)義奈辰。

ArrayList的屬性

ArrayList定義只定義類兩個(gè)私有屬性：

 /** 
  * The array buffer into which the elements of the ArrayList are stored. 
  * The capacity of the ArrayList is the length of this array buffer. 
  */  
 private transient Object[] elementData;  

 /** 
  * The size of the ArrayList (the number of elements it contains). 
  * 
  * @serial 
  */  
 private int size;  

很容易理解，elementData存儲(chǔ)ArrayList內(nèi)的元素乱豆，size表示它包含的元素的數(shù)量奖恰。
有個(gè)關(guān)鍵字需要解釋：transient。
Java的serialization提供了一種持久化對(duì)象實(shí)例的機(jī)制咙鞍。當(dāng)持久化對(duì)象時(shí)房官，可能有一個(gè)特殊的對(duì)象數(shù)據(jù)成員，我們不想用serialization機(jī)制
來(lái)保存它续滋。為了在一個(gè)特定對(duì)象的一個(gè)域上關(guān)閉serialization翰守，可以在這個(gè)域前加上關(guān)鍵字transient。
tansient是Java語(yǔ)言的關(guān)鍵字疲酌，用來(lái)表示一個(gè)域不是該對(duì)象串行化的一部分蜡峰。當(dāng)一個(gè)對(duì)象被串行化的時(shí)候，transient型變量的值不包括在串行化的表示中朗恳，然而非transient型的變量是被包括進(jìn)去的湿颅。

有點(diǎn)抽象，看個(gè)例子應(yīng)該能明白粥诫。

public class UserInfo implements Serializable {
    private static final long serialVersionUID = 996890129747019948L;
    private String name;
    private transient String psw;

    public UserInfo(String name, String psw) {
        this.name = name;
        this.psw = psw;
    }

    public String toString() {
        return "name=" + name + ", psw=" + psw;
    }
}

public class TestTransient {
    public static void main(String[] args) {
        UserInfo userInfo = new UserInfo("張三", "123456");
        System.out.println(userInfo);
        try {
            // 序列化油航，被設(shè)置為transient的屬性沒(méi)有被序列化
            ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream("UserInfo.out"));
            o.writeObject(userInfo);
            o.close();
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
        try {
            // 重新讀取內(nèi)容
            ObjectInputStream in = new ObjectInputStream(new FileInputStream("UserInfo.out"));
            UserInfo readUserInfo = (UserInfo) in.readObject();
            // 讀取后psw的內(nèi)容為null
            System.out.println(readUserInfo.toString());
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }
}

被標(biāo)記為transient的屬性在對(duì)象被序列化的時(shí)候不會(huì)被保存。

ArrayList的構(gòu)造方法

看完屬性看構(gòu)造方法怀浆。ArrayList提供了三個(gè)構(gòu)造方法

/** 
 * Constructs an empty list with the specified initial capacity. 
 */  
public ArrayList(int initialCapacity) {  
     super();  
    if (initialCapacity < 0)  
        throw new IllegalArgumentException("Illegal Capacity: "+  
                                           initialCapacity);  
    this.elementData = new Object[initialCapacity];  
}

/** 
 * Constructs an empty list with an initial capacity of ten. 
 */  
public ArrayList() {
    this(10);  
}

/** 
 * Constructs a list containing the elements of the specified 
 * collection, in the order they are returned by the collection's 
 * iterator. 
 */  
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);  
}

第一個(gè)構(gòu)造方法使用提供的initialCapacity來(lái)初始化elementData數(shù)組的大小谊囚。第二個(gè)構(gòu)造方法調(diào)用第一個(gè)構(gòu)造方法并傳入?yún)?shù)10怕享，即默認(rèn)elementData數(shù)組的大小為10。第三個(gè)構(gòu)造方法則將提供的集合轉(zhuǎn)成數(shù)組返回給elementData（返回若不是Object[]將調(diào)用Arrays.copyOf方法將其轉(zhuǎn)為Object[]）镰踏。

ArrayList的其他方法

• add(E e)

add(E e)都知道是在尾部添加一個(gè)元素函筋，如何實(shí)現(xiàn)的呢？

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

書(shū)上都說(shuō)ArrayList是基于數(shù)組實(shí)現(xiàn)的奠伪，屬性中也看到了數(shù)組跌帐，具體是怎么實(shí)現(xiàn)的呢？比如就這個(gè)添加元素的方法绊率，如果數(shù)組足夠大谨敛，則在將某個(gè)位置的值設(shè)置為指定元素即可，如果數(shù)組容量不夠了呢即舌？

看到add(E e)中先調(diào)用了ensureCapacityInternal(size + 1)方法佣盒，之后將元素賦給elementData[size]挎袜，而后size自增顽聂。例如：初次添加時(shí)，size為0盯仪，add將elementData[0]賦值為e紊搪，然后size設(shè)置為1（類似執(zhí)行以下兩條語(yǔ)句elementData[0]=e;size=1）。將元素賦給elementData[size++]不會(huì)出現(xiàn)數(shù)組越界的情況嗎全景？這里關(guān)鍵就在ensureCapacityInternal(size + 1)中了耀石。

根據(jù)ensureCapacityInternal的方法名可以知道是確保容量用的。ensureCapacityInternal(size + 1)后面的注釋可以明白是增加modCount的值（加了倆感嘆號(hào)爸黄，應(yīng)該蠻重要的滞伟，來(lái)看看）。

/**
 * Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

判斷minCapacity（即size+1）是否大于oldCapacity（即elementData.length）炕贵，若大于梆奈，則調(diào)整容量為oldCapacity + (oldCapacity >> 1)。調(diào)整elementData容量為新的容量称开，即返回一個(gè)內(nèi)容為原數(shù)組元素亩钟，大小為新容量的數(shù)組賦給elementData；否則不做操作鳖轰。

容量的拓展將導(dǎo)致數(shù)組元素的復(fù)制清酥，多次拓展容量將執(zhí)行多次整個(gè)數(shù)組內(nèi)容的復(fù)制。若提前能大致判斷l(xiāng)ist的長(zhǎng)度蕴侣，調(diào)用ensureCapacity調(diào)整容量焰轻，將有效的提高運(yùn)行速度。

可以理解提前分配好空間可以提高運(yùn)行速度昆雀，但是測(cè)試發(fā)現(xiàn)提高的并不是很大辱志，而且若list原本數(shù)據(jù)量就不會(huì)很大效果將更不明顯胧谈。

• add(int index, E element)

add(int index,E element)在指定位置插入元素。

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

首先判斷指定位置index是否超出elementData的界限荸频，之后調(diào)用ensureCapacityInternal調(diào)整容量（若容量足夠則不會(huì)拓展）菱肖，調(diào)用System.arraycopy將elementData從index開(kāi)始的size-index個(gè)元素復(fù)制到index+1至size+1的位置（即index開(kāi)始的元素都向后移動(dòng)一個(gè)位置），然后將index位置的值指向element旭从。

• addAll(Collection<? extends E> c)

addAll(Collection<? extends E> c) 將c中的全部元素添加到集合的末尾

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

先將集合c轉(zhuǎn)換成數(shù)組稳强，根據(jù)轉(zhuǎn)換后數(shù)組的長(zhǎng)度和ArrayList的size拓展容量，之后調(diào)用System.arraycopy方法復(fù)制元素到elementData的尾部和悦，調(diào)整size退疫。根據(jù)返回的內(nèi)容分析，只要集合c的大小不為0則返回true鸽素。

• addAll(int index,Collection<? extends E> c)

addAll(int index,Collection<? extends E> c) 在指定位置將c中的全部元素添加到集合

public boolean addAll(int index, Collection<? extends E> c) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

先判斷index是否越界褒繁。其他內(nèi)容與addAll(Collection<? extends E> c)基本一致，只是復(fù)制的時(shí)候先將index開(kāi)始的元素向后移動(dòng)X（c轉(zhuǎn)為數(shù)組后的長(zhǎng)度）個(gè)位置（也是一個(gè)復(fù)制的過(guò)程）馍忽，之后將數(shù)組內(nèi)容復(fù)制到elementData的index位置至index+X棒坏。

• clear()

clear() 清空集合

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clear的時(shí)候并沒(méi)有修改elementData的長(zhǎng)度（好不容易申請(qǐng)、拓展來(lái)的遭笋，憑什么釋放坝冕，留著搞不好還有用呢。這使得確定不再修改list內(nèi)容之后最好調(diào)用trimToSize來(lái)釋放掉一些空間）瓦呼，只是將所有元素置為null喂窟，size設(shè)置為0。

• clone()

返回此 ArrayList 實(shí)例的淺表副本央串。（淺層復(fù)制磨澡，不復(fù)制這些元素本身。）

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

調(diào)用父類的clone方法返回一個(gè)對(duì)象的副本质和，將返回對(duì)象的elementData數(shù)組的內(nèi)容賦值為原對(duì)象elementData數(shù)組的內(nèi)容稳摄，將副本的modCount設(shè)置為0。

• contains(Object o)

contains(Object o)如果集合包含指定的元素侦另，則返回值為true秩命。注意：元素的值可以為null

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

indexOf方法返回值與0比較來(lái)判斷對(duì)象是否在list中。接著看indexOf褒傅。

• indexOf(Object o)

indexOf(Object o) 返回指定元素在集合中的位置弃锐，如果不存在則返回-1。

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

通過(guò)遍歷elementData數(shù)組來(lái)判斷對(duì)象是否在list中殿托，若存在霹菊，返回index（[0, size-1]），若不存在則返回-1。所以contains方法可以通過(guò)indexOf(Object)方法的返回值來(lái)判斷對(duì)象是否被包含在list中旋廷。發(fā)現(xiàn)contains方法判斷是否包含指定元素鸠按，調(diào)用的是equals方法

• lastIndexOf(Object o)

lastIndexOf(Object o)返回指定元素在集合中最后一次出現(xiàn)的位置，如果不存在則返回-1

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

采用了從后向前遍歷elementData數(shù)組饶碘，若遇到Object則返回index值包券，若沒(méi)有遇到表悬，返回-1俭厚。

• get(int index)

get(int index) 返回指定位置的元素士鸥，如果index超出數(shù)組界限了，就拋出IndexOutBoundsException異常

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    return elementData(index);
}

• remove(int index)

remove(int index) 移除指定位置的元素豪治，并把元素返回洞拨。

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

首先是檢查范圍，修改modCount负拟，保留將要被移除的元素烦衣，將移除位置之后的元素向前挪動(dòng)一個(gè)位置，將list末尾元素置空（null）掩浙，返回被移除的元素花吟。

• remove(Object o)

remove(Object o) 移除指定的元素，移除成功則返回true涣脚。注意：傳入的元素可為null

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

首先通過(guò)代碼可以看到示辈，當(dāng)移除成功后返回true，否則返回false遣蚀。remove(Object o)中通過(guò)遍歷elementData尋找是否存在傳入對(duì)象，一旦找到就調(diào)用fastRemove移除對(duì)象纱耻。為什么找到了元素就知道了index芭梯，不通過(guò)remove(index)來(lái)移除元素呢？因?yàn)閒astRemove跳過(guò)了判斷邊界的處理弄喘，因?yàn)檎业皆鼐拖喈?dāng)于確定了index不會(huì)超過(guò)邊界玖喘，而且fastRemove并不返回被移除的元素。下面是fastRemove的代碼蘑志，基本和remove(index)一致累奈。

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

• set(int index, E element)

set(int index, E element) 將集合中指定位置的元素替換為指定元素，并返回被替換的元素

public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

• toArray()

toArray()返回集合的數(shù)組表示形式

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

• trimToSize()

trimToSize() 將集合的容量整理至集合實(shí)際包含的元素個(gè)數(shù)

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

關(guān)于modCount

/**
 * The number of times this list has been <i>structurally modified</i>.
 * Structural modifications are those that change the size of the
 * list, or otherwise perturb it in such a fashion that iterations in
 * progress may yield incorrect results.
 *
 * <p>This field is used by the iterator and list iterator implementation
 * returned by the {@code iterator} and {@code listIterator} methods.
 * If the value of this field changes unexpectedly, the iterator (or list
 * iterator) will throw a {@code ConcurrentModificationException} in
 * response to the {@code next}, {@code remove}, {@code previous},
 * {@code set} or {@code add} operations.  This provides
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
 * wishes to provide fail-fast iterators (and list iterators), then it
 * merely has to increment this field in its {@code add(int, E)} and
 * {@code remove(int)} methods (and any other methods that it overrides
 * that result in structural modifications to the list).  A single call to
 * {@code add(int, E)} or {@code remove(int)} must add no more than
 * one to this field, or the iterators (and list iterators) will throw
 * bogus {@code ConcurrentModificationExceptions}.  If an implementation
 * does not wish to provide fail-fast iterators, this field may be
 * ignored.
 */
protected transient int modCount = 0;

在父類AbstractList中定義了一個(gè)int型的屬性：modCount急但，記錄了ArrayList結(jié)構(gòu)性變化的次數(shù)澎媒。

在ArrayList的所有涉及結(jié)構(gòu)變化的方法中都增加modCount的值，包括：add()波桩、remove()戒努、addAll()、removeRange()及clear()方法镐躲。這些方法每調(diào)用一次储玫，modCount的值就加1侍筛。

關(guān)于迭代器

• Iterator<E> iterator()

iterator()方法是在AbstractList中實(shí)現(xiàn)的，該方法返回AbstractList的一個(gè)內(nèi)部類Itr的對(duì)象撒穷。

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

private class Itr implements Iterator<E> {
    
    int cursor = 0; //標(biāo)記位：標(biāo)記遍歷到哪一個(gè)元素
    int expectedModCount = modCount; //標(biāo)記位：用于判斷在遍歷的過(guò)程中匣椰，是否發(fā)生了add、remove等操作

    //檢測(cè)對(duì)象數(shù)組是否還有元素
    public boolean hasNext() {
        return cursor != size(); //如果cursor==size端礼，說(shuō)明已經(jīng)遍歷完了窝爪，上一次遍歷的是最后一個(gè)元素
    }

    //獲取元素
    public E next() {
        checkForComodification(); //檢測(cè)在遍歷的過(guò)程中，是否發(fā)生了add齐媒、remove等操作
        try {
            E next = ArrayList.this.get(cursor++);
            return next;
        } catch (IndexOutOfBoundsException e) { //捕獲get(cursor++)方法的IndexOutOfBoundsException
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    
    //移除元素
    public void remove() {
        checkForComodification();
        try {
            ArrayList.this.remove(cursor--);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) { //捕獲IndexOutOfBoundsException
            throw new ConcurrentModificationException();
        }
    }

    //檢測(cè)在遍歷的過(guò)程中蒲每，是否發(fā)生了add、remove等操作
    final void checkForComodification() {
        if (modCount != expectedModCount) //發(fā)生了add喻括、remove等操作,這個(gè)我們可以查看add等的源代碼邀杏，發(fā)現(xiàn)會(huì)出現(xiàn)modCount++
            throw new ConcurrentModificationException();
    }
}

對(duì)集合的遍歷操作，無(wú)論是for(int i=0; i<list.size(); i++)唬血，還是增強(qiáng)for循環(huán)望蜡，進(jìn)行編譯之后都會(huì)解除語(yǔ)法糖，變成迭代器的形式拷恨。

現(xiàn)在對(duì)modCount和expectedModCount的作用應(yīng)該非常清楚了脖律。在對(duì)一個(gè)集合進(jìn)行跌代操作的同時(shí)，并不限制對(duì)集合的元素進(jìn)行操作腕侄。但當(dāng)這些操作包括一些可能引起跌代錯(cuò)誤的add()或remove()等危險(xiǎn)操作時(shí)小泉，就會(huì)拋出ConcurrentModificationException。 這就是modCount和expectedModCount的作用所在冕杠。在迭代過(guò)程中微姊，如果要移除集合中的元素，必須要使用it.remove()分预，否則會(huì)拋出ConcurrentModificationException

總結(jié)

• ArrayList基于數(shù)組方式實(shí)現(xiàn)兢交，無(wú)容量的限制（會(huì)自動(dòng)擴(kuò)容），每次以當(dāng)前容量的50%進(jìn)行擴(kuò)容笼痹，即：10-->15-->22-->33....
• 添加元素時(shí)可能要擴(kuò)容（所以最好預(yù)判一下）配喳，刪除元素時(shí)不會(huì)減少容量（若希望減少容量，trimToSize()）凳干，刪除元素時(shí)晴裹，將刪除掉的位置元素置為null，下次gc就會(huì)回收這些元素所占的內(nèi)存空間纺座。
• 線程不安全
• add(int index, E element)：添加元素到數(shù)組中指定位置的時(shí)候息拜，需要將該位置及其后邊所有的元素都整塊向后復(fù)制一位
• get(int index)：獲取指定位置上的元素時(shí)，可以通過(guò)索引直接獲取（O(1)）
• remove(Object o)需要遍歷數(shù)組（底層調(diào)用元素的equals方法）
• remove(int index)不需要遍歷數(shù)組少欺，只需判斷index是否符合條件即可喳瓣，效率比remove(Object o)高，需要將該位置之后的所有元素都整塊往前復(fù)制一位
• contains(E)需要遍歷數(shù)組（底層調(diào)用元素的equals方法）