實(shí)現(xiàn)一個(gè)ArrayList過程

NickZhou 發(fā)布于2019-08-16 13:33 / 1410人閱讀

摘要：構(gòu)造器一個(gè)無參構(gòu)造器一個(gè)參數(shù)為型的有參構(gòu)造器一個(gè)參數(shù)為型的有參構(gòu)造器。參數(shù)為型的構(gòu)造器用來實(shí)現(xiàn)將其他繼承類的容器類轉(zhuǎn)換成。此處僅實(shí)現(xiàn)前兩種。默認(rèn)的大小無參構(gòu)造器中的是定義的私有變量，默認(rèn)值是，用來創(chuàng)建一個(gè)大小為的數(shù)組。

前言

ArrayList，可隨意添加和刪除元素而不許考慮數(shù)組的大小。

構(gòu)造器

一個(gè)無參構(gòu)造器、一個(gè)參數(shù)為int型的有參構(gòu)造器、一個(gè)參數(shù)為Collection型的有參構(gòu)造器。參數(shù)為Collection型的構(gòu)造器用來實(shí)現(xiàn)將其他繼承Collection類的容器類轉(zhuǎn)換成ArrayList。此處僅實(shí)現(xiàn)前兩種。

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

無參構(gòu)造器中的DEFAULT_CAPACITY是定義的私有變量，默認(rèn)值是10，用來創(chuàng)建一個(gè)大小為10的數(shù)組。有參構(gòu)造器中，則是通過int參數(shù)來生成指定大小的Object數(shù)組。而可以看到elementData才是真正的用來存儲(chǔ)元素的數(shù)組。

add方法

核心內(nèi)容是往容器中添加元素，add方法有兩個(gè)重載方法，一個(gè)是add（E e），另一個(gè)是add（int index，E e），但是其還要處理動(dòng)態(tài)數(shù)組，即數(shù)組大小不滿足的時(shí)候，擴(kuò)大數(shù)組的內(nèi)存。

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

isCapacityEnough方法用來判斷是否需要擴(kuò)容，傳入的參數(shù)就是最小的擴(kuò)容空間。因?yàn)閍dd一個(gè)元素，所以最小的擴(kuò)容空間，即所有元素+1，這里的size就是真正的元素個(gè)數(shù)。

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

判斷需要擴(kuò)容的空間是不是比默認(rèn)的空間大，如果需要的空間比默認(rèn)的空間大，就調(diào)用explicitCapacity繼續(xù)擴(kuò)容，這里有個(gè)size小于0的判斷，出現(xiàn)size小于0主要因?yàn)楫?dāng)size超過Integer.MAX_VALUE就會(huì)變成負(fù)數(shù)。

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);
}

首先，定義一個(gè)數(shù)組最大的容量的常理為最大值，這個(gè)值按照官方的源碼中的解釋是要有些VM保留了數(shù)組的頭部信息在數(shù)組中，因此實(shí)際存放數(shù)據(jù)的大小就是整數(shù)的最大值 - 8.

接著設(shè)定一個(gè)要擴(kuò)容的數(shù)組的大小，雖然上面說了有一個(gè)擴(kuò)容空間的值size+1，這個(gè)是實(shí)際我們最小需要擴(kuò)容的大小。但為了繼續(xù)增加元素，而不頻繁的擴(kuò)容，因此一次性的申請(qǐng)多一些的擴(kuò)容空間。newlength打算申請(qǐng)為數(shù)組長(zhǎng)度的2倍，然后去判斷這個(gè)長(zhǎng)度是否滿足需要的擴(kuò)容空間的值，即有了后續(xù)的兩段代碼

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

如果2倍的長(zhǎng)度仍然不滿足，則申請(qǐng)到需要的擴(kuò)容長(zhǎng)度。在我們只增加一個(gè)元素的情況下，這個(gè)判斷是永遠(yuǎn)不會(huì)生效的，但是如果有addAll方法，則增加的元素很多，就要導(dǎo)致一次申請(qǐng)2倍的長(zhǎng)度是不夠的。第二個(gè)判斷是判斷newLength的長(zhǎng)度如果超過上面定義的數(shù)組最大長(zhǎng)度則判斷要需要的擴(kuò)容空間是否大于數(shù)組最大長(zhǎng)度，如果大于則newLength為 MAX_VALUE ，否則為 MAX_ARRAY_LENGTH。

最后，調(diào)用Arrays.copyOf(elementData, newLength)得到一個(gè)擴(kuò)容后的數(shù)組。

add的另一個(gè)重載方法如下

public void add(int index, E e) {
 //判斷是不是越界
 checkRangeForAdd(index);
 //判斷需不需要擴(kuò)容
 isCapacityEnough(size + 1);
 //將index的元素及以后的元素向后移一位
 System.arraycopy(elementData,index,elementData,index + 1,size - index);
 //將index下標(biāo)的值設(shè)為e
 elementData[index] = e;
 size++;
}
private void checkRangeForAdd(int index){
 //這里index = size是被允許的，即支持頭，中間，尾部插入
 if (index < 0 || index > size){
  throw new IndexOutOfBoundsException("指定的index超過界限");
 }
}

get方法

用來得到容器中指定下標(biāo)的元素

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方法

用來得到指定元素的下標(biāo)，判斷傳入的元素是否為null，如果為null，則依次與null。如果不為空，則用equals依次比較。匹配成功就返回下標(biāo)，匹配失敗就返回-1。

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

contains方法

用來判斷該容器中是否包含指定的元素。在有了indexOf方法的基礎(chǔ)上，contains的實(shí)現(xiàn)就很簡(jiǎn)單了。

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

size方法

用來得到容器類的元素個(gè)數(shù)，實(shí)現(xiàn)很簡(jiǎn)單，直接返回size的大小即可。

public int size(){
 return size;
}

isEmpty方法

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

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

remove方法

用來對(duì)容器類的元素進(jìn)行刪除，與add一樣，remove方法也有兩個(gè)重載方法，分別是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;
 }
}

第一個(gè)remove方法是核心方法，首先得到要?jiǎng)h除的下標(biāo)元素的值，然后判斷index后面的要前移的元素的個(gè)數(shù)，如果個(gè)數(shù)大于零，則調(diào)用庫(kù)方法，將index后面的元素向前移一位。最后elementData[--size] = null;縮減size大小，并將原最后一位置空。

第二個(gè)remove方法不需要向第一個(gè)方法一樣，需要告訴使用者要?jiǎng)h除的下標(biāo)對(duì)應(yīng)的元素，只需要判斷是否刪除成功即可。如果要?jiǎng)h除的元素在列表中，則刪除成功，如果不在則失敗。因此調(diào)用contains方法就可以判斷是否要?jiǎng)h除的元素在列表中。在則調(diào)用remove(int index),不在則返回失敗。