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
public class OurArrayList<E> implements IList<E> {
private E[] data;
private int size;
public OurArrayList(int initialCapacity) {
this.data = (E[])new Object[initialCapacity];
this.size = 0;
}
public OurArrayList() {
this(10);
}
public String toString() {
if (this.size == 0) {
return "[]";
}
String result = "[";
for (int i = 0; i < this.size; i++) {
result += this.data[i] + ", ";
}
result = result.substring(0, result.length() - 2);
return result + "]";
}
public void add(E element) {
this.add(this.size, element);
}
/**
* Puts element at index idx, shifting over everything after to the right.
* @param idx
* @param element
* For example, idx = 2, element = 42
* [1, 2, 3, 4, 5]
* ^
* [1, 2, 42, 3, 4, 5]
*/
public void add(int idx, E element) {
resize();
for (int i = this.size; i > idx; i--) {
this.data[i] = this.data[i-1];
}
this.data[idx] = element;
this.size++;
}
private void resize() {
// size vs. capacity < how much storage space in the list
// ^ how many elements in the list
// capacity == this.data.length
if (this.size == this.data.length) {
// Time to resize!
E[] newData = (E[])new Object[this.data.length * 2];
for (int i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
}
}
@Override
public int size() {
return this.size;
}
@Override
public void set(int idx, E elem) {
if (idx < 0 || idx >= this.size) {
throw new IllegalArgumentException(idx + " is not a valid index!");
}
this.data[idx] = elem;
}
public E get(int idx) {
if (idx < 0 || idx >= this.size) {
throw new IllegalArgumentException(idx + " is not a valid index!");
}
return this.data[idx];
}
@Override
public void clear() {
this.size = 0;
}
}