动态数组 - 简书

动态数组

数组用一块连续的内存地址来存储相同类型的一组数据。最大的特点是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n) 。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

相比容器，数组的用武之地

Java中的ArrayList无法存储基本数据类型（Autoboxing和Unboxing会有性能损耗）,所以对性能有要求，需要选用数组。
如果数据大小已知，且操作简单，则选用数组。

动态数组类Array

底层采用静态数组存储数据，类中维护两个变量data和size。

private E[] data;   //静态数组存储数据
private int size;   //记录数组中元素的个数，即数组大小

resize(int capacity):

调整容量操作。在插入操作时，如果数组的容量已满，会触发扩容操作；在删除操作后，如果元素数量小于数组容量的四分之一，则触发缩容操作。这里需要注意由于此操作会引发的复杂度震荡，缩容应该避免过于激进。
```
public void resize(int newCapacity) {
    //生成新数组
    E[] newData = (E[])new Object[newCapacity];
    //移动数据
    for(int i = 0; i < size; i ++) {
        newData[i] = data[i];
    }
    System.arrayCopy(data,0,newData,0,size);
    //更新引用
    data = newData;
}
```

add(int index, E e):

在指定的位置index插入指定的元素e

public void add(int index, E e) {
    //索引检查
    if(index < 0 || index >= size) {
        throw new RuntimeException("Index out of bound!");
    }
    
    if(size == getCapacity()) {
        //容量不足，扩容
        resize(2 * getCapacity());
    }
    
    //从后面开始，元素后移
    for(int i = size; i > index; i++) {
        data[i] = data[i-1];
    }
    data[index] = e;
    size ++;
}

remove(int index):

删除指定位置的元素

public E remove(int index) {
    //索引检查
    if(index < 0 || index >= size) {
            throw new RuntimeException("Index out of bound!");
    }
    
    //保存要被删除的数值
    E ret = data[index];
    
    for(int i = index; i < size; i ++) {
        data[i] = data[i+1];
    }
    size --;
    
    if(size < getCapacity()/4 && getCapacity/2 != 0) {
        resize(getCapacity()/2);
    }
    
    return ret;
}

18/06/2019 :created

最后编辑于：2019.06.18 13:06:58