DS01:动态数组

数组的缺陷

静态数组的缺陷

目前为止所实现的数组类，有一个非常严重的局限性，就是这个数组实际使用的还是一个静态数组，内部容量有限。在实际使用的时候，我们往往无法预估要在这个数组中存入多少个元素。

解决思路

构建动态数组，使得数组的容量能够随着存入的元素进行伸缩。其实现底层仍为静态数组。

即：当元素超过数组当前容量时，对数组进行扩容（重新声明一个更大的数组，并将原数组中的元素迁移过去）。当元素由于删除操作远小于当前容量时，对数组容量进行缩小。

动态数组实现

类内基本信息

类中使用泛型<E>，同时使用静态数组data作为底层容器，并记录数组中元素的个数size。

同时，构建实现一些基本的方法。

public class Array<E> {

    private E[] data;
    private int size;

    // 有参构造函数
    // 传入预先设置的容量
    public Array(int capacity) {
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参构造函数，默认容量为10
    public Array() {
        this(10);
    }

    // 获取数组中元素个数
    public int getSize() {
        return size;
    }

    // 获取Array中数组容量
    public int getCapacity() {
        return data.length;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

实现数组的伸缩

实现数组的伸缩其实就是重新声明一个容量符合要求的数组，并将原数组中的元素拷贝进去，如下：

// 改变数组中容量大小
// 传入新容量
private void resize(int newCapacity) {
    E[] newData = (E[])new Object[newCapacity];
    for (int i=0;i<size;i++) {
        newData[i] = data[i];
    }
    data = newData;
}

向数组中添加元素

1、对输入参数进行判断，不合理抛出异常

2、若原数组已经容纳不下新元素，进行上述resize操作，将新数组容量变为之前的2倍（可以指定为其他倍数）

3、进行添加操作

// 向数组中index位置加入元素e
public void add(int index, E e) {
    if(index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed.");
    }

    if(size == data.length) {
        resize(2 * data.length);
    }

    for (int i=size-1;i>=index;i--) {
        data[i+1] = data[i];
    }
    data[index] = e;
    size++;
}

// 向最后添加一个元素
public void addLast(E e) {
    add(size, e);
}

// 向最前添加一个元素
public void addFirst(E e) {
    add(0, e);
}

删除元素

1、对输入参数进行判断，不合理抛出异常

2、若删除元素后数组容量为含有元素个数的4倍，则使用resize将数组容量改为原来的1/2（与add中倍数不同是为了避免复杂度震荡）

3、进行删除操作

// 删除索引为index的元素
public E remove(int index) {
    if(index<0 || index >= size) {
        throw new IllegalArgumentException("Set failed");
    }
    E res = data[index];
    for (int i=index+1;i<size;i++) {
        data[i-1] = data[i];
    }
    size--;
    data[size] = null;

    if (size == data.length / 4) {
        resize(data.length / 2);
    }

    return res;
}

// 删除第一个元素
public E removeFirst() {
    return remove(0);
}

// 删除最后一个元素
public E removeLast() {
    return remove(size-1);
}

其他操作

其余诸如查找索引等操作就是基本的数组操作了，直接进行实现即可。

复杂度分析

复杂度震荡

在之前提到过，在此进行记录其产生的具体过程：

1、假设现在我们有一个数组，容量是n，并且装满了元素。

2、这时候，我想添加一个元素，显然是需要进行扩容，容量变为2n，耗时O(n)的时间。

3、但是此时，我又删除了一个元素触发了缩容操作，耗时O(n)的时间。

4、当我们每次触发缩容或扩容操作，都会耗费O(n)额复杂度，那么这便是复杂度的震荡

解决方法：即将缩容与扩容触发的阈值设置的不同即可。

Donate