List ADT實(shí)現(xiàn)之增長(zhǎng)數(shù)組實(shí)現(xiàn)（ArrayList）

List ADT有兩種流行的實(shí)現(xiàn)方式，Java中ArrayList類提供了可增長(zhǎng)數(shù)組的實(shí)現(xiàn)，LinkedList提供了雙鏈表實(shí)現(xiàn)。

使用ArrayList的有點(diǎn)在于，對(duì)get和set操作花費(fèi)常數(shù)時(shí)間。其缺點(diǎn)是新元素的插入和元素的刪除付出的代價(jià)非常昂貴，除非變動(dòng)實(shí)在末端進(jìn)行。

為說(shuō)明增長(zhǎng)數(shù)組實(shí)現(xiàn)的一些思想，本篇文章將編寫ArrayList的簡(jiǎn)單實(shí)現(xiàn)。為避免與類庫(kù)中的ArrayList類相混淆，這里將把實(shí)現(xiàn)的類叫做MyArrayList，即MyArrayList是獨(dú)立的。

MyArrayList的一些細(xì)節(jié)：

  1. 維護(hù)數(shù)組的元素（elementData），數(shù)組的容量(elementData.length)，數(shù)組當(dāng)前的存儲(chǔ)的元素個(gè)數(shù)(size)。
  2. 提供一種機(jī)制來(lái)動(dòng)態(tài)改變數(shù)組的容量。通過(guò)建立新的數(shù)組，將老數(shù)組的元素拷貝到新數(shù)組中，然后允許虛擬機(jī)回收老數(shù)組。
  3. 提供set和get操作的實(shí)現(xiàn)。
  4. 提供基本操作，例如：size()，isEmpty()，和Clear()。提供remove(...)操作和add(...)操作 。
  5. MyArrayList實(shí)現(xiàn)Iterable接口，并提供了一個(gè)實(shí)現(xiàn)Iterator接口的實(shí)現(xiàn)類MyListIterator，該類實(shí)現(xiàn)了hasNext()，next()和remove()操作。最后通過(guò)實(shí)現(xiàn)的iterator放回一個(gè)Iterator實(shí)例。

代碼####

public class MyArrayList<E> implements Iterable<E> {

    private static final int DEFULT_CAPASITY = 10;

    private int size; // 維護(hù)數(shù)組當(dāng)前元素的個(gè)數(shù)
    private E[] elementData; // 存儲(chǔ)當(dāng)前List的元素

    // 構(gòu)造器
    public MyArrayList() {
        doClear();
    }

    // 清空List
    public void clear() {
        doClear();
    }

    // 清空List操作，設(shè)置size為0，elementData容量為默認(rèn)值10
    private void doClear() {
        size = 0;
        ensureCapacity(DEFULT_CAPASITY);
    }

    // 獲取size
    public int size() {
        return size;
    }

    // 判斷是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // 為了避免浪費(fèi)空間，設(shè)置容量為size
    public void trimToSize() {
        ensureCapacity(size);
    }

    // 通過(guò)索引獲取元素
    public E get(int index) {
        CheckRange(index);
        return elementData[index];
    }

    // 修改某個(gè)位子的元素
    public E set(int index, E element) {
        CheckRange(index);
        E old = elementData[index];
        elementData[index] = element;
        return old;
    }

    // 保證對(duì)List的操作時(shí)有足夠的空間。比如add操作，如果數(shù)組的容量和size相同，則沒(méi)有位子可以添加元素。
    // 傳入一個(gè)新的容量minCapacity，表示需要的最小容量。
    // 如果size>=newCapacity，則說(shuō)明容量足夠，不作處理。
    // 如果size<newCapacity，則將elementData擴(kuò)容至minCapacity。
    @SuppressWarnings("unchecked")
    public void ensureCapacity(int minCapacity) {
        if (size >= minCapacity) {
            return;
        }

        E[] old = elementData; // 將elementData拷貝到old
        elementData = (E[]) new Object[minCapacity]; // 把elementData擴(kuò)容至minCapacity

        for (int i = 0; i < size; i++) {
            elementData[i] = old[i]; // 還原elementData原來(lái)的元素
        }

    }

    // 在List的末尾添加元素，實(shí)際調(diào)用了add(int index, E element)方法。
    public void add(E element) {
        add(size, element);
    }

