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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
| package com.realchoi.arraylist;
/**
* 手动实现 ArrayList
*
* @author realchoi
*/
public class MyArrayList {
// List 中元素的个数
private int size;
// List 中维护的数组（关键就在这）
private Object[] elementData;
/**
* 无参构造方法，初始化 MyArrayList
*/
public MyArrayList() {
this(10);
}
/**
* 有参构造方法，初始化 MyArrayList，并给定初始容量
*
* @param capacity 初始容量
*/
public MyArrayList(int capacity) {
if (capacity < 0) {
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
elementData = new Object[capacity];
}
/**
* 获取 List 中元素的个数
*
* @return
*/
public int size() {
return size;
}
/**
* 将元素添加到 List 末尾
*
* @param element 待添加的元素
*/
public void add(Object element) {
// 添加时首先需要判断数组容量是否够用，否则进行扩容
ensureCapacity();
elementData[size] = element;
size++;
}
/**
* 在 List 的指定位置添加元素
*
* @param index 添加元素的位置
* @param element 待添加的元素
*/
public void add(int index, Object element) {
// 先判断指定的位置是否越界
rangeCheck(index);
// 再扩容
ensureCapacity();
// index 位置的数组向后移动一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
/**
* 获取 List 指定位置的元素
*
* @param index 指定的位置
* @return
*/
public Object get(int index) {
rangeCheck(index);
return elementData[index];
}
/**
* 移除指定位置的元素
*
* @param index 指定的位置
* @return 移除的元素
*/
public Object remove(int index) {
rangeCheck(index);
Object removedEle = elementData[index];
elementData[index] = null;
// index + 1 位置的数组往前移动一位
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
size--;
return removedEle;
}
/**
* 删除指定的元素
*
* @param element 待删除的元素
* @return 删除的元素的原位置
*/
public int remove(Object element) {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(element)) {
// 删除第一个和待删除元素 equals 的元素
elementData[i] = null;
System.arraycopy(elementData, i + 1, elementData, i, size - i - 1);
size--;
return i;
}
}
return -1;
}
/**
* 设置指定位置的元素
*
* @param index 指定的位置
* @param element 指定的元素
* @return 原位置的元素
*/
public Object set(int index, Object element) {
rangeCheck(index);
Object oldEle = elementData[index];
elementData[index] = element;
return oldEle;
}
/**
* 判断 List 是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 查询 List 中第一个和指定元素匹配的元素的索引
*
* @param element 指定的元素
* @return 元素的索引
*/
public int indexOf(Object element) {
// 先判断指定元素为 null 的情况
if (element == null) {
for (int i = 0; i < size; i++) {
if (elementData[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(element)) {
return i;
}
}
}
// 不存在则返回 -1
return -1;
}
/**
* 查询 List 中最后一个和指定元素匹配的元素的索引
*
* @param element 指定的元素
* @return 元素的索引
*/
public int lastIndexOf(Object element) {
if (element == null) {
for (int i = size - 1; i >= 0; i--) {
if (element == null) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (elementData[i].equals(element)) {
return i;
}
}
}
return -1;
}
/**
* 清空 List 中的元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
/**
* 将 List 转为数组
*
* @return
*/
public Object[] toArray() {
Object[] array = new Object[size];
for (int i = 0; i < size; i++) {
array[i] = elementData[i];
}
return array;
}
/**
* 将指定的 List 全部添加到原 List 的末尾
*
* @param myArrayList 待添加的 List
*/
public void addAll(MyArrayList myArrayList) {
// 扩容
if (size + myArrayList.size == elementData.length) {
Object[] newElementData = new Object[(size + myArrayList.size) * 2 + 1];
System.arraycopy(elementData, 0, newElementData, 0, size);
elementData = newElementData;
}
// 将待添加的 List 转为数组，并复制到原 List 的末尾
Object[] newArray = myArrayList.toArray();
System.arraycopy(newArray, 0, elementData, size, newArray.length);
size = size + newArray.length;
}
/**
* 将指定的 List 添加到原 List 的指定位置
*
* @param index 指定的位置
* @param myArrayList 待添加的 List
*/
public void addAll(int index, MyArrayList myArrayList) {
rangeCheck(index);
// 扩容
if (size + myArrayList.size == elementData.length) {
Object[] newElementData = new Object[(size + myArrayList.size) * 2 + 1];
System.arraycopy(elementData, 0, newElementData, 0, size);
elementData = newElementData;
}
// 原数组从 index 处向后移动，腾出位置插入新元素
System.arraycopy(elementData, index, elementData, index + myArrayList.size, size - index);
// 将待添加的 List 转为数组，并复制到原 List 的 index 处
Object[] newArray = myArrayList.toArray();
System.arraycopy(newArray, 0, elementData, index, newArray.length);
size = size + newArray.length;
}
/**
* 对 List 进行扩容
*/
private void ensureCapacity() {
if (size == elementData.length) {
Object[] newElementData = new Object[elementData.length * 2 + 1];
System.arraycopy(elementData, 0, newElementData, 0, size);
elementData = newElementData;
}
}
/**
* 检查指定的位置是否越界
*
* @param index 指定的位置
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
}
}
|