arraylist的方法，自己動手系列——實現一個簡單的ArrayList

2023-10-18 阅读 17 评论 0

摘要：ArrayList是Java集合框架中一個經典的實現類。他比起常用的數組而言，明顯的優點在于，可以隨意的添加和刪除元素而不需考慮數組的大小。處于練手的目的，實現一個簡單的ArrayList，并且把實現的過程在此記錄。實現的ArrayList主要的功能如下：

ArrayList是Java集合框架中一個經典的實現類。他比起常用的數組而言，明顯的優點在于，可以隨意的添加和刪除元素而不需考慮數組的大小。處于練手的目的，實現一個簡單的ArrayList，并且把實現的過程在此記錄。
實現的ArrayList主要的功能如下：

默認構造器和一個參數的有參構造器
add方法
get方法
indexOf方法
contains方法
size方法
isEmpty方法
remove方法

這個簡單的ArrayList類取名為SimpleArrayList，全部的代碼查看SimpleArrayList代碼

構造器

源碼ArrayList一共有三個構造器，一個無參構造器，一個參數為int型有參構造器，一個參數為Collection型的有參構造器。參數為Collection型的構造器用來實現將其他繼承Collection類的容器類轉換成ArrayList。SimpleArrayList類因為還沒有手動實現其他的容器類，所以實現的構造方法只有2個。代碼如下：

    public SimpleArrayList(){this(DEFAULT_CAPACITY);}public SimpleArrayList(int size){if (size < 0){throw new IllegalArgumentException("默認的大小" + size);}else{elementData = new Object[size];}}

無參構造器中的 DEFAULT_CAPACITY是定義的私有變量，默認值是10，用來創建一個大小為10的數組。有參構造器中，int參數是用來生成一個指定大小的Object數組。將創建好的數組傳給elementData。elementData是真正的用來存儲元素的數組。

add方法

arraylist的方法？add 方法用來往容器中添加元素，add方法有兩個重載方法，一個是add(E e),另一個是add(int index, E e)。add本身很簡單，但是要處理動態數組，即數組大小不滿足的時候，擴大數組的內存。具體的代碼如下：

    public void add(E e){isCapacityEnough(size + 1);elementData[size++] = e;}

方法isCapacityEnough就是來判斷是否需要擴容，傳入的參數就是最小的擴容空間。因為add一個元素，所以最小的擴容空間，即新的長度是所有元素+ 1。這里的size就是真正的元素個數。

   private void isCapacityEnough(int size){if (size > DEFAULT_CAPACITY){explicitCapacity(size);}if (size < 0){throw new OutOfMemoryError();}}

判斷擴容的方法也很簡單，判斷需要擴容的空間是不是比默認的空間大。如果需要的空間比默認的空間大，就調用explicitCapacity進行擴容。這里有個size小于0的判斷，出現size小于0主要是因為當size超過Integer.MAX_VALUE就會變成負數。

    private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;private void explicitCapacity(int capacity){int newLength = elementData.length * 2;if (newLength - capacity < 0){newLength = capacity;}if (newLength > (MAX_ARRAY_LENGTH)){newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);}elementData = Arrays.copyOf(elementData, newLength);}

上面的代碼是擴容的代碼，首先，定義一個數組最大的容量的常量為最大值，這個值按照官方的源碼中的解釋是要有些VM保留了數組的頭部信息在數組中，因此實際存放數據的大小就是整數的最大值 - 8
然后設定一個要擴容的數組的大小，雖然上面說了有一個擴容空間的值 size + 1 ，這個是實際我們最小需要擴容的大小。但為了繼續增加元素，而不頻繁的擴容，因此一次性的申請多一些的擴容空間。這里newLength 打算申請為數組長度的2倍，然后去判斷這個長度是否滿足需要的擴容空間的值。即有了后續的兩段代碼

      if (newLength - capacity < 0){newLength = capacity;}if (newLength > (MAX_ARRAY_LENGTH)){newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);}

如果2倍的長度仍然不滿足，則申請到需要的擴容長度。在我們只增加一個元素的情況下，這個判斷是永遠不會生效的，但是如果有addAll方法，則增加的元素很多，就要導致一次申請2倍的長度是不夠的。第二個判斷是判斷newLength的長度如果超過上面定義的數組最大長度則判斷要需要的擴容空間是否大于數組最大長度，如果大于則newLength為 MAX_VALUE ，否則為 MAX_ARRAY_LENGTH。
最后，真正實現數組擴容到設定長度的方法就沒意思了，調用Arrays.copyOf(elementData, newLength)得到一個擴容后的數組。
add的另一個重載方法也很簡單。

   public void add(int index, E e) {//判斷是不是越界checkRangeForAdd(index);//判斷需不需要擴容isCapacityEnough(size + 1);//將index的元素及以后的元素向后移一位System.arraycopy(elementData,index,elementData,index + 1,size - index);//將index下標的值設為eelementData[index] = e;size++;}

    private void checkRangeForAdd(int index){//這里index = size是被允許的，即支持頭，中間，尾部插入if (index < 0 || index > size){throw new IndexOutOfBoundsException("指定的index超過界限");}}

java arraylist方法、至此，一個簡單的add方法就實現完了。

get方法

get方法用來得到容器中指定下標的元素。方法實現比較簡單，直接返回數組中指定下標的元素即可。

    private void checkRange(int index) {if (index >= size || index < 0){throw new IndexOutOfBoundsException("指定的index超過界限");}}public E get(int index){checkRange(index);return (E)elementData[index];}

indexOf方法

indexOf方法用來得到指定元素的下標。實現起來比較簡單，需要判斷傳入的元素，代碼如下：

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

判斷傳入的元素是否為null，如果為null，則依次與null。如果不為空，則用equals依次比較。匹配成功就返回下標，匹配失敗就返回-1。

contains方法

contains用來判斷該容器中是否包含指定的元素。在有了indexOf方法的基礎上，contains的實現就很簡單了。

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

size方法

java ArrayList，size方法用來得到容器類的元素個數，實現很簡單，直接返回size的大小即可。

    public int size(){return size;}

isEmpty方法

isEmpty方法用來判斷容器是否為空，判斷size方法的返回值是否為0即可。

    public boolean isEmpty(){return size() == 0;}

remove方法

remove方法是用來對容器類的元素進行刪除，與add一樣，remove方法也有兩個重載方法，分別是
remove(Object o)和remove(int index)

     public E remove(int index) {E value = get(index);int moveSize = size - index - 1;if (moveSize > 0){System.arraycopy(elementData,index + 1, elementData,index,size - index - 1);}elementData[--size] = null;return value;}public boolean remove(Object o){if (contains(o)){remove(indexOf(o));return true;}else {return false;}}

第一個remove方法是核心方法，首先得到要刪除的下標元素的值，然后判斷index后面的要前移的元素的個數，如果個數大于零，則調用庫方法，將index后面的元素向前移一位。最后elementData[--size] = null;縮減size大小，并將原最后一位置空。
第二個remove方法不需要向第一個方法一樣，需要告訴使用者要刪除的下標對應的元素，只需要判斷是否刪除成功即可。如果要刪除的元素在列表中，則刪除成功，如果不在則失敗。因此調用contains方法就可以判斷是否要刪除的元素在列表中。在則調用remove(int index),不在則返回失敗。