几个关键点
下面我会直接给出一个简单的动态数组代码实现，包含了基本的增删查改功能。这里先给出几个关键点，等会你看代码的时候可以着重注意一下。
关键点一、自动扩缩容
在上一章 数组基础 中只提到了数组添加元素时可能需要扩容，并没有提到缩容。
在实际使用动态数组时，缩容也是重要的优化手段。比方说一个动态数组开辟了能够存储 1000 个元素的连续内存空间，但是实际只存了 10 个元素，那就有 990 个空间是空闲的。为了避免资源浪费，我们其实可以适当缩小存储空间，这就是缩容。
我们这里就实现一个简单的扩缩容的策略：
当数组元素个数达到底层静态数组的容量上限时，扩容为原来的 2 倍；
当数组元素个数缩减到底层静态数组的容量的 1/4 时，缩容为原来的 1/2。
关键点二、索引越界的检查
下面的代码实现中，有两个检查越界的方法，分别是 checkElementIndex 和 checkPositionIndex，你可以看到它俩的区别仅仅在于 index < size 和 index <= size。
为什么 checkPositionIndex 可以允许 index == size 呢，因为这个 checkPositionIndex 是专门用来处理在数组中插入元素的情况。
比方说有这样一个 nums 数组，对于每个元素来说，合法的索引一定是 index < size：
但如果要在数组中插入新元素，那么新元素可能插入位置并不是元素的索引，而是索引之间的空隙：
这些空隙都是合法的插入位置，所以说 index == size 也是合法的。这就是 checkPositionIndex 和 checkElementIndex 的区别。
关键点三、删除元素谨防内存泄漏
单从算法的角度，其实并不需要关心被删掉的元素应该如何处理，但是具体到代码实现，我们需要注意可能出现的内存泄漏。
在我给出的代码实现中，删除元素时，我都会把被删除的元素置为 null，以 Java 为例：
Java 的垃圾回收机制是基于 图算法 的可达性分析，如果一个对象再也无法被访问到，那么这个对象占用的内存才会被释放；否则，垃圾回收器会认为这个对象还在使用中，就不会释放这个对象占用的内存。
如果你不执行 data[size - 1] = null 这行代码，那么 data[size - 1] 这个引用就会一直存在，你可以通过 data[size - 1] 访问这个对象，所以这个对象被认为是可达的，它的内存就一直不会被释放，进而造成内存泄漏。
其他带垃圾回收功能的语言应该也是类似的，你可以具体了解一下你使用的编程语言的垃圾回收机制，这是写出无 bug 代码的基本要求。
其他细节优化
下面的代码当然不会是一个很完善的实现，会有不少可以进一步优化的点。比方说，我是用 for 循环复制数组数据的，实际上这种方式复制的效率比较差，大部分编程语言会提供更高效的数组复制方法，比如 Java 的 System.arraycopy。
不过它再怎么优化，本质上也是要搬移数据，时间复杂度都是 O(n)。本文的重点在于让你理解数组增删查改 API 的基本实现思路以及时间复杂度，如果对这些细节感兴趣，可以找到编程语言标准库的源码深入研究。
动态数组代码实现
Java
运行代码
复制代码
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
import java.util.Arrays;
// 检查索引越界
checkElementIndex(index);
// 修改数据
E oldVal = data[index];
data[index] = element;
return oldVal;
}
// 工具方法
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// 将 data 的容量改为 newCap
private void resize(int newCap) {
E[] temp = (E[]) new Object[newCap];
for (int i = 0; i < size; i++) {
temp[i] = data[i];
}
data = temp;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
// 检查 index 索引位置是否可以存在元素
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 检查 index 索引位置是否可以添加元素
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void display() {
System.out.println("size = " + size + " cap = " + data.length);
System.out.println(Arrays.toString(data));
}
public static void main(String[] args) {
// 初始容量设置为 3
MyArrayList<Integer> arr = new MyArrayList<>(3);
// 添加 5 个元素
for (int i = 1; i <= 5; i++) {
arr.addLast(i);
}
arr.remove(3);
arr.add(1, 9);
arr.addFirst(100);
int val = arr.removeLast();
for (int i = 0; i < arr.size(); i++) {
System.out.println(arr.get(i));
}
}
}
