使用java語言實現一個動態數組（詳解）（數據結構）

廢話不多說，上代碼

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 =%d\n ", 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();
}

最後，

浮於錶面看千遍，

不如自己思一遍，

希望這篇文章能夠對你起到幫助。