数据结构 - 动态数组

数组在内存中是连续保存的，容量也是在一开始就确定的，很多编程语言中，数组都有个缺点就是不可以动态的修改容量。或者底层已经封装好了一套动态数组的数据结构。
自己实现动态数组：代码如下

const DEFAULT_CAPATICY = 10;
const ELEMENT_NOT_FOUND = -1;

class ArrayList {
    // 传入数组的容量
    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;
    }

    // 判断是否包含一个元素 平均复杂度：O(n)
    contains(ele) {
        return this.indexof(ele) !== ELEMENT_NOT_FOUND;
    }

    // 添加元素 平均复杂度：O(n)
    add(ele, index) {
        this.expandCapacity(this.size + 1);
        // 给index添加元素
        if (typeof index === 'number') {
            this.rangeCheck(index, true);
            // 添加元素后所有的数组都需要往后移动
            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;
        }
    }

    // 获取固定下标的元素 平均复杂度：O(1)
    get(index) {
        this.rangeCheck(index);
        return this.elements[index];
    }

    // 设置固定下标的元素 平均复杂度：O(1)
    set(index, ele) {
        this.rangeCheck(index);
        this.elements[index] = ele;
    }

    // 删除固定下标的元素 平均复杂度：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;
    }

    // 获取元素的下标 平均复杂度：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');
        }
    }
    // 缩容 -- 如果已使用的容量远小于数组的容量,需要缩容
    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}`);
    }

    // 扩容 -- 如果已使用的容量已经大于等于容量需要扩容
    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} -->扩容为--> ${newCapaticy}`);
    }

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

动态数组的优点和缺点
优点：

1. 查询和更新元素效率高，直接通过索引查找
2. 开辟、销毁内存空间次数相对较少
   缺点：
3. 删除和添加（非尾部） 元素时需要移位，而且需要动态扩容和缩容，效率较低
4. 开辟空间后可能会造成空间浪费，不是开多少用多少。