?數組是由一組元素（值或變量）組成的數據結構，每個元素有至少一個索引或鍵來標識。

數組內的元素是連續存儲的，所以數組中元素的地址，可以通過其索引計算出來

空間占用

Java 中數組結構為

• 8 字節 markword

• 4 字節 class 指針（壓縮 class 指針的情況）

• 4 字節 數組大小（決定了數組最大容量是 2^32）

• 數組元素 + 對齊字節（java 中所有對象大小都是 8 字節的整數倍12，不足的要用對齊字節補足）

以下是動態數組的實現：

public class DynamicArray implements Iterable<Integer>{//邏輯大小private int size=0;//容量private int capacity=10;private int[] array;//數組尾部添加元素public void add(int element){add(size,element);}/***添加元素* @param index 向指定索引出添加數據* @param element  添加元素*/private void add(int index, int element) {//插入數據前對數組進行檢查checkAndGrow();if(index>=capacity){throw new RuntimeException("索引越界");}if(index>=0 && index <size){System.arraycopy(array,index,array,index+1,size-index);}array[index]=element;size++;}/*** 檢查數組大小* 若size==capacity則進行擴容*/public void checkAndGrow(){if(size==0){//初始化數組array=new int[capacity];}else if(size==capacity){//進行擴容，規則：當前容量+當前容量/2capacity +=capacity>>1;//創建新的數組int[] newArray=new int[capacity];System.arraycopy(array,0,newArray,0,size);//賦給原數組array=newArray;}}/***刪除元素* @param index 索引位置* @return 被刪除元素*/public int remove(int index){if(index>=capacity){throw new RuntimeException("索引越界");}int removed=array[index];if(index<size-1){System.arraycopy(array,index+1,array,index,size-index-1);}size--;return removed;}/*** 查詢元素* @param index 索引位置, 在 [0..size) 區間內* @return 該索引位置的元素*/public int get(int index){return array[index];}/*** 遍歷方法1* @param consumer 遍歷要執行的操作, 入參: 每個元素*/public void foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {// 提供 array[i]// 返回 voiconsumer.accept(array[i]);}}/*** 遍歷方法2 - 迭代器遍歷*/@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() { // 有沒有下一個元素return i < size;}@Overridepublic Integer next() { // 返回當前元素,并移動到下一個元素return array[i++];}};}/*** 遍歷方法3 - stream 遍歷** @return stream 流*/public IntStream stream(){return IntStream.of(Arrays.copyOfRange(array, 0, size));}
}

插入或刪除性能

頭部位置，時間復雜度是 O(n)

中間位置，時間復雜度是 O(n)

尾部位置，時間復雜度是 O(1)（均攤來說）