Java中數(shù)組容器(ArrayList)設(shè)的計與實現(xiàn)

更新時間：2022年07月07日 09:02:48 作者：一無是處的研究僧

本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作,感興趣的可以了解一下

本篇文章主要跟大家介紹我們最常使用的一種容器ArrayList、Vector的原理，并且自己使用Java實現(xiàn)自己的數(shù)組容器MyArrayList，讓自己寫的容器能像ArrayList那樣工作。在本篇文章當中首先介紹ArrayList的一些基本功能，然后去分析我們自己的容器MyArrayList應該如何進行設(shè)計，同時分析我們自己的具體實現(xiàn)方法，最后進行代碼介紹?。?！

ArrayList為我們提供了哪些功能

我們來看一個簡單的代碼，隨機生成100個隨機數(shù)，查看生成隨機數(shù)當中是否存在50這個數(shù)。

public class MyArrayList {

  public static void main(String[] args) {
    Random random = new Random();
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
      list.add(random.nextInt(5000));
    }
    for (int i = 0; i < 100; i++) {
      if (list.get(i) == 50) {
        System.out.println("包含數(shù)據(jù) 50");
      }
    }
    list.set(5, 1000);// 設(shè)置下標為5的數(shù)據(jù)為100
    list.remove(5);// 刪除下標為5的數(shù)據(jù)
    list.remove(new Integer(888));// 刪除容器當中的第一個值為5的數(shù)據(jù)
  }
}

上述代碼包含了ArrayList最基本的一個功能，一個是add方法，向數(shù)組容器當中加入數(shù)據(jù)，另外一個方法是get從容器當中拿出數(shù)據(jù)，set方法改變?nèi)萜骼锏臄?shù)據(jù)，remove方法刪除容器當中的數(shù)據(jù)。ArrayList的很多其他的方法都是圍繞這四個最基本的方法展開的，因此我們在這里不仔細介紹其他的方法了，后面我們自己實現(xiàn)的時候遇到問題的時候自然會需要設(shè)計相應的方法，然后我們進行解決即可。

現(xiàn)在我們就需要去設(shè)計一個數(shù)組容器實現(xiàn)“增刪改查”這四個基本功能。

設(shè)計原理分析

首先明白一點我們需要使用什么工具去實現(xiàn)這樣一個容器。我們手里有的工具就是Java提供給我們的最基本的功能——數(shù)組（這個好像是廢話，我們的標題就是數(shù)組容器??）。

當我們在Java當中使用數(shù)組去存儲數(shù)據(jù)時，數(shù)據(jù)在Java當中的內(nèi)存布局大致如下圖所示。

我們在設(shè)計數(shù)組容器這樣一個數(shù)據(jù)結(jié)構(gòu)的時候主要會遇到兩個問題：

我們申請數(shù)組的長度是多少。
當數(shù)組滿了之后怎么辦，也就是我們的擴容機制。

對于這兩個問題，首先我們數(shù)組的初始大小可以有默認值，在我們自己實現(xiàn)的MyArrayList當中設(shè)置為10，我們在使用類時也可以傳遞一個參數(shù)指定初始大小。第二個問題當我們的數(shù)組滿的時候我們需要對數(shù)組進行擴容，在我們實現(xiàn)的MyArrayList當中我們采取的方式是，新數(shù)組的長度是原數(shù)組的兩倍（這個跟JDK的ArrayList方式不一樣，ArrayList擴容為原來的1.5倍）。

代碼實現(xiàn)

為了讓我們的類實現(xiàn)的更加簡單我們在代碼當中就不做很多非必要的邏輯判斷并且拋出異常，我們的代碼只要能表現(xiàn)出我們的思想即可。

首先定義一個接口MyCollection，表示我們要實現(xiàn)哪些方法！

public interface MyCollection<E> {

  /**
   * 往鏈表尾部加入一個數(shù)據(jù)
   * @param o 加入到鏈表當中的數(shù)據(jù)
   * @return
   */
  boolean add(E o);

  /**
   * 表示在第 index 位置插入數(shù)據(jù) o
   * @param index
   * @param o
   * @return
   */
  boolean add(int index, E o);

  /**
   * 從鏈表當中刪除數(shù)據(jù) o
   * @param o
   * @return
   */
  boolean remove(E o);

