實現一個ArrayList過程

NickZhou 發布于2019-08-16 13:33 / 1377人閱讀

摘要：構造器一個無參構造器一個參數為型的有參構造器一個參數為型的有參構造器。參數為型的構造器用來實現將其他繼承類的容器類轉換成。此處僅實現前兩種。默認的大小無參構造器中的是定義的私有變量，默認值是，用來創建一個大小為的數組。

前言

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

構造器

一個無參構造器、一個參數為int型的有參構造器、一個參數為Collection型的有參構造器。參數為Collection型的構造器用來實現將其他繼承Collection類的容器類轉換成ArrayList。此處僅實現前兩種。

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

無參構造器中的DEFAULT_CAPACITY是定義的私有變量，默認值是10，用來創建一個大小為10的數組。有參構造器中，則是通過int參數來生成指定大小的Object數組。而可以看到elementData才是真正的用來存儲元素的數組。

add方法

核心內容是往容器中添加元素，add方法有兩個重載方法，一個是add（E e），另一個是add（int index，E e），但是其還要處理動態數組，即數組大小不滿足的時候，擴大數組的內存。

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下標的值設為e
 elementData[index] = e;
 size++;
}
private void checkRangeForAdd(int index){
 //這里index = size是被允許的，即支持頭，中間，尾部插入
 if (index < 0 || index > size){
  throw new IndexOutOfBoundsException("指定的index超過界限");
 }
}

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

用來得到指定元素的下標，判斷傳入的元素是否為null，如果為null，則依次與null。如果不為空，則用equals依次比較。匹配成功就返回下標，匹配失敗就返回-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方法的基礎上，contains的實現就很簡單了。

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

size方法

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

public int size(){
 return size;
}

isEmpty方法

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

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

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),不在則返回失敗。

云服務器 GPU云服務器寫一個存儲過程 webrtc具體實現過程數據倉庫的實現過程實現一個webrtc

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71914.html

數組和列表的轉換問題

摘要：以下指代數組，指代數組列表。常見的轉換方法是或。在的使用過程中需要注意，當要轉換的長度小于的時，不要試圖通過傳入形參的方式進行轉換，雖然這在的長度大于時不會出現問題。所以，極度建議在轉換之前初始化的長度為的，并且使用返回值重新給賦值。 Array 和 List 都是我們在開發過程中常見的數據結構。我們都知道 Array 是定長的，List 是可變長。而且，List 的實現類 Array...

ChristmasBoy 2019-08-16 14:37 評論0 收藏0
Java筆記-容器源碼(持續更新)

摘要：加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行操作即重建內部數據結構，從而哈希表將具有大約兩倍的桶數。成員變量每個對由封裝，存在了對象數組中。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 LinkedLis...

mrli2016 2019-08-14 12:07 評論0 收藏0
Java容器類研究4：ArrayList

摘要：顯然，開發人員認為通過下標遍歷的數組結構更加高效。在進行分裂時，原始保留中部至末尾的元素，新的保留原起始位置到中部的元素。同樣，也會進行重新賦值，使得在使用前與保持一致。在遍歷時，會調用方法，將動作施加于元素之上。 java.util.ArrayList ArrayList繼承自AbstractList，AbstractList為隨機訪問數據的結構，如數組提供了基本實現，并且提供了It...

xfee 2019-08-15 12:08 評論0 收藏0
深入了解Java集合中的ArrayList

摘要：實現了接口，所以包含的基本方法新增，刪除，插入等都實現了。線程安全問題在多線程情況下有線程進行修改時，是線程不安全的。線程安全性問題，取決于如何應用。反映的是當前數組中存了多少數據，而則反映的是內部數組的容量。什么是ArrayList ArrayList 是一個可擴容數組Resizable-array,它實現了List接口的所有方法。從對ArrayList的簡單描述中我們可以得出...

zeyu 2019-08-16 16:59 評論0 收藏0
Java集合干貨——ArrayList源碼分析

摘要：關于的具體實現，一些基本的都也知道，譬如數組實現，線程不安全等等，但是更加具體的就很少去了解了，例如初始化的長度，擴容等。前言在之前的文章中我們提到過ArrayList，ArrayList可以說是每一個學java的人使用最多最熟練的集合了，但是知其然不知其所以然。關于ArrayList的具體實現，一些基本的都也知道，譬如數組實現，線程不安全等等，但是更加具體的就很少去了解了，例如：...

Render 2019-08-15 13:50 評論0 收藏0
Java集合干貨——ArrayList源碼分析

摘要：關于的具體實現，一些基本的都也知道，譬如數組實現，線程不安全等等，但是更加具體的就很少去了解了，例如初始化的長度，擴容等。前言在之前的文章中我們提到過ArrayList，ArrayList可以說是每一個學java的人使用最多最熟練的集合了，但是知其然不知其所以然。關于ArrayList的具體實現，一些基本的都也知道，譬如數組實現，線程不安全等等，但是更加具體的就很少去了解了，例如：...

wupengyu 2019-08-15 13:39 評論0 收藏0