-
Notifications
You must be signed in to change notification settings - Fork 0
/
List_inArraySlots.java
153 lines (125 loc) · 4.46 KB
/
List_inArraySlots.java
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
/**
Implement a list of integer elements, including
both data and operations.
*/
public class List_inArraySlots {
private int[] elements; // container for the elements of the list
private int filledElements; // the number of elements in this list
private static final int INITIAL_CAPACITY = 10;
// *NEW* Head of the list of nodes
private Node headReference;
/**
Construct an empty list with a small initial capacity.
*/
public List_inArraySlots() {
elements = new int[ INITIAL_CAPACITY];
// filledElements has been initialized to the desired value, 0
}
/**
@return the number of elements in this list
*/
public int size() {
return filledElements;
}
/**
@return a string representation of this list,
in [a,b,c,] format
*/
public String toString() {
String result = "[";
for( int elemIndex = 0; elemIndex < filledElements; elemIndex++)
result += elements[ elemIndex] + ",";
return result + "]";
}
/**
Appends @value to the end of this list.
@return true, in keeping with conventions yet to be discussed
*/
public boolean add( int value) {
// expand if necessary
if( filledElements == elements.length) expand();
elements[ filledElements] = value;
filledElements++;
// idiomatic version: elements[ filledElements++] = value;
return true;
}
/**
Double the capacity of the List_inArraySlots,
preserving existing data.
*/
private void expand() {
System.out.println( "expand... (for debugging)");
/* S.O.P. rules for debugging:
Working methods should be silent. But during
development, the programmer must verify that
this method is called when that is appropriate.
So test using the println(), then comment it out.
*/
int[] bigger = new int[ elements.length * 2];
for( int elemIndex = 0; elemIndex < filledElements; elemIndex++)
bigger[ elemIndex] = elements[ elemIndex];
elements = bigger;
}
// --------- end of "code that worked in v0" ---------
/**
accessor
@return element @index from this list
precondition: @index is within the bounds of the array.
(Having warned the user about this precondition,
you should NOT complicate your code to check
whether user violated the condition.)
*/
public int get( int index ) {
// E-Z! pass through the request to the array object
return elements[ index];
}
/**
Set value at @index to @newValue
@return old value at @index
@precondition: @index is within the bounds of this list.
*/
public int set( int index, int newValue ) {
int saveForReturn = get( index);
elements[ index] = newValue;
return saveForReturn;
}
/**
Insert @value at position @index in this list.
Shift the element currently at that position (if any)
and any subsequent elements to the right
(that is, increase the index associated with each).
*/
public void add( int index, int value) {
if( index == filledElements) // adding at end of list
add( value);
else {// need space
// open up space, expanding if necessary
add( elements[ filledElements-1]);
// move the hole left / shift "subsequent elements" right
for( int hole = filledElements-1; hole > index; hole--)
elements[ hole] = elements[ hole-1];
elements[ index] = value; // store new value
}
}
/**
Remove the element at position @index in this list.
Shift any subsequent elements to the left (that is,
decrease the index associated with each).
@return the value that was removed from the list
*/
public int remove( int index) {
int result = elements[ index]; // save for returning
for( int put = index; put < filledElements-1; put++)
elements[ put] = elements[ put+1];
filledElements--;
return result;
}
// *NEW* Creates the head of the list
public boolean addAsHead( Object val) {
if (size() == 0) { headReference = new Node( val );}
else {
headReference = new Node( val, headReference);
}
return true;
}
}