  /**
   * 從鏈表當中刪除第 index 個數(shù)據(jù)
   * @param index
   * @return
   */
  boolean remove(int index);

  /**
   * 往鏈表尾部加入一個數(shù)據(jù)，功能和 add 一樣
   * @param o
   * @return
   */
  boolean append(E o);

  /**
   * 返回鏈表當中數(shù)據(jù)的個數(shù)
   * @return
   */
  int size();

  /**
   * 表示鏈表是否為空
   * @return
   */
  boolean isEmpty();

  /**
   * 表示鏈表當中是否包含數(shù)據(jù) o
   * @param o
   * @return
   */
  boolean contain(E o);

  /**
   * 設(shè)置下標為 index 的數(shù)據(jù)為 o
   * @param index
   * @param o
   * @return
   */
  boolean set(int index, E o);
}

我們的構(gòu)造函數(shù)，初始化過程。

  public MyArrayList(int initialCapacity) {
    this();
    // 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
    // 且數(shù)組的長度為 initialCapacity
    grow(initialCapacity); 
  }

  public MyArrayList() {
    this.size = 0; // 容器當中的數(shù)據(jù)個數(shù)在開始時為 0
    this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組
  }

我們需要實現(xiàn)的最復雜的方法就是add了，這個方法是四個方法當中最復雜的，其余的方法都相對比較簡單。

進入add方法之后，我們需要找到符合要求的最小數(shù)組長度，這個值通常是容器當中元素的個數(shù)size + 1 ，也就是圖中的minCapacity首先先比較這個值和現(xiàn)在數(shù)組的長度，如果長度不夠的話則需要進行擴容，將數(shù)組的長度擴大到原來的兩倍。
如果不需要擴容，則直接講元素放入到數(shù)組當中即可。

  @Override
  public boolean add(E o) {
    // 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
    ensureCapacity(size + 1);
    // 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
    elementData[++size] = o;
    return true;
  }

  /**
   * 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
   * @param capacity
   */
  public void ensureCapacity(int capacity) {
    int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  /**
   * 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
   * @param minCapacity
   * @return
   */
  private int findCapacity(int minCapacity) {
    /**
     * 如果 if 條件為 true 即 elementData 還是初始化時設(shè)置的空數(shù)組
     * 那么返回默認大小和需要大小的最大值 
     * 否則直接返回 minCapacity
     */
    if (elementData == EMPTY_INSTANCE){
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }

我們?yōu)槭裁葱枰獙?code>ensureCapacity的訪問限制權(quán)限設(shè)置為public？因為我們想讓用戶盡量去使用這個函數(shù)，因為如果我們?nèi)绻麑懗鱿旅孢@樣的代碼我們會一直申請內(nèi)存空間，然后也需要將前面的數(shù)組釋放掉，會給垃圾回收器造成更大的壓力。

    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) {
      list.add(i);
    }

下面我們對ArrayList的方法進行測試：

import java.util.ArrayList;

class Person {

  String name;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  @Override
  public String toString() {
    return "Person{" +
        "name='" + name + '\'' +
        '}';
  }
}


public class ArrayListTest {

  public static void main(String[] args) {
    ArrayList<Person> o1 = new ArrayList<>();
    o1.ensureCapacity(10000000);
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
      o1.add(new Person());
    }
    long end = System.currentTimeMillis();
    System.out.println("end - start: " + (end - start));
    ArrayList<Person> o2 = new ArrayList<>();
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
      o2.add(new Person());
    }
    end = System.currentTimeMillis();
    System.out.println("end - start: " + (end - start));
  }
}
// 輸出結(jié)果
end - start: 1345
end - start: 4730

從上面的測試結(jié)果我們可以看出提前使用ensureCapacity方法之后，程序執(zhí)行的時間更加短。

插入數(shù)據(jù)的add方法。

  @Override
  public boolean add(E o) {
    // 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
    ensureCapacity(size + 1);
    // 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
    elementData[size] = o;
    size++;
    return true;
  }

add在指定下標插入數(shù)據(jù)。

