-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathArrayList.java
More file actions
120 lines (93 loc) · 2.48 KB
/
ArrayList.java
File metadata and controls
120 lines (93 loc) · 2.48 KB
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
package Implementations;
import java.util.Iterator;
public class ArrayList<T> implements List<T>, Iterable<T> {
private T[] array;
private int size = 0;
public ArrayList(){
array = (T[])new Object[3];
}
private void grow(){
T[] bigger = (T[])new Object[array.length * 3 / 2 + 1];
System.arraycopy(array, 0, bigger, 0, array.length);
array = bigger;
}
private void shrink(){
T[] smaller = (T[])new Object[size];
System.arraycopy(array, 0, smaller, 0, smaller.length);
array = smaller;
}
@Override
public void add(T item) {
if(array.length <= size)
grow();
array[size] = item;
size++;
}
@Override
public T get(int index) {
if(index >= size)
throw new IndexOutOfBoundsException();
return array[index];
}
@Override
public void remove(int index) {
if(index > size - 1)
throw new IndexOutOfBoundsException();
for (int i = index; i < size - 1; i++){
if(i == array.length - 1)
array[i] = null; //Todo: This seems to be not necessary
else
array[i] = array[i + 1];
}
size--;
//Shrink
if(array.length > size + (size * 3 / 2))
shrink();
}
@Override
public void clear() {
size = 0;
array = (T[])new Object[3];
}
@Override
public int getIndex(T item) {
for(int i = 0; i < size; i++)
if(array[i].equals(item))
return i;
return -1;
}
@Override
public int size() {
return size;
}
@Override
public void set(int index, T value) {
if(index >= size)
throw new IndexOutOfBoundsException();
array[index] = value;
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
for(int i = 0; i < size; i++) {
if(s.length() != 0)
s.append(", ");
s.append(array[i].toString());
}
return "[" + s.toString() + "]";
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int currentIndex = 0;
@Override
public boolean hasNext() {
return currentIndex < size;
}
@Override
public T next() {
return array[currentIndex++];
}
};
}
}