Java原生ArrayList解析

基本結構

Java的ArrayList是基于數組實現的動態列表，主要特點包括：

1. 動態擴容：當元素數量超過當前容量時，自動擴容（通常增加50%）

2. 快速隨機訪問：通過索引訪問元素的時間復雜度為O(1)

3. 有序集合：保持元素的插入順序

核心實現機制

// JDK中的關鍵字段
transient Object[] elementData; // 存儲元素的數組緩沖區
private int size; // 列表中實際元素數量
private static final int DEFAULT_CAPACITY = 10; // 默認初始容量

擴容機制：

private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍擴容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;elementData = Arrays.copyOf(elementData, newCapacity);
}

時間復雜度分析：

• 訪問元素：O(1)

• 添加元素（尾部）：平均O(1)，最壞O(n)（需要擴容）

• 插入/刪除元素（非尾部）：O(n)（需要移動元素）

自定義MyArrayList實現

package com.zsy;import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;/*** 自定義動態數組實現，支持泛型元素存儲和基本列表操作** <p>本實現提供類似Java ArrayList的核心功能，包括：</p>* <ul>*   <li>動態擴容機制（默認初始容量10，按2倍擴容）</li>*   <li>支持索引訪問和修改</li>*   <li>提供元素遍歷功能</li>*   <li>實現基本的增刪改查操作</li>* </ul>** <p><b>特性說明：</b></p>* <ul>*   <li>時間復雜度：隨機訪問O(1)，插入/刪除平均O(n)</li>*   <li>空間復雜度：O(n)</li>*   <li><b>非線程安全</b> - 多線程環境下需要外部同步</li>* </ul>** @param <E> 列表元素類型* @author zsy* @see List*/
public class MyArrayList<E> implements List<E> {/*** 當前列表中實際存儲的元素數量*/private int size;/*** 列表當前分配的存儲容量*/private int capacity;/*** 存儲列表元素的數組緩沖區*/private Object[] elements;/*** 構造一個初始容量為10的空列表*/public MyArrayList() {this(10);}/*** 構造具有指定初始容量的空列表** @param initialCapacity 初始容量* @throws IllegalArgumentException 如果初始容量為負數*/public MyArrayList(int initialCapacity) {if (initialCapacity < 0) {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}this.capacity = initialCapacity;this.elements = new Object[initialCapacity];}/*** 將指定元素追加到列表末尾** @param element 要添加的元素*/@Overridepublic void add(E element) {ensureCapacity();elements[size++] = element;}/*** 在列表的指定位置插入指定元素** @param element 要插入的元素* @param index 插入位置的索引* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic void add(E element, int index) {rangeCheckForAdd(index);ensureCapacity();System.arraycopy(elements, index, elements, index + 1, size - index);elements[index] = element;size++;}/*** 移除并返回列表中指定位置的元素** @param index 要移除元素的索引* @return 被移除的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E remove(int index) {rangeCheck(index);E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0) {System.arraycopy(elements, index + 1, elements, index, numMoved);}elements[--size] = null; // 清除引用，幫助GCreturn oldValue;}/*** 從列表中移除首次出現的指定元素** @param element 要移除的元素* @return 如果列表包含該元素則返回true*/@Overridepublic boolean remove(E element) {for (int i = 0; i < size; i++) {if (Objects.equals(element, elements[i])) {remove(i);return true;}}return false;}/*** 替換列表中指定位置的元素** @param index 要替換元素的索引* @param element 要存儲的元素* @return 先前在指定位置的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elements[index] = element;return oldValue;}/*** 返回列表中指定位置的元素** @param index 要返回元素的索引* @return 列表中指定位置的元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/@Overridepublic E get(int index) {rangeCheck(index);return elementData(index);}/*** 返回列表中的元素數量** @return 列表中的元素數量*/@Overridepublic int size() {return size;}/*** 返回此列表中元素的迭代器** @return 按適當順序包含此列表中所有元素的迭代器*/@Overridepublic Iterator<E> iterator() {return new ArrayListIterator();}// ========== 私有輔助方法 ==========/*** 確保列表有足夠的容量容納新元素*/private void ensureCapacity() {if (size == capacity) {resize();}}/*** 擴容列表存儲容量*/private void resize() {int newCapacity = capacity * 2;Object[] newElements = new Object[newCapacity];System.arraycopy(elements, 0, newElements, 0, size);elements = newElements;capacity = newCapacity;}/*** 檢查索引是否在有效范圍內*/private void rangeCheck(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}}/*** 檢查添加操作的索引是否在有效范圍內*/private void rangeCheckForAdd(int index) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}}/*** 構造索引越界異常信息*/private String outOfBoundsMsg(int index) {return "Index: " + index + ", Size: " + size;}/*** 獲取指定位置的元素（帶類型轉換）*/@SuppressWarnings("unchecked")private E elementData(int index) {return (E) elements[index];}// ========== 內部迭代器實現 ==========/*** 列表迭代器實現*/private class ArrayListIterator implements Iterator<E> {/*** 當前迭代位置*/private int cursor;/*** 檢查是否還有更多元素可迭代** @return 如果迭代有更多元素則返回true*/@Overridepublic boolean hasNext() {return cursor != size;}/*** 返回迭代中的下一個元素** @return 迭代中的下一個元素* @throws NoSuchElementException 如果迭代沒有更多元素*/@Overridepublic E next() {if (cursor >= size) {throw new NoSuchElementException();}return elementData(cursor++);}}
}