Java实现动态数组
在学习Java时，学到的第一个数据结构就是数组。不过，JDK提供的数组是一个静态的，并不能很方便地进行增删改查等操作。今天我们就通过封装静态数组来实现我们自己的动态数组。
创建一个类，因为不知道调用者会传入什么类型的数据到数组中，所以我们这里使用泛型来表示数组类型，从而能保证复用性。
public class DynamicArray<T> {
private T[] mArray;
/**
* 数组中元素个数
*/
private int mSize;
public DynamicArray(int length) {
//noinspection unchecked
mArray = (T[]) new Object[length];
}
public DynamicArray() {
// 默认数组的长度为10
this(10);
}
}
类中提供了两个构造方法，使用者可以自定义数组的长度，若没有指定的话，数组默认的长度为10。当然，既然我们实现的是动态数组，那么后面我们会对这个长度进行扩容。
接着对外提供一些数组常用的方法，如数组长度、元素个数以及是否为空。
/**
* 获取数组长度
*
* @return
*/
public int length() {
return mArray.length;
}
/**
* 获取数组中元素个数
*
* @return
*/
public int getSize() {
return mSize;
}
/**
* 判断数组中元素是否为空
*
* @return true 是，false 否
*/
public boolean isEmpty() {
return mSize == 0;
}
上面几个方法比较简单，就不再详述了。接下来就是我们的增删改查等操作了。
添加元素。其实就是往数组中插入元素，需要提供插入的位置以及插入的元素。在插入之前需要将插入位置及之后的元素向后移动，如下图：
insert.png
/**
* 在指定位置上添加元素
*
* @param index 添加到数组中的位置
* @param element 需要添加的元素
*/
public void add(int index, T element) {
// step 1 判断添加位置的合法性
// 因为数组的元素添加是连贯性的，所以不可能大于当前数组中元素的个数
if (index < 0 || index > mSize) {
throw new IllegalArgumentException("添加失败，添加位置不能负数以及不能大于当前数组元数个数");
}
// step 2 当数组无空间后，再添加元素时需要进行扩容
if (mSize == mArray.length) {
resize(2 * mArray.length);
}
// step 3 添加元素时，先把数组中从最后一个到index位置的元素向后移动
for (int i = mSize - 1; i >= index; i--) {
mArray[i + 1] = mArray[i];
}
// step 4 最后将index的位置赋值新插入的值
mArray[index] = element;
// step 5 数组元素个数加1
mSize++;
}
注释已经写得非常清楚了。在step 2中，当数组满了之后，需要进行扩容，而扩容的大小一般为初始长度的一倍。下面是扩容的实现：
/**
* 对原数组进行扩容
*
* @param newLength 扩容后的长度
*/
private void resize(int newLength) {
//noinspection unchecked
T[] newArray = (T[]) new Object[newLength];
//将旧数组元素拷贝到扩容后的数组中
for (int i = 0; i < mSize; i++) {
newArray[i] = mArray[i];
}
mArray = newArray;
}
我们还可以对外提供头插入和尾插入。
public void addFirst(T element) {
add(0, element);
}
public void addLast(T element) {
add(mSize, element);
}
删除元素。把元素从数组删除时，要记得把被删除元素之后的元素向前移动。如下图：
delete.png
/**
* 删除指定位置的元素
*
* @param index 被删除元素的索引
* @return 被删除的元素
*/
public T delete(int index) {
// step 1 参数合法性判断
if (index < 0 || index > mSize) {
throw new IllegalArgumentException("删除失败，删除的元素位置不能负数以及不能大于当前数组元数个数");
}
// step 2 根据索引记录被删除的元素并返回
T ret = mArray[index];
// step 3 将index之后的元素到最后一个元素向前移动
for (int i = index + 1; i < mSize; i++) {
mArray[i - 1] = mArray[i];
}
// step 4 数组元素减1
mSize--;
// step 5 将未删除元素的原数组的最后一个置为null
mArray[mSize] = null;
// step 6 添加元素时，若是对数组进行了扩容，为了不浪费内存空间，
// 当删除了一定量的元素后，需要对数组进行缩容
// 缩容缩到什么时候为止了？当mArray.length为1时就没有必要继续缩容了
if (mSize == mArray.length / 4 && mArray.length / 2 != 0) {
resize(mArray.length / 2);
}
return ret;
}
step 5并不是非必要的。因为Java本身的垃圾回收机制，会把没用到的对象进行垃圾回收。至于step 6，为什么当元素个数为数组长度的1/4时才缩容，后面在分析到时间复杂度时候会给出原因。跟添加元素一样，我样也可以对外提供删除头和尾的元素。
public T deleteFirst() {
return delete(0);
}
public T deleteLast() {
return delete(mSize - 1);
}
修改元素。因为数组支持随机访问，所以修改数组元素非常快。
/**
* 修改指定位置的元素
*
* @param index
* @param element
*/
public void update(int index, T element) {
// 参数合法性判断
if (index < 0 || index > mSize) {
throw new IllegalArgumentException("修改失败，修改的元素位置不能负数以及不能大于当前数组元数个数");
}
mArray[index] = element;
}
查找元素
/**
* 获取指定位置的元素
*
* @param index
* @return
*/
public T findElement(int index) {
// 参数合法性判断
if (index < 0 || index > mSize) {
throw new IllegalArgumentException("查找失败，查找的元素位置不能为负数以及不能大于当前数组元数个数");
}
return mArray[index];
}
/**
* 获取指定元素的位置
*
* @param element
* @return -1 表示不存在
*/
public int findIndex(T element) {
for (int i = 0; i < mSize; i++) {
if (mArray[i].equals(element)) {
return i;
}
}
return -1;
}
/**
* 查看数组中是否包含指定元素
*
* @param element
* @return
*/
public boolean contains(T element) {
for (int i = 0; i < mSize; i++) {
if (mArray[i].equals(element)) {
return true;
}
}
return false;
}
根据查找的API,我们还可以对外提供一个删除方法
/**
* 删除指定元素
*
* @param element
*/
public void deleteElement(T element) {
int index = findIndex(element);
if (index != -1) {
delete(index);
}
}
时间复杂度分析
-
添加操作
addLast(e) 不需要移动任何元素，时间复杂度为O(1)； addFirst(e) 需向后移动n个元素，时间复杂度为O(n)； add(index,e) 当index越小时，向后移动的元素越多，反之，则越少。所以平均来说是n/2，去掉常数，也就是时间复杂度为O(n)； -
删除操作
与添加操作一样 deleteLast(e) O(1) deleteFirst(e) O(n) deleteElement(e) O(n) delete(index,e) O(n/2) = O(n) 最坏情况下的时间复杂度为： O(n) -
修改操作
update(index,e) O(1) -
查询操作
findElement(index) O(1) findIndex(e) O(n) contains(e) 0(n) 最坏情况下的时间复杂度为： O(n) -
扩容操作
在添加和删除元素时，会出现一种情况：扩容。根据实现的代码可以看出resize方法的时间复杂度在最坏的情况下为O(n)。但是它并不是每次添加或删除元素就会进行扩容，那么它出现的概率是多少呢？
在代码中，我们数组默认的长度为10，也就是在经过11次addLast操作后会触发resize，总共了进行了21次基本操作。也就是说，每一次addLast操作，约等于2次基本操作（21 / 11 ≈ 2）。以此可以推出：假设长度为n，n+1次addLast会触发resize，进行基本操作的次数为2，这样均摊计算的话，resize的时间复杂度为O(1)。很显然，均摊计算（amortized time complexity）比计算最坏情况有意义。
- 复杂度震荡
当我们调用addLast后，需要resize，此时，addLast的时间复杂度为O(n)，紧接着，我们又调用removeLast，又会触发resize，removeLast的时间复杂度为O(n);不停地这样操作就造成了复杂度的震荡。也就是removeLast时，resize被触发的过于着急。解决这个问题的关键点就在于什么时候缩容。我们可以在当前元素个数为数组长度的1/4时才去缩容，这样能保证缩完容后再马上去调用addLast也不会马上resize。
