摘要：類屬性是基于數(shù)組實(shí)現(xiàn)的，其屬性有其中常量表示數(shù)組的基礎(chǔ)容量。表示數(shù)組表當(dāng)前長(zhǎng)度數(shù)組元素個(gè)數(shù)，作索引時(shí)，表示數(shù)組的最后一個(gè)元素，而表示新添加的項(xiàng)可以被放置的位置。

PS：如果覺得文章有什么地方寫錯(cuò)了，哪里寫得不好，或者有什么建議，歡迎指點(diǎn)。

ArrayList 類提供了 List ADT 的可增長(zhǎng)數(shù)組的實(shí)現(xiàn)。

源碼鏈接：戳此進(jìn)GitHub查看

MyArrayList 泛型類實(shí)現(xiàn)了 Iterable 接口從而可以擁有增強(qiáng) for 循環(huán)（for each 循環(huán)）。

public class MyArrayList implements Iterable {
     
    @Override
    public Iterator iterator() {
        return new ArrayListIterator();
    }   
}

MyArrayList 是基于數(shù)組實(shí)現(xiàn)的，其屬性有：

private static final int DEFAULT_CAPACITY = 10;

private int theSize;

private AnyType[] theArrays;

其中常量 DEFAULT_CAPACITY 表示數(shù)組的基礎(chǔ)容量。theSize 表示數(shù)組表當(dāng)前長(zhǎng)度（數(shù)組元素個(gè)數(shù)），作索引時(shí)，A[theSize - 1] 表示數(shù)組的最后一個(gè)元素，而 A[theSize] 表示新添加的項(xiàng)可以被放置的位置。泛型數(shù)組 theArrays 為 MyArrayList 類的數(shù)組實(shí)現(xiàn)，即對(duì) MyArrayList 對(duì)象的操作實(shí)際為對(duì)數(shù)組 theArrays 的操作。

當(dāng)實(shí)例化 MyArrayList 對(duì)象時(shí)，調(diào)用構(gòu)造方法：

public MyArrayList(){
    theArrays = (AnyType[])new Object[DEFAULT_CAPACITY]; 
    doClear();
 }

在構(gòu)造方法中先實(shí)例化泛型數(shù)組 theArrays。由于泛型數(shù)組的創(chuàng)建是非法的，所以我們需要?jiǎng)?chuàng)建一個(gè)泛型類型限界的數(shù)組；即創(chuàng)建一個(gè) Object[] 類型的數(shù)組，然后向泛型類型數(shù)組 AnyType[] 強(qiáng)制轉(zhuǎn)型。

然后調(diào)用 doClear() 方法對(duì)數(shù)組表進(jìn)行清空、初始化的操作，此方法僅類內(nèi)部可調(diào)用：

private void doClear(){
   theSize = 0;
   expandCapacity(DEFAULT_CAPACITY);
}

此處先設(shè)置 theSize = 0，然后調(diào)用 expandCapacity() 方法改變數(shù)組容量為基礎(chǔ)容量。（在 expandCapacity() 方法的實(shí)現(xiàn)中，若擴(kuò)充的容量（參數(shù)）小于 theSize 時(shí)表示非法的操作。）

數(shù)組擴(kuò)容方法 expandCapacity() ：

public void expandCapacity(int newCapacity){
    if (newCapacity < theSize){
        return;
    }

   // 數(shù)組容量的擴(kuò)充:
   AnyType[] newArrays = (AnyType[])new Object[newCapacity];
 
   // 利用 System.arraycopy() 方法拷貝數(shù)組
   System.arraycopy(theArrays,0,newArrays,0,theSize);
   theArrays = newArrays;
}

System.arraycopy() 方法: 
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

/**
 * 根據(jù)下標(biāo)得到數(shù)組元素的值
 */
public AnyType get(int idx){
    if (idx <0 || idx >= theSize){
        throw new ArrayIndexOutOfBoundsException();
    }
    return theArrays[idx];
}

/**
 * 根據(jù)下標(biāo)設(shè)置數(shù)組元素的值
 * 返回該下標(biāo)元素的原值
 */
public AnyType set(int idx,AnyType newVal){
    if (idx <0 || idx >= theSize){
        throw new ArrayIndexOutOfBoundsException();
    }

    AnyType oldVal = theArrays[idx];
    theArrays[idx] = newVal;
    return oldVal;
}

 /**
  * 根據(jù)下標(biāo)向數(shù)組插入新元素 
  */
