純數據結構Java實現(1/11)(動態數組)
- 2019 年 10 月 3 日
- 筆記
我怕說這部分內容太簡單後，突然蹦出來一個大佬把我虐到哭，還是悠著點，踏實寫
大致內容有: 增刪改查，泛型支援，擴容支援，複雜度分析。(鋪墊: Java語言中的數組)
基礎鋪墊
其實沒啥好介紹的，順序存儲，(非受限的)線性結構。查詢O(1)，因為支援隨機存取。
Java中的數組
Java 中的數組操作，大致如下:
int[] arr = new int[10] String[] strArr = new String[9] // 定義的時候就有初始值 --- 自動感知數組長度 int[] scores = new int[]{100, 99, 88} //獲取數組的長度 arr.length //for each 循環 (數組是可迭代對象) for(int s in arr){ System.out.println(s) }但不同於 Python 這類動態腳本語言，Java中的數組只能存儲相同類型的元素。
- Java比較奇葩，
長度一會兒是 length, 一會兒是 length()，一會兒是 size() - 可以大致按照數組-屬性，字元串-方法，其他容器-size() 來記憶
自己實現
先別管動態擴容的部分，現在就看數組這個容器，如何實現增刪改查
大體思路
其實就是內部封裝一個 int[] 數組，為了方便，順便需要一個長度屬性。
package array; public class MyArray { //先聲明一下相應的變數, 不暴露給外部 (內部維護保持兩者一致) private int[] data; //capacity 就是 data 的 length private int size; // 構造函數，傳入數組容量 public MyArray(int capacity) { data = new int[capacity]; size = 0; //初始情況下，實際有 0 個元素 } //提供一個默認的吧, 不需要用戶手動提供 capacity, 無參 public MyArray() { this(10); } //獲取數組元素個數 public int getSize() { return size; } //返回動態數組的容量 public int getCapacity() { return data.length; } //數組此刻是否為空 public boolean isEmpty() { return size == 0; } }- capacity 容量，數組實際裝了多少，用 size 表示
- capacity 可以用內部數組的長度表示，及 data.length
上面就是整體的框架。(還沒有涉及動態擴容)
增刪改查
因為趕時間，所以增刪改查一起來。
添加元素
此時 size 應該指向的是，要添加元素的下一個位置。即尾部添加時 size++ 。
簡單想: 一開始沒有元素，size 在 0 位置，即第一個元素的位置。
尾部添加:
public void append(int elem) { //TODO: 考慮一下是否超過容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } this.data[size++] = elem; } //如果實現了 insert(key, elem) 方法，可以直接寫成 //末尾添加 public void append(int elem) { insert(size, elem); }指定位置添加:
//指定位置插入 public void insert(int index, int elem) { //TODO: 考慮一下是否超過容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } //檢查 index 是合法的 if(index < 0 || index > size){ throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size "); } //先移動元素，從後面開始 (size-1 移動到 size --> index 移動到 index+1；騰出 index) for(int i = size-1; i>=index; i--){ data[i+1] = data[i]; } data[index] = elem; //覆蓋原來的 index 處的內容 size++; }注意一下，要維護 size 。
頭部添加:
此時就可以復用 insert 方法了:
//頭部添加 public void presert(int elem){ insert(0, elem); }遍曆元素
其實就是遍歷內部封裝的數組，找到相應的元素。
獲取整體: （覆寫 toString 這個方法）
//獲取數組整體，即列印時需要顯示的資訊 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("MyArray: size=%d, capacity=%dn", size, data.length)); res.append("["); //只遍歷現有元素，而不是容量 for (int i = 0; i < size; i++) { res.append(data[i]); if(i != size-1){ res.append(", "); } } res.append("]"); return res.toString(); }測試看看:
import array.MyArray; public class Main { public static void main(String[] args) { MyArray arr = new MyArray(20); //容量20 //放入 10 個元素 for(int i=0; i< 10; i++){ arr.append(i); } System.out.println(arr); arr.insert(1, 100); System.out.println(arr); } } //輸入結果如下: MyArray: size=10, capacity=20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]取出具體元素 (getter)
按照索引取。
//獲取某個具體元素: 通過封裝，加入自定義 index 檢查(保證獲取數據安全) public int get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } return data[index]; }修改元素 (setter)
按照索引修改。
//更新元素 public void set(int index, int elem) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } data[index] = elem; }是否包含
線性遍歷一遍，看看是否存在
//是否包含 public boolean contains(int elem) { for (int i = 0; i < size; i++) { if (data[i] == elem) { return true; } } return false; }搜索元素
還是線性搜索一下，找到就返回下標
public int find(int elem){ for(int i=0; i<size; i++){ if(data[i] == elem){ return i; } } return -1; //沒有找到返回 -1 }刪除元素
刪除就是覆蓋，大致分為兩類: 按照索引刪除，按照元素刪除。
從 index 開始到 size-1，不斷往前賦值，最後維護一下整體的 size-—。
(size的元素用戶是拿不到的，所以data[size]值不必擔心)
//刪除元素 (通常要返回相應的元素) public int remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存儲起來 int ret = data[index]; //覆蓋刪除: 把 index+1 的值移動到 index --> 把 size-1 的值移動到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因為用戶取不到 data[size] return ret; }當然也可以補充一些快捷方法:
//快捷刪除尾部元素 public int pop(){ return remove(size-1); } //快捷刪除頭部元素 public int popLeft(){ return remove(0); }按照元素刪除: 先查找，然後刪除
//刪除指定元素 (不必返回，因為用戶已經知道 elem) public void removeElem(int elem){ int index = find(elem); if(-1 == index) { throw new IllegalArgumentException("Remove failed, cannot find this elem"); } //成功了什麼都不提示，出錯才提示 remove(index); }- 默認都是查找，刪除第一個找到的元素
簡單測試一下，刪除:
//[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //刪除試試 arr.remove(1); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //刪除末尾試試 arr.pop(); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8] //刪除頭部試試 arr.popLeft(); System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8] //刪除 4 這個數字 arr.removeElem(4); System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8]泛型支援
語法限制
由於泛型的限制(不能放入基本類型，只能放入其包裝類)，內部封裝的數組初始化的時候需要強制類型轉換一下。
也就是說，可以用於聲明，但不能用於定義。
data = new E[capacity]; //報錯，歷史遺留問題，不支援該語法 //正確的寫法 (藉助強制類型轉換) data = (E[])new Object[capacity];完整程式碼
特別注意一下:
- 對象值的比較，需要改成
equals - 刪除的時候，因為存儲的是對象的引用，所以應該把移動後的
data[size]位置設置為NULL- 但是這一條是非必須，因為
閑逛對象 != memory leak
- 但是這一條是非必須，因為
還是貼一下，支援泛型的完整程式碼吧:
package array; public class AdvanceArray<E> { //先聲明一下相應的變數, 不暴露給外部 (內部維護保持兩者一致) private E[] data; //capacity 就是 data 的 length private int size; // 構造函數，傳入數組容量 public AdvanceArray(int capacity) { data = (E[])new Object[capacity]; size = 0; //初始情況下，實際有 0 個元素 } //提供一個默認的吧, 不需要用戶手動提供 capacity, 無參 public AdvanceArray() { this(10); } //獲取數組元素個數 public int getSize() { return size; } //返回動態數組的容量 public int getCapacity() { return data.length; } //數組此刻是否為空 public boolean isEmpty() { return size == 0; } //末尾添加 public void append(E elem) { insert(size, elem); } //頭部添加 public void presert(E elem) { insert(0, elem); } //指定位置插入 public void insert(int index, E elem) { //TODO: 考慮一下是否超過容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } //檢查 index 是合法的 if (index < 0 || index > size) { throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size "); } //先移動元素，從後面開始 (size-1 移動到 size --> index 移動到 index+1；騰出 index) for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = elem; //覆蓋原來的 index 處的內容 size++; } //獲取數組整體，即列印時需要顯示的資訊 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("MyArray: size=%d, capacity=%dn", size, data.length)); res.append("["); //只遍歷現有元素，而不是容量 for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(", "); } } res.append("]"); return res.toString(); } //獲取某個具體元素: 通過封裝，加入自定義 index 檢查(保證獲取數據安全) public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } return data[index]; } //更新元素 public void set(int index, E elem) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } data[index] = elem; } //是否包含 public boolean contains(E elem) { for (int i = 0; i < size; i++) { if (data[i].equals(elem)) { return true; } } return false; } //搜索元素 public int find(E elem) { for (int i = 0; i < size; i++) { if (data[i].equals(elem)) { return i; } } return -1; //沒有找到返回 -1 } //刪除元素 (通常要返回相應的元素) public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存儲起來 E ret = data[index]; //覆蓋刪除: 把 index+1 的值移動到 index --> 把 size-1 的值移動到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因為用戶取不到 data[size] //當使用泛型，對對象元素支援時 data[size] = null; //方便 java 回收 loitering objects (非必須，閑逛對象 != memory leak) return ret; } //快捷刪除尾部元素 public E pop() { return remove(size - 1); } //快捷刪除頭部元素 public E popLeft() { return remove(0); } //刪除指定元素 (不必返回，因為用戶已經知道 elem) public void removeElem(E elem) { int index = find(elem); if (-1 == index) { throw new IllegalArgumentException("Remove failed, cannot find this elem"); } //成功了什麼都不提示，出錯才提示 remove(index); } }測試程式碼如下:
//這個類主要用於 AdvanceArray 做泛型測試 public class Student { private String name; private int score; public Student(String studentName, int studentScore){ name = studentName; score = studentScore; } @Override public String toString() { return String.format("Student(name: %s, score: %d)", name, score); } } // main.java 中: public class Main { private static void test_2(){ //泛型不支援基本類型，所以這裡寫 Integer；使用時會自動box，unbox AdvanceArray<Integer> arr = new AdvanceArray<>(20); //容量20 //放入 10 個元素 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //插入試試 arr.insert(1, 100); System.out.println(arr); //[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //刪除試試 arr.remove(1); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //刪除末尾試試 arr.pop(); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8] //刪除頭部試試 arr.popLeft(); System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8] //刪除 4 這個數字 arr.removeElem(4); System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8] } private static void test_3(){ AdvanceArray<Student> arr = new AdvanceArray<>(); //默認容量是 10 //添加測試數據 arr.append(new Student("AAA", 100)); arr.append(new Student("BBB", 90)); arr.append(new Student("CCC", 60)); System.out.println(arr); } } // 測試結果 MyArray: size=3, capacity=10 [Student(name: AAA, score: 100), Student(name: BBB, score: 90), Student(name: CCC, score: 60)]動態支援
上面其實沒有支援動態擴容，也就不能稱為一個
動態數組
上面的做法是，一旦檢測到索引異常，基本都拋異常結束流程了；正常索引就插入，但沒有考慮插入之後超過容量了怎麼辦？（在容量滿的時候就應該檢測到了）
解決方案，最基本的就是:
- 1.開闢新空間
- 2.把元素複製過去
但這只是擴容支援，如果元素縮減到一定程度，那麼也應該減少容量。
增加擴容
//主要就是修改 insert 函數 public void insert(int index, E elem) { //檢查 index 是合法的 if (index < 0 || index > size) { throw new IllegalArgumentException("insert failed, need: index >=0 and index <= size "); } //滿了，那麼就擴容吧 -- 這裡不再是拋異常對象了 if (size == data.length) { resize(2 * data.length); //java arraylist 選擇的是 1.5 倍 } //先移動元素，從後面開始 (size-1 移動到 size --> index 移動到 index+1；騰出 index) for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = elem; //覆蓋原來的 index 處的內容 size++; } private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; //複製舊元素過去 for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; }簡單測試一下:
//初始容量為 10，先初始化 10 個元素 AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默認為 10 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //再添加一個元素，試試 arr.append(100); System.out.println(arr); //輸出結果: MyArray: size=10, capacity=10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100]刪除縮減
刪除元素的之後，如果空間小到一定程度，自動縮減空間
- 只要就是在刪除後，做一下 size 和 capacity 的判斷，然後 resize
(即刪除後，size 為 capacity 的一半就可以縮容了)
//初始容量為 10，先初始化 10 個元素 AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默認為 10 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //再添加一個元素，試試 -- 此時容量變為 20，實際佔用 11 arr.presert(100); System.out.println(arr); //pop一個，容量立馬縮減為 10 arr.pop(); System.out.println(arr); //運行結果為: MyArray: size=10, capacity=10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=10, capacity=10 [100, 0, 1, 2, 3, 4, 5, 6, 7, 8]最後，擴容或者刪除容量，對於 client 而言，它並不知道。(擴容策略也可以在細緻些)
複雜度分析
O(1) -> O(logn)優良 —> O(n) 一般 —> O(nlogn) 一般般,其實和O(n)差不太多 —> O(n^2) 差 —>O(C^n) 超差
一般談起來，會說和運行規模成: 常數關係，對數關係，線性關係，nlogn，平方關係，指數關係。簡單理解就是，級大一級壓死人。
詳細分析
添加操作:
-
末尾插入 append: O(1)
-
頭添加 presert: O(n)
-
任意位置插入 insert(index): 在 O(1) 和 O(n) 之間，假設 index 的取值概率一樣，index 靠前的時候越慢，越靠後越快，整體需要靠具體需要移動多少個元素，n + (n-1) + … + 0，n 種情況，平均需要移動的元素 n/2，所以複雜度是 O(n/2)，即 O(n)
resize 的操作也是 O(n)。
(尾部操作也可能是 O(n)，但幾率比較小，不可能每次都觸發 resize)
綜上所述，以最差來考慮，即 O(n)。 (一般考慮的是概率最高的情況)
刪除操作: (其實分析方法類似，核心因素還是元素的移動)
- 末尾刪除 pop(): O(1)
- 頭刪除 popLeft(): O(n) 因為元素要往前面移動
- 任意位置，平均 remove(index): O(n/2)，即 O(n)
resize 的操作也是 O(n)。
(頭部操作也可能是 O(n)，但幾率比較小，不可能每次都觸發 resize)
綜上所述，以最差來考慮，即 O(n)。
修改操作: 因為可以支援隨機訪問(按地址，索引)，所以複雜度 O(1)
查找操作:
- get(index): O(1)
- contains(e): O(n) 線性遍歷
- find(e): O(n) 線性遍歷
從上面也可以看出，時間複雜度和順序存儲情況一致。
均攤複雜度
也就是仔細考慮一下包含這個 擴容&縮容 耗時操作的 remove/insert 到底應該算作 O(1) 還是 O(n)。
比如 addLast() 本來是 O(1)，加入動態支援後，此時還是 O(1) 么。
顯而易見，容易得證:
假設 capacity = n，那麼進行 n+1 次 addLast，觸發擴容，此時包括移動元素，總共操作 2n+1 次，也就是說平均每次 addLast 觸發 (2n+1)/(n+1) 即 2 次操作，即常量次操作，所以 addLast() 算均攤，也是 O(1)。
震蕩優化
剛添加一個元素，擴容；立馬刪除一個元素，又縮容
連環的 addLast 和 removeLast 導致最近的操作都是 O(n)。(常規而言是O(1)的)
此時就要延遲處理(lazy)縮容，即真實元素為 1/4 capacity時才容量減半。
程式碼如下:
//刪除元素 (通常要返回相應的元素) public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存儲起來 E ret = data[index]; //覆蓋刪除: 把 index+1 的值移動到 index --> 把 size-1 的值移動到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因為用戶取不到 data[size] //當使用泛型，對對象元素支援時 data[size] = null; //方便 java 回收 loitering objects (非必須，閑逛對象 != memory leak) //縮減 (只在一個特定的時機縮減，不能用 < 或者 >，可能會存在多次縮減) //注意一下，延遲縮減，即 1/4 時，才縮減為一半 (還有一半是空的) if(size == data.length/4 && data.length/2 != 0) { resize(data.length/2); //那麼就縮減為一半 } return ret; }上面有個技巧或者程式語言問題， data.length/2 != 0，因為 java 的除法默認是截斷的，即可能出現 capacity 為 0 的情況。比如，當前capacity = 1 即 data.length 為 1，即便 size=0，也不能再縮減了(否則執行縮減， capacity 就為 0了)。
總結
順序存儲的結構，不管是不是線性的，基本都有這些操作特徵，只不過上層介面隱藏了實現細節，比如 順序棧 這類受限的結構，底層就是封裝了動態數組(而非原始數組了)。
實現的時候注意移動操作從哪裡開始，索引合法性判斷以及記得維護 size。
深怕有人需要這些粗鄙的程式碼，我還是把它放在了 gayhub 上，供您參考。
如有不足之處，萬望批評指正，蝦蝦儂。
