背景
想進步，想學習了，反正面試都要問的，還不如早點看了好，探索ArrayList源代碼是基于JDK1.8版本的，相比以前的版本不知道有沒有優化，畢竟沒看過之前版本的底層代碼，一般看底層代碼前我都習慣先閱讀下該類的注釋說明，也不知道在哪里養成的習慣，相信大家都寫過應用代碼，既然寫過，那也深知注釋對于一個使用者來說是多么的重要，決定了它是否能夠正確的使用，所以這是一個好習慣，
閱讀注釋
看到這不知道你們有沒有很驚訝，反正我倒是一驚，所以我說看注釋很重要！！！如果是你寫代碼給別人看，除了看具體代碼之外，看注釋就是最好的理解方式了，一語道破很多原理，要求不高的我都覺得可以不用看代碼實作了，所以接下來會繼續閱讀注釋，
這就變相地在說，ArrayList中的get/set效率比LinkedList高，這不正好驗證了我們常說的ArryList存取快，插入洗掉慢，我想它的時間復雜度說明了一切，雖然這里只是給出了結論，在這里順便提供下有趣的時間復雜度的介紹文章，便于理解，
簡單地說陣列會自動擴容，
在這里我將amount翻譯成次數，這個單詞本意是數量的意思，基于我對ArrayList的了解，當容量不足時，它是需要擴充容量的，就上面咱們提到的自動擴容，每次容量不足時都需要自動擴容，若一開始就設定好這個容量，那么就減少了自動擴容的次數，所以我將它翻譯成次數，它的意思就是讓你提前設定好容量大小，以便容量不足時需要消耗時間去自動擴容，
大致意思是ArrayList不是執行緒安全，所以在多執行緒環境下要在外部控制同步防止資料紊亂，
截圖中應該講的挺明白了！
Fail-Fast：快速失敗，我也是第一次聽說該術語，它僅僅用于檢測BUG，說明不了什么問題，
資料結構
按照順序先來看下ArrayList都具有哪些成員屬性，
//支持序列化、可克隆、隨機訪問
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//序列化標識
private static final serialVersionUID = 8683452581122892189L;
//默認初始值容量大小10
private static final DEFAULT_CAPACITY = 10;
//空陣列實體，主要用來做賦值
private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/zlia/archive/2020/12/16/{};
//空陣列實體，當采用默認的空建構式時采用該實體作為默認值
//該實體與 EMPTY_ELEMENTDATA 被區分開來以便知道當第一個元素被添加時陣列該擴充多大，簡單來說該屬性會參與到計算當中，而 EMPTY_ELEMENTDATA只是用作簡單的賦值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList中的元素被添加到該陣列中
//ArrayList的容量大小是該陣列的長度大小
//空建構式的 elementData被賦值為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，當添加第一個元素時，elementData陣列大小將會被擴充到默認容量大小10
//該物件加上 transient 修飾符表示不對該屬性進行序列化
transient Object[] elementData;
//ArrayList容量大小，意指它包含元素的個數
private int size;
//我們都知道定義一個陣列的大小是 int 型別，那么也就意味著最大的陣列大小應該是Integer.MAX_VALUE，但是這里為啥要減去8呢？
//查閱資源發現大部分的人都在說8個位元組是用來存盤陣列的大小，半信半疑
//分配最大陣列，某些VM會在陣列中存盤header word，按照上面的說法指的應該是陣列的大小
//若嘗試去分配更大的陣列可能會造成 OutOfMemoryError: 定義的陣列大小超過VM上限
//不同的作業系統對于不同的JDK可能分配的記憶體會有所差異，所以8這個數字可能是為了保險起見
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//ArrayList結構被修改的次數
//該欄位主要針對迭代器與子集使用，若該屬性被出乎意料的改變了，呼叫迭代器的相關方法，如 next、 remove、previous、set、add則會拋出 ConcurrentModificationException例外，該//情況其實就是上面提到的fail-fast
//嚴格上來說，該欄位并不算是結構被修改的次數，在判斷是否需要擴容時，它是首先進行增加在判斷，不過這不影響，該欄位僅用來判斷是否與其他欄位相等
protected transient int modCount = 0;
}
這些成員屬性都很容易理解，加上提供了注釋，所以這邊就不做多的闡述！
建構式
接下來介紹ArrayList提供的建構式，
/**
* 構造一個指定初始容量大小的空陣列，相當于 new Object[initialCapacity]
* 若入參initialCapacity大于0，則創建具有指定大小的空陣列，并讓elementData指向該陣列
* 若入參initialCapacity等于0，則elementData指向已經創建好的空陣列
* 若入參initialCapacity小于0，則拋出引數例外
* @param initialCapacity 初始容量大小
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
* 構造一個初始容量為10的空陣列，并讓elementData指向已經創建好的空陣列
* 初始容量并不是在這里設定，而是在添加第一個元素時進行初始化
*/
public ArrayLlist() {
this.elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 構建一個包含指定collection集合的陣列，ArrayList容量大小和該集合大小一致，指定集合中的元素按照迭代器的順序排列
* collection集合型別有Map、set、List等子類，所以入參可以是多種型別
* collection集合轉換成陣列，elementData指向該陣列，size成員屬性被賦值為collection集合長度
* 若該陣列大小大于0，則判斷陣列型別是否是Ojbect[],若不是則創建一個新的陣列，并拷貝elementData陣列中的內容
* 若該陣列大小等于0，則elementData指向空陣列
* collection集合不可能創建長度為負數的集合
* @param c 指定集合
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//c.toArray 可能不會回傳正確的Object[]型別，這邊可能會利用多型的性質，如 A a = new B()
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//空陣列
this.elementData = EMPTY_ELEMENTDATA;
}
}
-
若已經提前知道陣列容量，則建議使用new ArrayList(initialCapacity)
-
若不知道陣列容量的話，那就沒辦法了
-
ArrayList(Collection c)一般是在包含關系的情況下使用
方法說明
接下來按照類的宣告順序介紹方法，有必要的情況下結合例子進行說明，
縮小陣列大小空間
/**
* 縮小ArrayList物件的容量到當前陣列的大小，應用可以呼叫該方法來最小化ArrayList物件的存盤空間，簡單來說就是節約空間，去掉沒有用到的剩余陣列空間
* modCount 是記錄ArrayList修改結構的次數，節約陣列空間就是減少了陣列的大小
* size 是陣列填充了元素的個數，實實在在的大小，而 elementData.length 是陣列的總容量大小，也就是說只有當填充/洗掉元素時size的大小才會變化
* 而當進行擴容時 elementData.length 才會變化，畢竟陣列的長度變大了
* 若size小于elementData.length，則判斷 size是否等于0
* 若size等于0，則將 elementData 指向空陣列
* 若size不等于0，則創建一個大小為size的陣列，并將elementData中原有的元素拷貝到新陣列中，同時更新elementData指向新陣列，從而完成節約資料空間的作用
* size的長度是不可能大于elementData.length
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/(size == 0) ? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
自定義容量 + 擴容機制
自定義容量可以在創建ArrayList物件時設定，若后期發現容量不足總不能手動去改數值吧，故而提供了其他方法去自定義容量，
/**
* 增加ArrayList物件的容量，在必要情況下，入參minCapacity至少要確保能容納元素的數量
* 若 elementData 不等于空陣列，則minExpand = 0，否則minExpand = DEFAULT_CAPACITY = 10
*
* 假設去掉設定minExpand的值的陳述句會造成的影響：
* 若采用new ArrayList的方式創建物件，則表示在第一次添加元素時，自動將容量擴充到10，而若在此之前先手動擴充容量，如果該值小于10，則會擴容一次，而當容量不足時，
* 又會擴容一次，總的來說會頻繁的進行擴容，而為什么一開始要設定成10呢，微軟工程師做過調研，認為該數字比較常用，實際上設定成其它值也是沒問題的
*
* 擴容機制為了保證所有的元素都能被容納，自定義容量與自動擴容的數值會進行比較，取較大值作為擴容的引數，故而有了minCapacity與minExpand的比較
* 若minCapacity大于minExpand，則呼叫ensureExplicitCapacity方法
*
* @param minCapacity 手動擴充的容量大小
*/
public void ensureCapacity (int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* modCount指的是記錄修改結構的次數，但若是minCapacity 小于 elementData.length，則結構并沒有修改，在這點上不是很難理解
* 判斷完需要擴容的引數，接下來應該判斷該引數是否大于預先定義好的總容量大小，還是取較大值
* 若minCapacity大于elementData.length，則呼叫grow方法開始擴容
*
* @param minCapacity 手動擴充的容量大小
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* oldCapacity >> n：oldCapacity除以2的n次方
*
* 首先獲取當前陣列的容量大小，獲取自動擴容時的容量大小為 oldCapacity + oldCapacity/2 = 1.5 * oldCapacity，也就是說兩次擴容之間是1.5倍的關系
* 判斷手動擴充的容量是否大于自動擴充的容量
* 若大于，則自動擴容的容量修改為手動擴充的容量，即 newCapacity = minCapacity，否則newCapacity不變，即采用自動擴充的容量
* 為了防止記憶體溢位，擴容并不是無止境的擴充，當大于一個臨界點MAX_ARRAY_SIZE時，就不允許在采用自動擴容的容量大小，而是取最大值或臨界點
*
* 參考hugeCapacity方法：
* 當程式執行到①時，我們可以知道 newCapacity >= minCapacity（指的是賦值之后的關系）
* 若MAX_ARRAY_SIZE大于newCapacity，則就開始創建長度為newCapacity的新陣列，三者的關系為 MAX_ARRAY_SIZE > newCapacity >= minCapacity
* 若MAX_ARRAY_SIZE小于newCapacity，則進入到hugeCapacity方法，但此時我們不知道minCapacity 與 MAX_ARRAY_SIZE的大小關系
* 若minCapacity大于MAX_ARRAY_SIZE，則采用最大值，不允許無限制的手動設定擴充容量，不過最大值有可能會出現記憶體溢位
* 三者關系為：newCapacity >= minCapacity > MAX_ARRAY_SIZE
* 若minCapacity小于MAX_ARRAY_SIZE，則采用臨界值，該臨界值是保證在不同的作業系統下不會發生記憶體溢位， 三者關系為：newCapacity > MAX_ARRAY_SIZE > minCapacity
* 得出結論：
* 添加元素時會先到底臨界值，此時不會發生記憶體溢位，若在往上增長則達到最大值，最大值有可能發生記憶體溢位
*
* @param minCapacity 手動擴充的容量大小
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; --------------------> ① 手動添加
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/Arrays.copyOf(elementData, newCapacity);
}
/**
* 判斷入參minCapacity 是否大于 MAX_ARRAY_SIZE
* 若 minCapacity > MAX_ARRAY_SIZE，則回傳值是最大值
* 若 minCapacity <= MAX_ARRAY_SIZE，則回傳值是臨界值
*
* @param minCapacity 手動擴充的容量大小
* @return 容量大小結果值
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 計算出要擴充的容量大小并擴容
*
* @param minCapacity 手動擴充的容量大小
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 只有在采用new ArrayList()的方式創建物件后，elementData才會等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而以其他方式創建物件后都具有一定的容量大小
* 若 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，比較手動擴容與自動擴容的容量大小，取較大值
* 若不相等，則采用手動擴容容量大小
*
* @param elementData 陣列
* @param minCapacity 手動擴充的容量大小
* @return 容量大小結果值
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
什么情況下會擴容
- 這個問題有點白問，當然了是陣列不夠用了才需要擴充容量了，不過它不是一個一個的擴充，而是采用一定的規則去擴充，回答的也有點傻！
自動擴容機制
- 每次自動擴容都以
1.5倍的關系進行增長，如果期間手動擴充容量，則會比較手動擴充的容量大小與1.5倍的容量大小，取較大值進行擴容， - 擴容是比較耗時的，應該盡力去避免，所以在初始化時就應該提供一個容量引數，
容量最大值
- 最大值是Interger.MAX_VALUE，但容易造成記憶體溢位，保險起見在容量等于Integer.MAX_VALUE - 8 的時候就應該停止擴充容量，
獲取元素
/**
* 獲取陣列中指定索引的元素
* @param index 指定索引
* @return 指定索引對應的元素
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
修改元素
/**
* 修改陣列中指定索引的值
* rangCheck檢查角標是否越界
* @param index 索引
* @param element 新元素，替換索引對應的值
* @return 舊元素，索引對應的值
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = https://www.cnblogs.com/zlia/archive/2020/12/16/elementData(index);
elementData[index] = element;
return oldValue;
}
添加/插入元素
/**
* 添加元素到陣列尾部，添加元素之前會先進行擴容判斷
* @param e 新元素
* @return 是否添加成功
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
/**
* 添加元素到陣列中的指定位置，添加元素之前會先進行擴容和角標越界判斷
* 插入程序中將index索引位置及后續的所有元素都將向右移動一格，同時將當前索引位置的值修改成新值
* 陣列擴容跟size屬性沒有任何關系，size只負責陣列中有多少個元素，插入元素后故而 + 1
* @param index 索引
* @param element 新元素
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 添加陣列到另外一個陣列中，從尾部開始追加
* 相當于合并兩個陣列
* @param c 陣列
* @return 陣列中的元素是否添加到另外一個陣列中
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 添加陣列到另外一個陣列中，從指定索引出開始添加
* 插入程序中將index索引位置及后續的任何元素都將往右移動 numNew 格，相當于是批量插入
* 相當于在插入前先將原有的元素都往右移動，預先留出空位來給后面要添加的元素
* @param index 索引
* @param c 陣列
* @return 陣列中的元素是否添加到另外一個陣列中
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
移除元素
/**
* 移除陣列中指定索引的值，移除元素之前會先進行角標越界判斷
* 移除程序中將index索引位置后續的所有元素都將向左移動一格
* 為了能讓GC盡可能地回收資源，主動將尾部位置設定成null
* @param index 索引
* @return 移除的舊值
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = https://www.cnblogs.com/zlia/archive/2020/12/16/elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 移除陣列中第一次出現的指定值
* @param o 指定元素
* @return 是否洗掉成功
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/**
* 移除從指定起始索引到指定結束索引之間的所有元素
* 移除包含fromIndex索引對應的值，但不包括toIndex索引對應的值
* 移除程序中將toIndex索引位置及其后續的所有元素往左移動 toIndex - fromIndex 格
*
* 看到這里的時候有些理解難題，在移除元素后索引位置上的元素主動設定成null，我明白這一點，不好理解的點在于演算法
* 假設如下：
* f t
* 1 2 3 4 5 6 7 8
*
* 移除3后的結果，注意4是不會被移除的：
* 1 2 6 7 8 9 null null
*
* 根據需求，我們知道要將8位置上的值設定成null，那么問題就在于我怎么才能知道7位置上的索引是多少呢？哦，是7，這個不算，演算法應該怎么寫呢？
* 所以我很好奇怎么是這個答案：size - (toIndex-fromIndex)，后面著重理解了一下：
*
* f t
* 1 2 6 7 8 9 null null
* <= size =>
* <= t-f =>
* <= ? =>
* 求?的值，也就是在求null的索引是多少，看上面的圖就應該比較好理解了（不知道看的懂不），size - (toIndex-fromIndex)就剛好是索引的值
*
* @param fromIndex 起始索引
* @param toIndex 結束索引
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 批量移除陣列中的指定陣列的元素
* @param c 指定移除的元素集合
* @return 是否移除成功
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
簡單方法
/**
* 獲取陣列中的元素個數
* @return 陣列中的元素個數
*/
public int size() {
return size;
}
/**
* 判斷是否是空元素陣列
* @return 陣列是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 采用正向遍歷的方式，獲取陣列中與指定元素相等的元素的索引
* 若存在多個元素，取第一次與指定元素相等的元素的索引
* 若找不到指定元素則回傳 -1
* 方法中通過equals判斷兩物件是否相等，若是呼叫Object#equals方法，是在判斷兩者的地址是否指向同一個
* 若物件中已經覆寫了Object#equals，則應該引起注意！
* @param o 指定元素
* @return 指定元素的索引
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 采用反向遍歷的方式，獲取陣列中與指定元素相等的元素的索引
* 若存在多個元素，取第一次與指定元素相等的元素的索引
* 若找不到指定元素則回傳 -1
* 方法中通過equals判斷兩物件是否相等，若是呼叫Object#equals方法，是在判斷兩者的地址是否指向同一個
* 若物件中已經覆寫了Object#equals，則應該引起注意！
* @param o 指定元素
* @return 指定元素的索引
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 呼叫該clone之前，該類要實作Cloneable，不然會拋出例外
* 陣列默認已經實作了Cloneable介面，直接呼叫方法即可，而且直接回傳對應的型別，不需要向下轉型，同時包含陣列元素
* 淺拷貝與深拷貝，舉個例子吧
* 比如A類中包含基本型別與B類，當呼叫A類clone方法后，兩個A物件肯定是不一致，不然就不叫做拷貝了，不過這不是關鍵
* 若A1物件中的B物件與A2物件中的B物件指向同一個物件，則認為它是淺拷貝，認為B沒有被拷貝新的一份
* 若兩者指向不相等的話，則認為深拷貝，認為B重新拷貝了一份，不過這通常需要我們自定義代碼，就像下面的方法一樣
* @return 克隆后的新物件
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/**
* 回傳一個包含所有串列元素的有序（按照添加順序）陣列
* 此方法是創建一個新陣列，方便使用者能夠隨便操作新陣列
* @return 新陣列
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 將串列的所有元素放入到指定陣列中并回傳
*
* 注意：T型別要么是陣列中資料的相同型別，要么是陣列中資料的父型別，運用多型性質
* 若傳入的新陣列容量 < 串列容量，則取它的型別別來創建一個包含串列元素的新陣列，并回傳
* 若傳入的新陣列容量 > 串列容量，則將串列中的元素按照順序拷貝到新陣列中，同時將新陣列中索引為size的值設定成null
*
* 一開始我也好奇為啥要在索引為size上設定個null呢？
* 看了注釋加上自我的理解，若傳入的新陣列是個空陣列的話，那么除了拷貝串列元素后剩余的所有空間的值都為null，此時在給索引為size的值設定成null似乎沒有多大
* 意思；另外一種情況是若傳入的新陣列不是個空陣列，那這個設定就有意義了，傳入的新陣列的某些元素會被串列元素覆寫，同時有個null，剩下的才是自己本身的資料，呈現這樣子一種效果
*
* List list = new ArrayList<>();
* list.add(11);
*
* Integer[] str = new Integer[]{1,2,3,4,5,6,7,8,9,10};
* Integer[] s1 = list.toArray(str);
*
* for (Integer s : s1) {
* System.out.println(s +",");
* }
*
* 輸出結果：11,null,3,4,5,6,7,8,9,10,
* 那么設定這個null的意義就在于能夠確定串列中元素個數（長度），但有個前提就是呼叫者知道鏈表中的所有節點資訊不存在null才有意義，目前我只有想到這一種情況下有用！
*
* @param a 指定陣列
* @return 填充完串列元素的指定陣列
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 獲取陣列中指定索引中的值
* @param index 指定索引
* @return 指定索引的元素
*/
E elementData(int index) {
return (E) elementData[index];
}
/**
* 判斷索引是否越界
* @param index 指定索引
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 判斷角標是否越界，該方法專門針對add 和 addAll方法
* @param index 指定索引
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 本質上該方法與移除元素沒啥區別
* @param index 索引
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
/**
* 清空元素，主動將陣列中的元素設定為null方便GC回收垃圾
*/
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 集合與陣列取交集
* 最終陣列中只包含與集合共有的元素，相當于在修改陣列
* @param c 指定集合
* @return 陣列元素是否被修改成功
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* 批量洗掉元素
* 若集合是否包含指定元素的結果與入參complement比較，
* 若complement是false，移除陣列與集合共有的元素
* 若complement是true，保留陣列與集合共有的元素，即交集
* @param c 指定集合
* @param complement 比較值
* @return 陣列元素是否被修改
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
/**
* 自定義序列化
* 若寫入程序中陣列結構被修改則會拋出例外
* 如果采用默認的序列化機制，空余的空間會作為null寫入本地檔案或者在網路中傳輸，耗費了不必要的資源
* 故而使用自定義序列化機制，僅寫入索引為(0，size）的有效元素以節省資源
* 默認的序列化機制會將非靜態與非瞬時（非transient修飾）寫入流中
* @param s 輸出流
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
int expectedModCount = modCount;
//執行默認序列化程序
s.defaultWriteObject();
//寫入元素個數
s.writeInt(size);
// 按順序寫入
for (int i=0; i 0) {
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
//將流中的元素寫入到陣列中
Object[] a = elementData;
for (int i=0; i action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/(E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 根據指定條件移除元素
* 筆者對BitSet也是第一次接觸，針對本文章它顯的不是很重要，故而大概了解了一下
*
* 該方法中將滿足條件的元素索引存放到BitSet中，同時記錄移除元素的個數removeCount
* 緊接著BitSet呼叫 nextClearBit方法，該方法根據指定的索引獲取沒有在BitSet中存放的下一個索引，直接上個例子吧
* BitSet removeSet = new BitSet();
* removeSet.set(1)
* removeSet.set(2)
* System.out.println(removeSet.nextClearBit(1)) --> 3
*
* 一開始已經在BitSet中存放了要移除的元素的索引，當呼叫nextClearBit方法回圈遍歷獲取到的索引就是要保留的元素的索引
* 故而直接獲取元素的值將其存放到陣列中，最后的陣列是按照保留元素的順序進行存放的
*
* 函式式介面中不能呼叫修改結構的方法
* @param filter 使用指定條件來過濾元素
* @return 是否移除成功
*/
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
/**
* 根據指定規則替換所有舊元素
* operator.apply方法：舊元素作為入參傳入，根據規則回傳新元素，然后進行替換
* operator.apply方法中不能呼叫修改結構的方法
* @param operator 指定規則，函式式介面
*/
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
/**
* 根據指定規則對陣列中的元素進行排序
* 若沒有指定規則則使用默認的升序進行排序
* 指定規則后會呼叫自定義比較器中的compare方法進行比較排序
* @param c 自定義比較器，覆寫compare方法
*/
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
/**
* 判斷陣列中是否包含指定集合中的所有元素
* 但凡集合中有一個元素不存在陣列中則回傳false
* @param c 指定集合
* @return 陣列中是否包含指定集合中的所有元素
*/
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
/**
* 先判斷當前物件與指定物件是否指向同一個物件，就是在判斷地址
* 緊接著判斷指定物件屬于List的子類
* 緊接著獲取兩個物件的迭代器
* 若兩個迭代器的元素個數不相等，則回傳false
* 若兩個迭代器的元素個數相等，則將兩個迭代器的元素進行對應的比較，但凡出現對應的元素不相等則回傳false
* @param o 指定物件
* @return 當前物件與指定物件是否相等
*/
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
/**
* 獲取哈希值
* @return 哈希值
*/
public synchronized int hashCode() {
return super.hashCode();
}
/**
* 獲取陣列元素的字串
* @return 陣列元素的字串
*/
public synchronized String toString() {
return super.toString();
}
/**
* 獲取分割迭代器
* 由于該方法涉及到另外一個介面，會另外新起一篇文章來講解該內容，這里就不做闡述
* 附上文章地址：http://zlia.tech/2019/08/28/explain-arraylist-spliterator-sourcecode
* @return
*/
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
迭代器
/**
* 回傳一個包含指定索引到結尾之間的元素的串列迭代器
* 元素之間按照順序排序
* @param index 起始索引
* @return 包含元素的串列迭代器
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* 回傳一個包含所有元素的串列迭代器
* @return 包含元素的串列迭代器
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* 獲取迭代器
* @return 迭代器
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* 迭代器，正向迭代
* 通過判斷是否存在下一個元素，若有則獲取，若沒有則說明迭代結束
* @param E 元素型別
*/
private class Itr implements Iterator<E> {
//下一個元素的索引
int cursor;
//當前元素的索引
int lastRet = -1;
int expectedModCount = modCount;
/**
* 初始化
*/
Itr() {}
/**
* 判斷是否存在下一個元素
* @return 是否存在下一個元素
*/
public boolean hasNext() {
return cursor != size;
}
/**
* 獲取下一個元素的值
* @return 下一個元素的值
*/
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
/**
* 移除迭代程序中當前索引的元素
* 初始化時當前索引為 -1
*/
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 遍歷元素，只能遍歷一次
* 在遍歷程序中呼叫remove方法需要注意，可能會拋出IllegalStateException例外
* 在移除程序中 lastRet 成員變數可能為是 -1，故而會拋出例外
* 與forEach的區別在于：可以遍歷多次
* @param consumer 函式式介面，宣告如何處理元素的函式
*
* List list = new ArrayList<>();
* list.add("1");
* list.add("2");
* list.iterator().forEachRemaining(str -> {
* System.out.println("str:" + str);
* });
*
* List<String> list = new ArrayList<>();
* list.add("1");
* list.add("2");
* list.add("3");
* list.add("4");
* list.add("5");
* Iterator<String> iterator = list.iterator();
* while (iterator.hasNext()) {
* String nextValue = https://www.cnblogs.com/zlia/archive/2020/12/16/iterator.next();
* if (nextValue.equals("3")) {
* iterator.forEachRemaining(str -> {
* System.out.println("內層：" + str);
* });
* }
* System.out.println("外層：" + nextValue);
* }
*
*/
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]); //迭代程序中依次傳入元素
}
cursor = i;
lastRet = i - 1;
checkForComodification();
}
/**
* 初始化時 modCount 與 expectedModCount 是相等的
* 但如果在遍歷的程序修改陣列結構的話，此時 modCount 會有所變化，導致兩者不相等，故而拋出例外，也就是我們上面提到的fast-failed例外
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* 串列迭代器，正向迭代
* 可獲取上一個元素、下一個元素及索引
*/
private class ListItr extends Itr implements ListIterator {
/**
* 初始化引數
*/
ListItr(int index) {
super();
cursor = index;
}
/**
* 判斷是否有前一個元素
* @return 是否有前一個元素
*/
public boolean hasPrevious() {
return cursor != 0;
}
/**
* 獲取下一個元素的索引
* @return 下一個元素的索引
*/
public int nextIndex() {
return cursor;
}
/**
* 獲取上一個元素的索引
* @return 上一個元素的索引
*/
public int previousIndex() {
return cursor - 1;
}
/**
* 獲取上一個元素
* 在獲取程序中會判斷該陣列結構是否被修改
* @return 上一個元素
*/
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
/**
* 隨著遍歷，索引是會向前移動，用指定元素替換索引處的元素
* @param e 指定元素
*/
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 隨著遍歷，索引是會向前移動，將指定元素添加到下一個索引位置上
* @param e 指定元素
*/
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
要理解迭代器，很關鍵的一個點就是cursor，它的位置決定了你呼叫方法的結果！
子集
/**
* 獲取指定起始索引到指定結束索引之間的元素，簡稱獲取指定子集
* 指定區間中的元素包括起始索引，不包括結束索引
* 若起始索引與結束索引相等，則回傳空元素
* 對子集的操作，即呼叫set、add、remove等方法將會影響到整個陣列
* 但在先獲取子集后，又對整個陣列的結構進行修改，這時在遍歷子集則會導致報錯，而對于整體的非結構性修改則不會報錯，不過依然會影響到子集
* 所以在獲取子集后最好不要修改陣列的結構
* @param fromIndex 起始索引
* @param toIndex 結束索引
* @return 指定區間中的所有元素，稱為子集
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
/**
* 判斷起始索引與結束索引
* 該判斷在子集中又獲取子集時顯得較為重要
* @param fromIndex 起始索引
* @param toIndex 結束索引
* @param size 陣列大小
*/
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
/**
* 子集物件，支持隨機訪問
*
* List<String> list = new ArrayList<>();
* list.add("1"); //0
* list.add("2"); //1
* list.add("3"); //2
* list.add("4"); //3
* list.add("5"); //4
* list.add("6"); //5
* list.add("7"); //6
* list.add("8"); //7
* list.add("9"); //8
* list.add("10"); //9
*
* List<String> sub = list.subList(1,9);
* 0,1,2,3,4,5,6,7
* 2,3,4,5,6,7,8,9
*
* sub.subList(2,8);
* 0,1,2,3,4,5
* 4,5,6,7,8,9
*
* 以上提供的方法只要是幫助大家去理解子集又獲取子集的例子，其中加入了索引（上）及索引對應的元素（下）
*
*/
private class SubList extends AbstractList<E> implements RandomAccess {
/**
* 指向呼叫者的參考，該變數特別是在子集中又子集時很關鍵，決定了是否理解該功能的重要因素
* ArrayList -> subList -> subList
* 當第一次呼叫subList獲取子集時，為了方便理解，稱為子集1，這個時候子集1中的parent指向了ArrayList，這點比較好理解
* 當子集1又獲取子集時，稱為子集2，這個時候子集2中的parent指向了子集1，依次類推
* 如果你仔細看了下面的方法后，你會知道它是如何呼叫的？例如子集2中呼叫add方法
* 子集2#add -> parent#add = 子集1#add -> parent#add = ArrayList#add，最終都會呼叫到最上層類
*
* 那么為什么要這么設計呢？何不子集2#add -> ArrayList#add 這樣子的呼叫呢？
* 理由在于modCount，它是指陣列結構被修改的次數，這邊就不再闡述何為結構被修改，假設下若按照 子集2#add -> ArrayList#add這樣子的順序呼叫的話
* ArrayList#modCount會正常變化，子集2#modCount也會正常變化，可參考add方法中的 this.modCount = parent.modCount 代碼片段，
* 按照上面的假設，此時只有ArrayList與子集2的modCount正常變化，但是子集1卻沒有變化，那當你在遍歷子集1時，它會首先判斷子集1的modCount是否與ArrayList的modCount相等
* 若不相等，則拋出例外，具體可看 checkForComodification 方法，所以子集2#add時，也必須同時修改子集1的modCount，故而如此設計
*
* 有一個點關鍵，我們說是因為modCount，而只有結構修改了modCount才會變化，才需要如此呼叫，那么如果modCount沒有被修改呢？
* 那就不需要那么麻煩了，呼叫流程就是我們所假設的如此了 子集2#add -> ArrayList#add
*
* 所以兩種設計就用到了兩個變數：parentOffset、offset
* 兩個變數分別針對兩種方式去呼叫
*/
private final AbstractList<E> parent;
/**
* 當前子集索引與父子集索引的偏移量，簡單地說就是子集2與子集1的索引偏移量，有一個等式
* index2：子集2的索引 parentOffset2：子集2的屬性
* index1：子集1的索引 parentOffset1：子集1的屬性
* index3:ArrayList的索引
* parentOffset2 + index2 = index1 + parentOffset1 = index3
* 做了那么多，無非就是把子集1與子集2與ArrayList三者關聯起來
*/
private final int parentOffset;
/**
* 當前子集索引與ArrayList索引的偏移量，簡單地說就是子集2與ArrayList的索引偏移量
* 在創建子集2時，會把子集1與ArrayList的索引偏移量傳給子集2，接著在加上子集2與子集1的索引偏移量就可以得到子集2與ArrayList的索引偏移量
*
* offset2：子集2與子集1的索引偏移量（fromIndex）
* offset1：子集1與ArrayList的索引偏移量（offset）
* offset：當前子集，也就是子集2與ArrayList的索引偏移量
* offset2 + offset1 = offset
*/
private final int offset;
/**
* 子集的元素個數
*/
int size;
/**
* 初始化引數
* @param parent 呼叫者
* @param offset 當前子集與ArrayList的索引偏移量
* @param fromIndex 子集的起始索引
* @param toIndex 子集的結束索引
*/
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
/**
* 將指定元素替換子集中的指定索引
* 指定索引的大小是相對于子集，故而加上offset
* 由于該方法并沒有修改結構，故而直接呼叫ArrayList的對應方法
* @param index 相對于子集的索引
* @param e 指定元素
* @return 舊元素
*/
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
/**
* 獲取子集中指定索引對應的元素
* 指定索引的大小是相對于子集，故而加上offset
* 由于該方法并沒有修改結構，故而直接呼叫ArrayList的對應方法
* @param index 相對于子集的索引
* @return 指定索引對應的元素
*/
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
/**
* 獲取子集的元素個數
*/
public int size() {
checkForComodification();
return this.size;
}
/**
* 子集中指定索引上添加元素
* 由于該方法修改了陣列結構，故而先呼叫上層子集的add方法，若沒有子集則直接是ArrayList
* @param index 相對于子集的索引
* @param e 添加的元素
*/
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
/**
* 移除子集中指定索引位置的元素
* 由于該方法修改了陣列結構，故而先呼叫上層子集的remove方法，若沒有子集則直接是ArrayList
* @param index 相對于子集的索引
* @return 移除的元素
*/
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
/**
* 移除子集中指定索引范圍的所有元素
* 由于該方法修改了陣列結構，故而先呼叫上層子集的removeRange方法，若沒有子集則直接是ArrayList
* @param fromIndex 相對于子集的起始索引
* @param toIndex 相對于子集的結束索引
*/
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
/**
* 子集末尾上追加集合
* @param c 集合
* @return 是否添加成功
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
/**
* 子集中指定索引上添加集合
* @param index 相對于子集的索引
* @param c 集合
* @return 是否添加成功
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
/**
* 獲取子集迭代器
* @return 子集迭代器
*/
public Iterator iterator() {
return listIterator();
}
/**
* 獲取子集串列迭代器
* 串列迭代器中的元素是從指定索引開始到結束索引
* 這里就不對子集串列迭代器中的方法做再次解釋了，畢竟它跟ArrayList是類似的
* @param index 相對于子集的索引
* @return 串列迭代器
*/
public ListIterator listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = https://www.cnblogs.com/zlia/archive/2020/12/16/ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
/**
* 獲取子集
* 子集中又獲取子集
* @param fromIndex 相對于子集的起始索引
* @param toIndex 相對于子集的結束索引
* @return 子集
*/
public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
/**
* 校驗索引是否超出范圍
* @param index 相對于子集的索引
*/
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 校驗索引是否超出范圍
* @param index 相對于子集的索引
*/
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 索引超出范圍的錯誤資訊
* @param index 相對于子集的索引
* @return 錯誤資訊
*/
private String outOfBoundsMsg(int index) {
return"Index: "+index+", Size: "+this.size;
}
/**
* 校驗子集的結構修改次數是否與ArrayList一致
* 若先獲取子集后，接著在ArrayList上修改了結構，則會報錯
* 因為子集的modCount并沒有隨著ArrayList結構的修改而變化，導致了兩個變數不一致
*/
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
/**
* 由于該方法涉及到另外一個介面，會另外新起一篇文章來講解該內容，這里就不做闡述
* 附上文章地址：http://zlia.tech/2019/07/19/explain-arraylist-spliterator-sourcecode/
*/
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
其他方法
public class Arrays {
/**
* 拷貝指定陣列到新陣列中，根據指定的長度縮短或使用null擴充新陣列
* 新陣列與原始陣列的資料型別是完全一樣的
*/
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
/**
* 拷貝指定陣列到新陣列中，根據指定的長度縮短或使用null擴充新陣列
* 新陣列的資料型別由入參newType決定
* 判斷入參newType是否是Ojbect[]型別
* 若newType是Object[]型別，則創建一個長度為newLength的新陣列，并向下轉型為T[]型別
* 若newType不是Object[]型別，則創建一個長度為newLength的新陣列，但由于Array.newInstance回傳值是Object，故而向下轉型為T[]型別
* Array.newInstance與System.arraycopy屬于C底層代碼，故而查看不了具體實作
* System.arraycopye(param1, param2, param3, param4, param5)
* param1：原始陣列； param2：原始陣列復制元素的起始角標； param3：新陣列； param4：復制元素到新陣列的起始角標處；param5：原始陣列要從起始角標開始拷貝多少個元素到新陣列
* 從原始陣列param1的角標為param2開始復制param5個元素，到新陣列param3的角標為param4作為復制元素的起始點
* 回傳新陣列，此時已經填充好資料
*
* System.arraycopy性能趨勢：當陣列大小在百萬到千萬級別之間時所花費的時間差別不大，但是當達到億級別后，所花費的時間就會差很多
* 所以這也就導致了當陣列容量達到億級別后，手動呼叫ensureCapacity來預先設定容量大小所帶來的效率比自動擴容的銷量要低很多
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
}
總結
寫的內容有點過多，這里總結一下，方便獲取直接獲取結果！
-
ArrayList允許存放Null，
-
ArrayList內部通過陣列實作，大體上和Vector類似，除了是非執行緒安全，
-
ArrayList中的size、isEmpty、get、set、iterator、listIterator的時間復雜度是O(1)，而add操作的時間復雜度是O(n)，
-
由于ArrayList是非執行緒安全，所以多執行緒情況下要在外部控制執行緒安全或使用Collections.synchronizedList也行，
-
創建空引數的ArrayList物件時，默認的初始容量是10，當容量不足時，以1.5倍速度增長，
-
在構建ArrayList物件時，最好能預先設定容量大小，以免減少后期擴容花費的時間，
-
ArrayList容量的臨界值是最大值 - 8，這個數字8是因為在陣列中除了存盤元素之外還會存盤陣列的長度，而這些資料都在記憶體中，不同作業系統對記憶體的分配可能有所差異，減去8更多的是為了防止記憶體溢位，
-
ArrayList的Iterator迭代器中的forEachRemaining方法只能呼叫一次，且在該方法中不能呼叫remove方法，
-
ArrayList的ListIterator迭代器可反向遍歷串列，
-
在獲取ArrayList的子集后不能在做結構上的修改，
-
獲取迭代器后，不允許進行結構修改操作，因為會 expectedModCount 與 modCount 是否相等，
-
在遍歷程序中不允許修改結構，否則會拋出錯誤，
重點關注
默認每次自動擴容的關系是1.5倍 非執行緒安全 默認初始擴容值10 get/set時間復雜度O(1)，add時間復雜度O(n) 底層是通過陣列存盤元素，故是有序可重復集合
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/235907.html
標籤：其他