-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArrayList.java
More file actions
169 lines (148 loc) · 4.54 KB
/
Copy pathArrayList.java
File metadata and controls
169 lines (148 loc) · 4.54 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
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
import java.util.NoSuchElementException;
/**
* Your implementation of an ArrayList.
*/
public class ArrayList<T> {
/*
* The initial capacity of the ArrayList.
*
* DO NOT MODIFY THIS VARIABLE!
*/
public static final int INITIAL_CAPACITY = 9;
/*
* Do not add new instance variables or modify existing ones.
*/
private T[] backingArray;
private int size;
/**
* This is the constructor that constructs a new ArrayList.
*
* Recall that Java does not allow for regular generic array creation,
* so instead we cast an Object[] to a T[] to get the generic typing.
*/
public ArrayList() {
//DO NOT MODIFY THIS METHOD!
backingArray = (T[]) new Object[INITIAL_CAPACITY];
}
/**
* Adds the data to the front of the list.
*
* This add may require elements to be shifted.
*
* Method should run in O(n) time.
*
* @param data the data to add to the front of the list
* @throws java.lang.IllegalArgumentException if data is null
*/
public void addToFront(T data) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
if (data == null) {
throw new IllegalArgumentException("Cannot add null to ArrayList.");
}
if(size == backingArray.length) {
resize();
}
//shift exiisting elements to the right by one
for(int i = size; i > 0; i--) {
backingArray[i] =backingArray[i - 1];
}
backingArray[0] = data;
size++;
}
/**
* Adds the data to the back of the list.
*
* Method should run in amortized O(1) time.
*
* @param data the data to add to the back of the list
* @throws java.lang.IllegalArgumentException if data is null
*/
public void addToBack(T data) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
if (data == null) {
throw new IllegalArgumentException("Cannot add null to ArrayList.");
}
if(size == backingArray.length) {
resize();
}
backingArray[size] = data;
size++;
}
/**
* Removes and returns the first data of the list.
*
* Do not shrink the backing array.
*
* This remove may require elements to be shifted.
*
* Method should run in O(n) time.
*
* @return the data formerly located at the front of the list
* @throws java.util.NoSuchElementException if the list is empty
*/
public T removeFromFront() {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
if (size == 0) {
throw new NoSuchElementException("Cannot remove from an empty ArrayList.");
}
final T elementRemoved = backingArray[0];
// Shift elements left by one
for (int i = 0; i < size - 1; i++) {
backingArray[i] = backingArray[i + 1];
}
backingArray[size - 1] = null;
size--;
return elementRemoved;
}
/**
* Removes and returns the last data of the list.
*
* Do not shrink the backing array.
*
* Method should run in O(1) time.
*
* @return the data formerly located at the back of the list
* @throws java.util.NoSuchElementException if the list is empty
*/
public T removeFromBack() {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
if (size == 0) {
throw new NoSuchElementException("Cannot remove from an empty ArrayList.");
}
T removedElement = backingArray[size - 1];
backingArray[size - 1] = null;
size--;
return removedElement;
}
/**
* Returns the backing array of the list.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the backing array of the list
*/
public T[] getBackingArray() {
// DO NOT MODIFY THIS METHOD!
return backingArray;
}
/**
* Returns the size of the list.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the size of the list
*/
public int size() {
// DO NOT MODIFY THIS METHOD!
return size;
}
private void resize() {
final T[] newArray = (T[]) new Object[backingArray.length * 2];
for(int i = 0; i< backingArray.length; i++){
newArray[i] = backingArray[i];
}
backingArray =newArray;
}
}