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
public class ArrayIntList {
/*
Reminders:
-- Lab is hybrid tomorrow: you may attend online or in-person.
-- Project01 is due tonight at 11:30pm.
-- We will evaluate at the end of the week if OH and lecture can be hybrid for next week.
Today: ArrayIntList
-> supposed to be a list that stores unbounded numbers of ints in an order
- What does it need to be able to do?
- add to end
- remove at index
- insert at index
- set an index
- get an index
- get size
- printable ("we need to convert to a string somehow")
- What does it need to "have inside"?
(design goal: minimize the number of fields)
"somewhere to store the data" -> ..an array of ints
-> some concept of "resizing"
"store the number of actual elements" -> size
ArrayLists have:
(1) capacity: "how big the internal array is"
-> client "user" shouldn't be able to edit
-> the fact that there is a capacity is not relevant to the user
(2) size: "how many elements there actually are"
*/
private int[] data;
// data[-]
// data.length ==== capacity
private int size;
// Implementor: [0, 0, 0, 0, 0, ...]
// Client: []
public ArrayIntList() {
this.data = new int[10];
this.size = 0;
}
/*
[0, 1, 2]
*/
public String toString() {
String result = "[";
for (int i = 0; i < this.size; i++) {
result += this.data[i] + ", ";
}
if (this.size != 0) {
result = result.substring(0, result.length() - 2);
}
return result + "]";
}
// size is the number of actual elements in the list
// capacity is the number of spaces we have to store elements
private void ensureCapacity() {
if (this.size >= this.data.length) {
// Create a new array of double size
int[] newData = new int[this.size * 2];
// Copy the contents from old to new
for (int i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
// Set the field to new array
this.data = newData;
}
}
public void add(int toAdd) {
this.add(this.size, toAdd);
}
/**
* 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, int element) {
// "the last one" is this.data[this.size - 1]
// "go backwards"
// [1, 2, 3, 4]
// ^
// 5
// [1, 2, 5, 5]
// valid idx inputs: 0, ..., this.size
if (!(0 <= idx && idx <= this.size)) {
throw new IllegalArgumentException();
}
this.ensureCapacity();
for (int i = this.size; i >= idx + 1; i--) {
// first iteration: this.data[this.size] = this.data[this.size - 1]
// last iteration: this.data[idx + 1] = this.data[idx]
this.data[i] = this.data[i - 1];
}
this.data[idx] = element;
this.size++;
}
public int get(int idx) {
return -1;
}
}