首先將插入下標后的數(shù)據(jù)往后移動一個位置
然后在將數(shù)據(jù)放在指定下標的位置。

  /**
   * 在下標 index 位置插入數(shù)據(jù) o
   * 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
   * 然后將 index 賦值為 o
   * @param index
   * @param o
   * @return
   */
  @Override
  public boolean add(int index, E o) {
    // 確保容器當中的數(shù)組長度至少為 size + 1
    ensureCapacity(size + 1);
    // 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
    // 做一個原地拷貝
    System.arraycopy(elementData, index, elementData, index + 1,
        size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
    elementData[index] = o;
    size++;
    return true;
  }

刪除數(shù)據(jù)的方法remove。

首先先刪除指定下標的數(shù)據(jù)。
然后將指定下標后的數(shù)據(jù)往前移動一個位置
在實際的操作過程中我們可以不刪除，直接移動，這樣也覆蓋被插入位置的數(shù)據(jù)了。

  /**
   * 移除下標為 index 的數(shù)據(jù)
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 需要被移動的數(shù)據(jù)個數(shù)
    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
          numMoved);
    elementData[--size] = null;

    return true;
  }

移除容器當中具體的某個對象。

  /**
   * 這個方法主要是用于溢出容器當中具體的某個數(shù)據(jù)
   * 首先先通過 for 循環(huán)遍歷容器當中的每個數(shù)據(jù)，
   * 比較找到相同的數(shù)據(jù)對應的下標，然后通過下標移除方法
   * @param o
   * @return
   */
  @Override
  public boolean remove(E o) {
    if (o == null) {
      for (int index = 0; index < size; index++)
        if (elementData[index] == null) {
          remove(index);
          return true;
        }
    } else {
      for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {
          remove(index);
          return true;
        }
    }
    return false;
  }

set方法，這個方法就很簡單了。

  @Override
  public boolean set(int index, E o) {
    elementData[index] = o;
    return true;
  }

重寫toString方法。

  @Override
  public String toString() {

    if (size <= 0)
      return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    for (int index = 0; index < size; index++) {
      builder.append(elementData[index].toString() + ", ");
    }
    builder.delete(builder.length() - 2, builder.length());
    builder.append("]");
    return builder.toString();
  }

測試代碼

public static void main(String[] args) {
    MyArrayList<Integer> list = new MyArrayList<>();
    for (int i = 0; i < 15; i++) {
      list.add(-i);
    }
    System.out.println(list.contain(5));
    System.out.println(list);
    list.remove(new Integer(-6));
    System.out.println(list);
    System.out.println(list.elementData.length); // 容器會擴容兩倍，而默認容器長度為10，因此這里是 20 
    list.add(5, 99999);
    System.out.println(list);
    System.out.println(list.contain(99999));
  }
// 代碼輸出
false
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14]
[0, -1, -2, -3, -4, -5, -7, -8, -9, -10, -11, -12, -13, -14]
20
[0, -1, -2, -3, -4, 99999, -5, -7, -8, -9, -10, -11, -12, -13, -14]
true

完整代碼

