引出

1.ArrayList的結(jié)構(gòu)分析，可迭代接口，是List的實現(xiàn)；
2.數(shù)組增加元素和刪除元素的分析，何時擴容，如何擴容；
3.插入數(shù)據(jù)的復(fù)雜度O(N)；
4.數(shù)組特點：查找和修改容易O(1)；增加和刪除復(fù)雜O(N)；文章來源地址http://www.zghlxwxcb.cn/news/detail-655870.html

手動實現(xiàn)ArrayList

定義接口MyList<T>

package com.tianju.book.jpa.mlist;

/**
 * 手工打造ArrayList
 */
public interface MyList<T> {
    /**
     * 增加一個元素，涉及到容量的變化
     */
    void add(T t);

    /**
     * 根據(jù)索引刪除元素
     * @param index 要刪除元素的索引，超過索引？索引不存在？
     */
    void remove(int index);

    /**
     * 根據(jù)索引修改一個元素
     * @param index 要修改的索引
     * @param t 修改的值
     */
    void set(int index,T t);

    /**
     * 根據(jù)索引獲取元素
     * @param index 索引
     * @return 獲取的元素
     */
    T get(int index);

    int size();

    String toString();

}

寫ArrayList的實現(xiàn)類

增加元素

• 如果放不下怎么辦？如何擴容？
• 擴容后如何操作？

擴容：每次為原來的1.5倍

如果放不下，就擴容；

擴容后把原來的數(shù)據(jù)一個一個再放回去；

刪除元素

源碼分析

• 刪除頭部，尾部，中間——最一般的就是中間元素被刪除；
• 此時需要跳過被刪除的元素，把沒有被刪除的放回去；

package com.tianju.book.jpa.mlist;

public class MyArrayList<T> implements MyList<T> {

    private int size; // 不寫初始值為0

    private Object[] elementData = new Object[5]; // 自己的ArrayList的默認大小是5


    @Override
    public void add(T t) {
        // 如果放不下就要擴容
        if (size+1>=elementData.length){
            // >> 位運算，右移相當于除以2，所以新的長度是原來的1.5倍
            int newLen = elementData.length + (elementData.length>>1);
            // 這里相當于新建一個數(shù)組，把原來的一個一個放進去，然后把elementData指向新的數(shù)組
//            elementData = Arrays.copyOf(elementData, newLen); // arrays工具類的實現(xiàn)
            Object[] newElementData = new Object[newLen];
            for(int i=0;i<elementData.length;i++){
                newElementData[i] = elementData[i];
            }
            elementData = newElementData;
            System.out.println("擴容后長度"+elementData.length);
        }
        elementData[size] = t;//把新的元素放過來
        size = size + 1; // 新的size比原來加1
    }

    @Override
    public void remove(int index) {
        // 刪除怎么搞？
        // 刪除頭部？尾部？中間？
        // 這里采用新建一個數(shù)組，跳過要刪除的那個元素，一個一個再放回去
        Object[] newElementData = new Object[elementData.length]; // 和原來大小一樣
        int j = 0; // 新的索引
        for (int i=0;i<size;i++){
            if (i==index){
                System.out.println(index+"跳過: "+elementData[i]);
                continue;
            }
            newElementData[j] = elementData[i];
            j++; // 跳過被刪除的那個索引
        }
        elementData = newElementData; // 再指向新的數(shù)組
        size--; // 刪除元素后size-1

    }

    @Override
    public void set(int index, T t) {
        // 修改的復(fù)雜度為O(1)
        if (index>=size){
            throw new IndexOutOfBoundsException("索引越界");
        }
        elementData[index] = t;

    }

    @Override
    public T get(int index) {
        // 根據(jù)索引獲取元素的復(fù)雜度也為O(1)
        // 需要判斷索引是不是超了
        if (index>=size){
            throw new IndexOutOfBoundsException("索引越界");
        }
        return (T) elementData[index];

    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public String toString(){
        String str ="[";
        for (int i =0;i<size;i++){
            str += elementData[i] + ",";
        }
        str +="]";
        return str;
    }
}

寫測試類進行測試

package com.tianju.book.jpa.mlist;


import java.util.ArrayList;
import java.util.List;

public class MyListTest {
    public static void main(String[] args) {
        MyList<String> myList = new MyArrayList<>();
        System.out.println(myList.size());
        myList.add("Peter001");
        myList.add("Peter002");
        myList.add("Peter003");
        myList.add("Peter004");
        System.out.println(myList.size());
        myList.add("Peter005");
        System.out.println("目前List中元素的數(shù)量"+myList.size());
        System.out.println(myList);

        System.out.println("*******刪除一個元素*******");
        myList.remove(1);
        System.out.println(myList);
        System.out.println("刪除元素后list長度："+myList.size());

        myList.add("shirley");
        System.out.println("新增shirley元素后list："+myList);
        System.out.println("長度："+myList.size());

        System.out.println("*******修改一個元素*******");
        myList.set(0, "zgg");
        System.out.println(myList);

        System.out.println("*******查詢一個元素*******");
        String s = myList.get(2);
        System.out.println("索引為2的元素為："+s);

        System.out.println("索引越界的情況");
        System.out.println(myList.get(10));


        List<String> strings = new ArrayList<>();
        System.out.println(strings.size());

    }
}

數(shù)組插入數(shù)據(jù)?

插人和刪除的花費卻潛藏著昂貴的開銷，這要看插入和刪除發(fā)生在什么地方。最壞的情形下，在位置0的插入（即在表的前端插入）首先需要將整個數(shù)組后移一個位置以空出空間來，而刪除第一個元素則需要將表中的所有元素前移一個位置，因此這兩種操作的最壞情況為O(N)。

平均來看，這兩種操作都需要移動表的一半的元素，因此仍然需要線性時間。另一方面，如果所有的操作都發(fā)生在表的高端，那就沒有元素需要移動，而添加和刪除則只花費O(1)時間。

存在許多情形，在這些情形下的表是通過在高端進行插入操作建成的，其后只發(fā)生對數(shù)組的訪問（即只有findKth操作）。在這種情況下，數(shù)組是表的一種恰當?shù)膶崿F(xiàn)。然而，如果發(fā)生對表的一些插入和刪除操作，特別是對表的前端進行，那么數(shù)組就不是一種好的選擇。另一種數(shù)據(jù)結(jié)構(gòu)：鏈表(linked list)。

總結(jié)

1.ArrayList的結(jié)構(gòu)分析，可迭代接口，是List的實現(xiàn)；
2.數(shù)組增加元素和刪除元素的分析，何時擴容，如何擴容；
3.插入數(shù)據(jù)的復(fù)雜度O(N)；
4.數(shù)組特點：查找和修改容易O(1)；增加和刪除復(fù)雜O(N)；

到了這里，關(guān)于Java進階（3）——手動實現(xiàn)ArrayList & 源碼的初步理解分析 & 數(shù)組插入數(shù)據(jù)和刪除數(shù)據(jù)的問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！