「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。
参考labuladong 的算法笔记 和 k神的Hello 算法
做好以下几个点就可以了
- 关键点一、自动扩缩容
- 关键点二、索引越界的检查
- 关键点三、删除元素谨防内存泄漏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
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;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyArrayList<E> {
// 真正存储数据的底层数组
private E[] data;
// 记录当前元素个数
private int size;
// 默认初始容量
private static final int INIT_CAP = 1;
public MyArrayList() {
this(INIT_CAP);
}
public MyArrayList(int initCapacity) {
data = (E[]) new Object[initCapacity];
size = 0;
}
// 增
public void addLast(E e) {
int cap = data.length;
// 看 data 数组容量够不够
if (size == cap) {
resize(2 * cap);
}
// 在尾部插入元素
data[size] = e;
size++;
}
public void add(int index, E e) {
// 检查索引越界
checkPositionIndex(index);
int cap = data.length;
// 看 data 数组容量够不够
if (size == cap) {
resize(2 * cap);
}
// 搬移数据 data[index..] -> data[index+1..]
// 给新元素腾出位置
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
// 插入新元素
data[index] = e;
size++;
}
public void addFirst(E e) {
add(0, e);
}
// 删
public E removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
int cap = data.length;
// 可以缩容，节约空间
if (size == cap / 4) {
resize(cap / 2);
}
E deletedVal = data[size - 1];
// 删除最后一个元素
// 必须给最后一个元素置为 null，否则会内存泄漏
data[size - 1] = null;
size--;
return deletedVal;
}
public E remove(int index) {
// 检查索引越界
checkElementIndex(index);
int cap = data.length;
// 可以缩容，节约空间
if (size == cap / 4) {
resize(cap / 2);
}
E deletedVal = data[index];
// 搬移数据 data[index+1..] -> data[index..]
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
data[size - 1] = null;
size--;
return deletedVal;
}
public E removeFirst() {
return remove(0);
}
// 查
public E get(int index) {
// 检查索引越界
checkElementIndex(index);
return data[index];
}
// 改
public E set(int index, E element) {
// 检查索引越界
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));
}
}
}
|