import java.util.ArrayList;
import java.util.Arrays;


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

  /**
   * 容器當中存儲數(shù)據(jù)的個數(shù)
   */
  private int size;

  /**
   * 容器中數(shù)組的默認長度
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * 存放具體數(shù)據(jù)的數(shù)組，也就是我們?nèi)萜鳟斨姓嬲鎯?shù)據(jù)的地方
   */
  Object[] elementData;

  /**
   * 當容器當中沒有數(shù)據(jù)將 elementData 設(shè)置為這個值，這個值是所有實例一起共享的
   */
  private static final Object[] EMPTY_INSTANCE = {};


  public MyArrayList(int initialCapacity) {
    this();
    // 增長數(shù)組的空間為 initialCapacity，即申請一個數(shù)組
    // 且數(shù)組的長度為 initialCapacity
    grow(initialCapacity);
  }

  public MyArrayList() {
    this.size = 0; // 容器當中的數(shù)據(jù)個數(shù)在開始時為 0
    this.elementData = EMPTY_INSTANCE; // 將數(shù)組設(shè)置為空數(shù)組
  }

  /**
   * 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 capacity
   * @param capacity
   */
  public void ensureCapacity(int capacity) {
    int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  /**
   * 這個函數(shù)的主要目的就是找到最終數(shù)組長度需求的容量
   * @param minCapacity
   * @return
   */
  private int findCapacity(int minCapacity) {
    /**
     * 如果 if 條件為 true 即 elementData 還是初始化時設(shè)置的空數(shù)組
     * 那么返回默認大小和需要大小的最大值
     * 否則直接返回 minCapacity
     */
    if (elementData == EMPTY_INSTANCE){
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }

  /**
   * 該函數(shù)主要保證 elementData 的長度至少為 minCapacity
   * 如果數(shù)組的長度小于 minCapacity 則需要進行擴容，反之
   * @param minCapacity 數(shù)組的最短長度
   */
  private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新的數(shù)組長度為原來數(shù)組長度的兩倍
    int newCapacity = oldCapacity << 1;

    // 如果數(shù)組新數(shù)組的長度 newCapacity 小于所需要的長度 minCapacity
    // 新申請的長度應該為 minCapacity
    if (newCapacity < minCapacity) {
      newCapacity = minCapacity;
    }
    // 申請一個長度為 newCapacity 的數(shù)組，在將原來數(shù)組
    // elementData 的數(shù)據(jù)拷貝到新數(shù)組當中
    elementData = Arrays.copyOf(elementData, newCapacity);
  }

  @Override
  public boolean add(E o) {
    // 這個函數(shù)的主要作用就是確保數(shù)組的長度至少為 size + 1
    ensureCapacity(size + 1);
    // 新增加了一個數(shù)據(jù)，容器的大小需要 + 1
    elementData[size] = o;
    size++;
    return true;
  }

  /**
   * 在下標 index 位置插入數(shù)據(jù) o
   * 首先先將 index 位置之后的數(shù)據(jù)往后移動一個位置
   * 然后將 index 賦值為 o
   * @param index
   * @param o
   * @return
   */
  @Override
  public boolean add(int index, E o) {
    // 確保容器當中的數(shù)組長度至少為 size + 1
    ensureCapacity(size + 1);
    // 將 elementData index位置之后的數(shù)據(jù)往后移動一個位置
    // 做一個原地拷貝
    System.arraycopy(elementData, index, elementData, index + 1,
        size - index); // 移動的數(shù)據(jù)個數(shù)為 size - index
    elementData[index] = o;
    size++;
    return true;
  }

  /**
   * 這個方法主要是用于溢出容器當中具體的某個數(shù)據(jù)
   * 首先先通過 for 循環(huán)遍歷容器當中的每個數(shù)據(jù)，
   * 比較找到相同的數(shù)據(jù)對應的下標，然后通過下標移除方法
   * @param o
   * @return
   */
  @Override
  public boolean remove(E o) {
    if (o == null) {
      for (int index = 0; index < size; index++)
        if (elementData[index] == null) {
          remove(index);
          return true;
        }
    } else {
      for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {
          remove(index);
          return true;
        }
    }
    return false;
  }

  /**
   * 移除下標為 index 的數(shù)據(jù)
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 需要被移動的數(shù)據(jù)個數(shù)
    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
          numMoved);
    elementData[--size] = null;

    return true;
  }

  @Override
  public boolean append(E o) {
    return add(o);
  }

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

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

  @Override
  public boolean contain(E o) {
    if (o == null) {
      for (int index = 0; index < size; index++)
        if (elementData[index] == null) {
          return true;
        }
    } else {
      for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {
          return true;
        }
    }
    return false;
  }

  @Override
  public String toString() {

    if (size <= 0)
      return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    for (int index = 0; index < size; index++) {
      builder.append(elementData[index].toString() + ", ");
    }
    builder.delete(builder.length() - 2, builder.length());
    builder.append("]");
    return builder.toString();
  }
    
  @Override
  public boolean set(int index, E o) {
    elementData[index] = o;
    return true;
  }


  public static void main(String[] args) {
    MyArrayList<Integer> list = new MyArrayList<>();
    for (int i = 0; i < 15; i++) {
      list.add(-i);
    }
    System.out.println(list.contain(5));
    System.out.println(list);
    list.remove(new Integer(-6));
    System.out.println(list);
    System.out.println(list.elementData.length);
    list.add(5, 99999);
    System.out.println(list);
    System.out.println(list.contain(99999));
  }
}

以上就是Java中數(shù)組容器(ArrayList)設(shè)的計與實現(xiàn)的詳細內(nèi)容，更多關(guān)于Java數(shù)組容器的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: