數(shù)組在內(nèi)存中是連續(xù)保存的，容量也是在一開始就確定的，很多編程語言中，數(shù)組都有個缺點(diǎn)就是不可以動態(tài)的修改容量?；蛘叩讓右呀?jīng)封裝好了一套動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)。
自己實(shí)現(xiàn)動態(tài)數(shù)組：代碼如下

const DEFAULT_CAPATICY = 10;
const ELEMENT_NOT_FOUND = -1;

class ArrayList {
    // 傳入數(shù)組的容量
    constructor(capaticy = DEFAULT_CAPATICY) {
        this.elements = new Array(capaticy);
        this.size = 0;
    }

    // 清空
    clear() {
        this.elements = new Array(DEFAULT_CAPATICY);
        this.size = 0;
    }

    // 獲取size
    getSize() {
        return this.size;
    }

    // 判斷是否為空
    isEmpty() {
        return this.size === 0;
    }

    // 判斷是否包含一個元素 平均復(fù)雜度：O(n)
    contains(ele) {
        return this.indexof(ele) !== ELEMENT_NOT_FOUND;
    }

    // 添加元素 平均復(fù)雜度：O(n)
    add(ele, index) {
        this.expandCapacity(this.size + 1);
        // 給index添加元素
        if (typeof index === 'number') {
            this.rangeCheck(index, true);
            // 添加元素后所有的數(shù)組都需要往后移動
            for (let i = this.size; i >= index; i--) {
                this.elements[i + 1] = this.elements[i];
                if (i === index) this.elements[i] = ele;
            }
            this.size++
        } else {
            // 給末尾添加元素
            this.elements[this.size++] = ele;
        }
    }

    // 獲取固定下標(biāo)的元素 平均復(fù)雜度：O(1)
    get(index) {
        this.rangeCheck(index);
        return this.elements[index];
    }

    // 設(shè)置固定下標(biāo)的元素 平均復(fù)雜度：O(1)
    set(index, ele) {
        this.rangeCheck(index);
        this.elements[index] = ele;
    }

    // 刪除固定下標(biāo)的元素 平均復(fù)雜度：O(n)
    remove(index) {
        this.rangeCheck(index);

        let old = this.get(index);
        for (let i = index; i < this.size; i++) {
            if (i === this.size - 1) {
                this.elements[i] = null
            } else {
                this.elements[i] = this.elements[i + 1];
            }
        }
        this.size--;
        this.reduceCapacity();
        return old;
    }

    // 獲取元素的下標(biāo) 平均復(fù)雜度：O(n)
    indexof(ele) {
        for (let i = 0; i < this.size; i++) {
            if (this.elements[i] === ele) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    // 檢查是否超出范圍
    rangeCheck(index, isadd) {
        if (isadd) {
            if (index > this.size || index < 0) throw new RangeError('index is out of range');
        } else {
            if (index >= this.size || index < 0) throw new RangeError('index is out of range');
        }
    }
    // 縮容 -- 如果已使用的容量遠(yuǎn)小于數(shù)組的容量,需要縮容
    reduceCapacity() {
        let oldCapaticy = this.elements.length; // 5
        let newCapaticy = oldCapaticy >> 1; // 2

        if (newCapaticy < this.size || oldCapaticy <= DEFAULT_CAPATICY) return false;

        let elements = new Array(newCapaticy);
        for (let i = 0; i < this.size; i++) {
            elements[i] = this.elements[i];
        }
        this.elements = elements;

        console.log(`${oldCapaticy} -->縮容為--> ${newCapaticy}`);
    }

    // 擴(kuò)容 -- 如果已使用的容量已經(jīng)大于等于容量需要擴(kuò)容
    expandCapacity(capaticy) {
        let oldCapaticy = this.elements.length;
        if (capaticy <= oldCapaticy) return false;

        let newCapaticy = oldCapaticy + (oldCapaticy >> 1);
        let elements = new Array(newCapaticy);

        for (let i = 0; i < this.size; i++) {
            elements[i] = this.elements[i];
        }
        this.elements = elements;

        console.log(`${oldCapaticy} -->擴(kuò)容為--> ${newCapaticy}`);
    }

    toString() {
        return `${(this.elements || []).join(',')} --> size = ${this.size}`;
    }
}

動態(tài)數(shù)組的優(yōu)點(diǎn)和缺點(diǎn)
優(yōu)點(diǎn)：

1. 查詢和更新元素效率高，直接通過索引查找
2. 開辟、銷毀內(nèi)存空間次數(shù)相對較少
   缺點(diǎn)：
3. 刪除和添加（非尾部） 元素時需要移位，而且需要動態(tài)擴(kuò)容和縮容，效率較低
4. 開辟空間后可能會造成空間浪費(fèi)，不是開多少用多少。