    // 在某個(gè)位子添加元素。
    public void add(int index, E element) {
        CheckRangeForAdd(index); // 數(shù)組越界檢查
        // 如果數(shù)組的容量等于size，即數(shù)組被填滿，則需要擴(kuò)容
        if (elementData.length == size) {
            ensureCapacity(size + 1); // 擴(kuò)容一個(gè)元素的空間
        }
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1]; // index及其后面的元素后移
        }
        elementData[index] = element;
        size++;
    }

    // 刪除某位子的元素
    public void remove(int index) {
        CheckRange(index); // 數(shù)組越界檢查
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1]; // 索引大于index的元素遷移
        }
        size--;
    }

    // 越界檢查，智能訪問(wèn)0~size-1的范圍
    private void CheckRange(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    // 針對(duì)add操作的數(shù)組越界檢查，因?yàn)榭梢栽贚ist末尾添加元素，所以其訪問(wèn)范圍為0~size
    private void CheckRangeForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
    }

    // iterator方法，返回一個(gè)MyIterator實(shí)例
    public Iterator<E> iterator() {
        return new MyIterator();
    }

    // MyArrayList的內(nèi)部類，實(shí)現(xiàn)了Iterator接口，用來(lái)實(shí)現(xiàn)遍歷List的操作
    private class MyIterator implements Iterator<E> {
        // 遍歷數(shù)組，默認(rèn)從0開(kāi)始
        private int currentIndex = 0;

        // 如果沒(méi)有超過(guò)size，則說(shuō)明還有下一元素
        public boolean hasNext() {
            return currentIndex < size;
        }

        // 每一次調(diào)用都返當(dāng)前元素，比如第一調(diào)用next()返回第一元素，第二次調(diào)用則返回第二個(gè)元素
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return elementData[currentIndex++];
        }

        // 刪除當(dāng)前元素。實(shí)際上是調(diào)用了MyAarrayList的remove方法。
        @SuppressWarnings("unused")
        public void remove() {
            MyArrayList.this.remove(--currentIndex);
        }

    }
}

測(cè)試代碼####

public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<String>();
        Iterator<String> sIterator = myArrayList.iterator();

        // 在末尾添加元素
        System.out.println("添加元素：b,c,d");
        myArrayList.add("b");
        myArrayList.add("c");
        myArrayList.add("d");

        // 遍歷數(shù)組元素
        System.out.print("iterator遍歷List:");
        while (sIterator.hasNext()) {
            System.out.print(sIterator.next());
        }

        System.out.println();

        // size()
        System.out.println();
        System.out.println("此時(shí)List中元素的個(gè)數(shù)為：" + myArrayList.size());

        System.out.println();

        // 在指定位置添加元素，并輸出結(jié)果
        System.out.println("在List首部添加元素:a");
        myArrayList.add(0, "a");

        System.out.print("iterator遍歷List:");
        sIterator = myArrayList.iterator();
        while (sIterator.hasNext()) {
            System.out.print(sIterator.next());
        }

        System.out.println();

        // 刪除指定位子元素(刪除d)
        System.out.println();
        System.out.println("刪除index為3的元素(d)");
        myArrayList.remove(3);
        System.out.print("iterator遍歷List:");
        sIterator = myArrayList.iterator();
        while (sIterator.hasNext()) {
            System.out.print(sIterator.next());
        }

        System.out.println();
        System.out.println();

        // set()和get()
        System.out.println("修改List的第一個(gè)元素為z.");
        myArrayList.set(0, "z");
        System.out.println("獲取第一個(gè)元素" + myArrayList.get(0));

        System.out.println();

        // iterator.remove()
        System.out.println("測(cè)試iterator的remove方法：遍歷List，每次遍歷刪除當(dāng)前元素");
        Iterator<String> rIterator = myArrayList.iterator();
        while (rIterator.hasNext()) {
            if (rIterator.next() != null) {
                rIterator.remove();
            }
        }
        System.out.println("刪除后的List長(zhǎng)度為" + myArrayList.size());
    }

測(cè)試結(jié)果####

測(cè)試結(jié)果

本篇只給出了ArrayList的一些基本操作，如果大家想更深入的了解，可以去查看ArrayList的源碼，下面是一篇ArrayList源碼分析很好的文章：
http://blog.csdn.net/jzhf2012/article/details/8540410

大家可以思考兩個(gè)問(wèn)題：

  1. 為什么MyArrayList有了remove方法，為什么iterator中還要實(shí)現(xiàn)remove方法。
  2. 為什么MyIterator要作為MyArrayList的內(nèi)部類，還有其他實(shí)現(xiàn)方式嗎？
    如果有答案，歡迎大家在評(píng)論區(qū)討論。
最后編輯于 ：
?著作權(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)容