使用java語言實現一個動態數組（詳解）（數據結構）
- 2019 年 10 月 21 日
- 筆記
廢話不多說，上程式碼
1.從類名開始（我真是太貼心了，給自己點個贊）
public class Array<E>
首先數組類需要帶有泛型，這個不多說。需要注意的是在java中，數組只能存放同一個類型的。
2.成員變數
private int size; //數組中元素的個數 private E[] data; //數組聲明
插個題外話：
關於size和索引，最開始學數組時讓我很傷神，首先數組的索引是從0開始，而size是指數組中元素的
的個數，假設數組中有3個元素，那麼size=3,而索引則為0,1,2。它們是差一位的，這個神奇的設計讓我每次在寫循環的界限條件時，
總要換算一下。
比如，遍歷出數組的所有元素
for (int i = 0; i < size; i++) { }
我的心路歷程是這樣的:
首先，第一步想，從0開始，到最後一位元素的索引位置結束，那麼最後一位元素的索引是應該進來for循環的，那麼i就應該
小於最後一位元素的索引的下一位，那麼最後一位元素的索引的下一位是誰呢，對哦，size比索引大一位，那麼應該是size，
所以應該i<size;
如果每次寫for循環的界限時，都要這麼想一下，白白消耗腦力阿。是不是只有我這麼笨。
最後我的辦法是轉化成圖來記在腦海里。每次用到的時候，直接腦海里浮現出這個圖。
學習的本質就是將複雜的東西簡單化。
3.構造方法
一種用戶指定初始數組容量
一種用戶不指定初始數組容量
public Array (int capacity) { data = (E[])new Object[capacity]; size = 0; } public Array () { this(10); //調用另一個構造方法，並默認初始容量為10 }
4.居家必備的基本方法
//獲得數組元素個數 public int getSize () { return size; } //獲得數組長度 public int getCapacity () { return data.length; } //獲得數組是否為空 public boolean isEmpty () { return size == 0; }
5.添加方法
數組添加的本質就是：從後往前到指定索引位置，每個元素向後移一個格，給新來的騰出個地方。 重點：從後往前
//向數組指定位置添加元素，index為指定索引位置，e為添加的值 public void add (int index, E e) { //索引位置不能讓它瞎插，索引為負數，或者跳格子插，不可以。 if (index < 0 || index > size) { throw new IllegalArgumentException("add is fail, require index < 0 || index > size"); } //當數組容量滿了的時候，調用擴容方法，此處給它擴當前數組長度的兩倍。 if (data.length == size) { this.resize(data.length * 2); }for (int i = size - 1; i >= index; i--) { data[i+1] = data[i]; } //新來的進坑 data[index] = e; //維護size size ++; }
//向數組第一位添加元素 public void addFirst (E e) { //直接復用上一個add方法 this.add(0, e); } //向數組最後一位添加元素 public void addLast (E e) { //同理 this.add(size, e); }
6.刪除方法（我個人分為兩種，一種根據索引刪除，一種根據值刪除）
刪除的本質：和添加相反，從要刪除的索引位置的下一位開始，到最後一位元素索引位置結束，依次向前佔一個坑。 重點：遍歷的時候從前往後
//根據索引刪除某個元素 返回刪除的元素 public E remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove is fail,require index < 0 || index >= size"); } //先把要刪除的元素存起來，不然等會就給覆蓋了。 E value = data[index]; for (int i = index + 1; i < size; i++) { data[i-1] = data[i]; } //維護size size --; //此處為什麼設置為null呢，因為泛型的原因，傳進來的都是類對象，數組中存的是引用地址，引用不斷開的話，垃圾回收器沒辦法回收。 data[size] = null; //此處縮容，當數組元素個數等於數組長度四分之一時，進行縮容
if (size == data.length/4 && data.length / 2 != 0) { //縮容為數組長度的二分之一 this.resize(data.length /2); } return value; }
問題來了，為什麼不在二分之一時就進行縮容呢？而是四分之一呢？
此處涉及到複雜度震蕩問題，比較極端的一個情況是： 比如容量為10的一個數組， 此時該數組滿了，此時要進來個元素，然後數組進行擴容，那麼添加完元素此時數組的情況為容量為20， 內部有11個元素。 此時我再對數組進行刪除一個元素，刪除之後，數組元素個數變為10個，恰好為數組長度的二分之一， 那麼自動進行縮容，以此類推，反覆操作，每次擴容縮容的時間複雜度為O(n)，所以此處應用了lazy的解決方案 就是等到數組元素個數為數組長度的四分之一時，再進行縮容，就可以避免這個問題。
//根據值刪除某個元素 public void removeByValue (E e) { //復用根據值查找元素的方法，返回索引（此方法在下面） int index = this.getByElement(e); if (index != -1) { //復用根據索引刪除的方法 this.remove(index); } } //刪除第一個元素 public E removeFirst () { return this.remove(0); } //刪除最後一個元素 public E removeLast () { return this.remove(size - 1); }
7.查找方法（同樣分為兩種，一種根據索引，一種根據值）
//根據索引查找數組某個元素,返回值 public E getByIndex (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get is fail, require index < 0 || index >= size"); } return data[index]; }
//根據值查找數組某個元素,返回索引 public int getByElement (E e) { //本質：遍曆數組進行比對 for (int i = 0; i < size; i++) { if (data[i].equals(e) ) { return i; } } return -1; }
//是否包含該元素 public boolean contains (E e) { //本質：遍曆數組進行比對 for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return true; } } return false; }
8.修改方法
//修改數組某個元素 public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("set is fail, require index < 0 || index >= size"); } data[index] = e; }
9.擴容方法
擴容的本質：就是開闢個新數組，把舊數組的內容複製過去
private void resize (int newCatacity) { E[] newData = (E[])new Object[newCatacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } //給成員變數data重新賦值新引用（後面有記憶體圖介紹） data = newData; }
畫個擴容引用轉換的記憶體圖
測試程式碼
public static void main(String[] args) { Array<Integer> array = new Array(5); array.addLast(1); array.addLast(2); array.addLast(3); array.addLast(4); array.addLast(5); }
10.toString方法
本質就是：創建一個StringBuilder對象，然後通過append方法，將數組的內容遍歷，添加進StringBuilder對象。
@Override public String toString () { StringBuilder stringBuilder = new StringBuilder(); //Format(String, Object, Object) 將指定的 String 中的格式項替換為兩個指定的 Object 實例的值的文本等效項。 stringBuilder.append(String.format("size =%d ,capacity =%dn ", size, data.length)); stringBuilder.append('['); for (int i = 0; i < size; i++) { stringBuilder.append(data[i]); if (i != size -1) { stringBuilder.append(','); } } stringBuilder.append(']'); return stringBuilder.toString(); }
最後，
浮於表面看千遍，
不如自己思一遍，
希望這篇文章能夠對你起到幫助。