public boolean add(int idx,AnyType newVal){
    // 當(dāng) idx=theSize 時(shí)，在 A[theSize] 位置處插入元素
    if (idx < 0 || idx > theSize){
        throw new ArrayIndexOutOfBoundsException();
    }

    // 數(shù)組滿時(shí)擴(kuò)充容量
    if (theArrays.length == theSize){
        expandCapacity(theSize*2 + 1);
    }

    // 數(shù)組元素后移
    for (int i=theSize;i>idx;i--){
        theArrays[i] = theArrays[i-1];
    }

    theArrays[idx] = newVal;
    theSize++;
    return true;
}

/**
 * 在數(shù)組末尾插入新元素
 */
public boolean add(AnyType newVal){
    add(theSize,newVal);
    return true;
}

/**
 * 根據(jù)下標(biāo)刪除元素
 * 返回被刪除的元素
 */
public AnyType remove(int idx){
    if (idx < 0 || idx >= theSize){
        throw new ArrayIndexOutOfBoundsException();
    }

    // 數(shù)組元素前移
    AnyType removedElem = theArrays[idx];
    for (int i = idx; i < theSize-1; i++) {
        theArrays[i] = theArrays[i+1];
    }
    theSize--;
    return removedElem;
}

實(shí)現(xiàn) Iterable 接口的集合必須提供 iterator 方法，該方法返回一個(gè) Iterator （java.util.Iterator）類型的對(duì)象:

public interface Iterator {
    boolean hasNext();
    AnyType next();
    void remove();
}

即每個(gè)集合均可通過(guò) iterator 方法創(chuàng)建并返回給客戶一個(gè)實(shí)現(xiàn) Iterator 接口的對(duì)象，并把 當(dāng)前位置 的概念在對(duì)象內(nèi)部存儲(chǔ)下來(lái)。根據(jù)當(dāng)前位置項(xiàng)每次調(diào)用 hasNext() 來(lái)判斷是否存在下一項(xiàng)，調(diào)用 next() 來(lái)給出下一項(xiàng)，而 remove() 方法則刪除由 next() 方法最新返回的項(xiàng)（即當(dāng)調(diào)用一次 remove() 后，直到對(duì) next() 再調(diào)用一次后才能調(diào)用 remove() 方法）。例：

public static  void print(Collection coll){
    Iterator itr = coll.iterator();
    while(itr.hasNext()){
        AnyType item = itr.next();
        System.out.println(item);
        // itr.remove();
    }
}

Java 中的增強(qiáng) for 循環(huán)（for each）底層即是通過(guò)這種迭代器模式來(lái)實(shí)現(xiàn)的，當(dāng)使用增強(qiáng) for 循環(huán)時(shí)也就是間接的使用 Iterator。

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList implements Iterable {
    ......

    @Override
    public Iterator iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements Iterator{

        // 初始時(shí)當(dāng)前位置為 0
        private int current = 0;
        
        @Override
        public boolean hasNext() {
            return current < theSize;
        }

        @Override
        public AnyType next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            return theArrays[current++];
        }

        @Override
        public void remove() {
            /* 因?yàn)?remove() 方法有相同的，MyArrayList.this 表示外部類當(dāng)前對(duì)象的一個(gè)引用 */
            MyArrayList.this.remove(--current);
        }
    }
}

iterator() 方法直接返回 ArrayListIterator 類的一個(gè)實(shí)例，該類是一個(gè)實(shí)現(xiàn) Iterator 接口的類。ArrayListIterator 存儲(chǔ)當(dāng)前位置的概念，并提供 hasNext()、next()、remove() 的實(shí)現(xiàn)。當(dāng)前位置 表示要被查看的下一元素（的數(shù)組下標(biāo)），因此初始化當(dāng)前位置為 0。

其中，泛型類 ArrayListIterator 是一個(gè) 內(nèi)部類，使用內(nèi)部類的目的及優(yōu)點(diǎn)：

next() 方法中使用當(dāng)前位置作為下標(biāo)訪問(wèn)數(shù)組元素然后將當(dāng)前位置向后推進(jìn)，而迭代器中是沒有數(shù)組的，使用內(nèi)部類可以訪問(wèn)外部類的域 theArrays；

theArrays 是 MyArrayList 的私有域，使用內(nèi)部類訪問(wèn)可以很好的滿足面向?qū)ο缶幊痰幕驹瓌t，即讓數(shù)據(jù)盡可能地隱藏；

滿足迭代器 Iterator 的特性，即當(dāng)集合（外部類）不存在的時(shí)候，迭代器（內(nèi)部類）也是不存在的。

因?yàn)?ArrayList 是基于數(shù)組實(shí)現(xiàn)的，所以和數(shù)組相似：ArrayList 的 get() 和 set() 方法花費(fèi)常數(shù)時(shí)間 O(1)；而使用 add() 和 remove() 方法時(shí)為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)搬移工作，其花費(fèi)的時(shí)間代價(jià)為 O(n)。

歡迎您的點(diǎn)贊、收藏和評(píng)論！
（完）