資料結構與算法(一): 動态數組（下）

四、動态數組的實作

1、添加元素

我們知道, 每當數組添加新元素時, 都會在數組最後一個元素的後面添加新元素
這個 新元素需要添加到的索引 等于 目前數組元素的個數 , 在 ArrayList 中 size 屬性就是 目前數組元素的個數 , 是以就是将新元素添加到數組的 size 位置上, 然後 size 加 1

public void add(E element) {
    elements[size] = element;
    size++;
}
複制代碼

2、數組擴容

由于數組 elements 最大的容量隻有 10 , 是以當數組存滿元素時, 就需要對數組進行擴容
因為數組是無法動态擴容的, 是以需要建立一個新的數組,這個數組的容量要比之前數組的容量大
然後在将原數組中的元素存放到新數組中, 這樣就實作了數組的擴容

private void ensureCapacity() {
    // 擷取數組目前容量
    int oldCapacity = elements.length;
    // 如果 目前存儲的元素個數 < 目前數組容量, 直接傳回
    if (size < oldCapacity) return;
    // 新數組的容量為原數組容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 建立新數組
    E[] newElements = (E[]) new Object[newCapacity];
    // 原數組中的元素存儲到新數組中
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // 引用新數組
    elements = newElements;
}
複制代碼

此時, add 方法的實作如下, 在添加新元素之前, 先判斷是否需要擴容

public void add(E element) {
    // 添加新元素之前, 先判斷是否需要擴容
    ensureCapacity();
    elements[size] = element;
    size++;
}
複制代碼

3、删除元素

删除元素, 實際上就是去掉 指定位置的元素 , 并将後面的元素 向前移動
如下圖, 當删除索引為 3 的元素時, 隻需要将後面的元素向前移動, 然後在去掉最後一個元素, size 減 1 即可

public E remove(int index) {
    // 取出需要删除的元素
    E element = elements[index];
    // 通過循環, 将index後面的所有元素向前移動一位
    for (int i = index; i < size - 1; i++) {
        elements[i] = elements[i + 1];
    }
    // 删除最後一個元素
    elements[--size] = null;
    // 将删除的元素傳回
    return element;
}
複制代碼

注意: 删除元素時傳入的索引不能越界, 即 不能小于0, 也不能大于等于size
是以我們在删除元素之前需要先進行索引檢查

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
}
複制代碼

remove 方法實作如下

public E remove(int index) {
    // 判斷索引是否越界
    rangeCheck(index);
    // 取出需要删除的元素
    E element = elements[index];
    // 通過循環, 将index後面的所有元素向前移動一位
    for (int i = index; i < size - 1; i++) {
        elements[i] = elements[i + 1];
    }
    // 删除最後一個元素
    elements[--size] = null;
    // 将删除的元素傳回
    return element;
}
複制代碼

4、數組縮容

當數組中的元素删除後, 數組剩餘的空間可能會很大, 這樣就會造成記憶體的浪費
是以當數組中元素删除後, 我們需要對數組進行縮容
實作方法類似于擴容, 當數組中容量小于某個值時, 建立新的數組, 然後将原有數組中的元素存入新數組即可

public void trim() {
    // 擷取目前數組的容量
    int capacity = elements.length;
    // 當size大于等于容量的一半, 或則容量已經小于預設容量(10)時, 直接傳回
    if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // 計算新的容量 = 原有容量的一半
    int newCapacity = capacity >> 1;
    // 建立新數組
    E[] newElements = (E[]) new Object[newCapacity];
    // 将原數組元素存入新數組
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // 引用新數組
    elements = newElements;
}
複制代碼

每次删除元素後, 判斷是否需要縮容

public E remove(int index) {
    // 判斷索引是否越界
    rangeCheck(index);
    // 取出需要删除的元素
    E element = elements[index];
    // 通過循環, 将index後面的所有元素向前移動一位
    for (int i = index; i < size - 1; i++) {
        elements[i] = elements[i + 1];
    }
    // 删除最後一個元素
    elements[--size] = null;
    // 判斷數組是否需要縮容
    trim();
    // 将删除的元素傳回
    return element;
}
複制代碼

5、清空元素

清空元素, 隻需要将所有的元素置為 null , 然後 size 置為

public void clear() {
    // 清空存儲的資料
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // 将size置為0
    size = 0;
}
複制代碼

6、修改元素

修改元素時, 隻需要将原有位置的元素替換掉即可, 隻是需要注意一下索引是否越界

public E set(int index, E element) {
    // 判斷索引是否越界
    rangeCheck(index);
    // 取出被替換元素
    E oldElement = elements[index];
    // 替換元素
    elements[index] = element;
    // 傳回被替換元素
    return oldElement;
}
複制代碼

7、查詢元素

查詢元素, 隻需要将指定索引的元素傳回, 注意索引是否越界即可

public E get(int index) {
    rangeCheck(index);
    return elements[index];
}
複制代碼

8、插入元素

插入元素類似于删除元素, 隻需要将插入位置後面的元素向後移動即可
注意: 需要從後向前移動元素, 如果從前向後移動元素, 那麼會進行元素覆寫, 最後出錯

public void add(int index, E element) {
    // 從後向前的順序, 将元素向後移動
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    // 插入元素
    elements[index] = element;
    // size+1
    size++;
}
複制代碼

需要注意的是, 插入元素的索引也不能越界, 不過不同于删除和設定元素時, 插入的位置可以是所有元素的最後, 即size的位置

public void rangeCheckForAdd(int index) {
    // 當索引小于0 或 大于 size時 抛出異常
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
}
複制代碼

add 方法如下

public void add(int index, E element) {
    // 檢查索引是否越界
    rangeCheckForAdd(index);
    // 從後向前的順序, 将元素向後移動
    for (int i = size - 1; i >= index; i--) {
        elements[i + 1] = elements[i];
    }
    // 插入元素
    elements[index] = element;
    // size+1
    size++;
}
複制代碼

9、檢視元素位置

可以通過循環, 查找元素在數組中的位置
注意: 數組中可以存儲 null , 而 null 是不能調用 equals 方法的, 是以需要對傳入的元素進行判斷, 如果查找的元素是 null , 需要單獨處理
當元素存在時傳回索引, 否則傳回變量 ELEMENT_ON_FOUND 的值

private static final int ELEMENT_ON_FOUND = -1;
public int indexOf(E element) {
    if (element == null) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i;
        }
    }else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i;
        }
    }
    return ELEMENT_ON_FOUND;
}
複制代碼

10、是否包含某個元素

當元素存在時, 隻需要判斷索引是否等于 ELEMENT_ON_FOUND

public boolean contains(E element) {
    // 檢視元素的索引是否為ELEMENT_ON_FOUND即可
    return indexOf(element) != ELEMENT_ON_FOUND;
}
複制代碼

11、元素的數量

數組元素的數量, 就是size的值

public int size() {
    return size;
}
複制代碼

12、數組是否為空

判斷 size 的值是否為

public boolean isEmpty() {
    return size == 0;
}
複制代碼

13、動态數組列印

可以重寫 toString 方法, 來列印 ArrayList 中的元素

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size = ").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(",");
        }
        string.append(elements[i]);
    }
    string.append("]");
    return string.toString();
}

資料結構與算法(一): 動态數組（下）

四、動态數組的實作

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希