数据结构之动态数组

数据结构之动态数组

实现动态数组的关键方法是 resize方法

1
2
3
4
5
6
7
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}

核心思想是当数组满了或者过长导致浪费的时候新建一个合适的数组,把原来数组中的元素复制到新的数组中。
关于

关于addLast的时间复杂度分析

从上面的代码看可能认为addLast它的时间复杂度是O(n),
但是普通的时间复杂度计算方法对于这个addLast操作不太合适。
因为这个操作不是每一次都会触发。
应该使用均摊复杂度计算。
假设这个数组长度为n,现在每次插入都从末尾插入,当执行n+1次操作的时候才会触发一次resize操作。
尾部插入操作涉及1次基本操作,一次resize是n次基本操作。平均下来每次涉及(n+n+1)/n 约等于2 次基本操作。
所以addLast其时间复杂度用均摊时间复杂度计算为O(1)更为合适。同理removeLast也一样。

复杂度震荡的情况

当addLast和removeLast放在一起的时候,可能会出现复杂度震荡的情况。比如现在capacity=10,当addLast执行10次后,再次执行第11次时,resize方法会执行。此时如果执行一个remove操作,数组的长度变为原本代码的一半,如果此时立即缩短数组触发resize操作就会出现复杂度震荡的情况。为了避免出现这种情况,应该使用Lazy的方式。remove的代码如下

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
/**
* 删除指定索引的元素 返回该索引的值
* 如果数组中的元素的个数小于数组长度的四分之一就缩短数组长度为原来的二分之一
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
// loitering objects != memory leak 这里置空后垃圾回收机制会自动回收 否则不会回收 但也不属于内存泄露
data[size] = null;

//这里之所以用四分之一是为了做了lazy的处理 避免数组出现复杂度震荡的情况 如果除以2则
// removeLast 时 resize 过于着急(Eager) 可能会出现震荡

if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}

完整版代码如下

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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
package ArrayTrain;

/**
* @ Description: 实现自己的动态数组
* @ Date: Created in 14:37 11/07/2018
* @ Author: Anthony_Duan
*/
public class Array<E> {

private E[] data;

/**
* size指向的是数组中最后一个元素的下一个空的存储单元
*/
private int size;

/**
* 构造函数,传入数组的容量capacity构造Array
*
* @param capacity
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}

/**
* 无参构造方法 默认数组长度为10
*/
public Array() {
this(10);
}

/**
* 获得数组的容量
*
* @return
*/
public int getCapacity() {
return data.length;
}

/**
* 获得数组中元素的个数
*
* @return
*/
public int getSize() {
return size;
}

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

/**
* 在index索引的位置插入一个新元素e
* 如果数组已经满了就扩充数组,新扩充的数组的长度是原来的2倍
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (size == data.length) {
resize(2 * data.length);
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;

}

/**
* 向数组末尾追加元素e
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}

/**
* 向数组的头部添加元素e
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}

/**
* 获得指定索引的元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
} else {
return data[index];
}

}

/**
* 修改指定索引元素的值为e
*
* @param index
* @param e
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
} else {
data[index] = e;
}
}

/**
* 判断数组中是否包含元素e
*
* @param e
* @return
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}

/**
* 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
*
* @param e
* @return
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}

/**
* 删除指定索引的元素 返回该索引的值
* 如果数组中的元素的个数小于数组长度的四分之一就缩短数组长度为原来的二分之一
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
// loitering objects != memory leak 这里置空后垃圾回收机制会自动回收 否则不会回收 但也不属于内存泄露
data[size] = null;

//这里之所以用四分之一是为了做了lazy的处理 避免数组出现复杂度震荡的情况 如果除以2则
// removeLast 时 resize 过于着急(Eager) 可能会出现震荡

if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}

/**
* 从数组中删除元素e 在数组存在多个e时只能删除第一个
*
* @param e
*/
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}

/**
* 从数组中删除第一个元素, 返回删除的元素
*
* @return
*/
public E removeFirst() {
return remove(0);
}

/**
* 从数组中删除最后一个元素, 返回删除的元素
*
* @return
*/
public E removeLast() {
return remove(size - 1);
}

/**
* 将数组空间的容量变成newCapacity大小
*
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}


@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Arry: size = %d , capacity = %d\n", size, data.length));
res.append("[");
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append("]");
return res.toString();
}
}
-------------End Of This ArticleThank You For Reading-------------