8.1. ArrayList Implementation¶
8.1.1. Full Implementation¶
Below is a complete implementation for the array-based list, named MHCArrayList.
MHCArrayList must implement all of the methods of the MHCList interface.
Note
We provide the full implementation for completeness, but we will focusing on only a few methods in the following sections.
import java.util.Arrays;
/**
* Array-based list implementation of the MHCList interface.
*/
public class MHCArrayList<E> implements MHCList<E> {
private E[] elements; // Array holding list elements
private int capacity; // Maximum number of values that fit in the array
private int size; // Current number of elements in the list
// Constructor: creates a list with a default capacity of 10
@SuppressWarnings("unchecked") // Generic array allocation
public MHCArrayList() {
elements = (E[]) new Object[10]; // Initialize elements array to 10 by default
capacity = elements.length;
size = 0;
}
// Replaces the element at the specified position in this list with the specified element.
public void set(int position, E o) {
// Check that the position is valid
if (position < 0 || position >= size) {
throw new IndexOutOfBoundsException(position);
}
elements[position] = o;
}
// Returns the element at the specified position in this list.
public E get(int position) {
if (position < 0 || position >= size) {
throw new IndexOutOfBoundsException(position);
}
return elements[position];
}
// Returns the number of elements in this list.
public int size() {
return size;
}
// Helper method to resize the array when it's full
private void grow() {
capacity = 2 * capacity;
// Utility method that copies elements into a new array with the larger capacity
elements = Arrays.copyOf(elements, capacity);
}
// Appends the specified element to the end of this list.
public boolean add(E o) {
// If the array is full, make it bigger.
if (size >= capacity) {
grow();
}
elements[size] = o;
size++; // We've added an element, increase the size of the list
// indicate that the add was successful
return true;
}
// Inserts the specified element at the specified position in this list.
public void add(int position, E o) {
if (position < 0 || position > size) {
throw new IndexOutOfBoundsException(position);
}
// If the array is full, make it bigger.
if (size >= capacity) {
grow();
}
// Shift elements to the right to make space at the position
for (int i = size; i > position; i--) {
elements[i] = elements[i - 1];
}
elements[position] = o;
size++; // We've added an element, increase the size of the list
}
// Removes the element at the specified position in this list, and returns it.
public E remove(int position) {
// Check that the position is valid
if (position < 0 || position >= size) {
throw new IndexOutOfBoundsException(position);
}
E removedElement = elements[position];
// Shift elements to the left
for (int i = position; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
size--; // Update size
return removedElement;
}
public boolean isEmpty() {
return this.size == 0;
}
// Returns a string representation of the list elements
public String toString() {
// use square brackets to indicate beginning/end of list
String out = "[";
for(int i = 0; i < this.size; i++) {
out = out + this.elements[i].toString();
if (i < this.size - 1) {
out = out + ", "; // add a comma separator if this is not the last element
}
}
out = out + "]";
return out;
}
}
8.1.2. How ArrayLists internally represent data¶
Note
Make sure to click through all the animations until the green check mark shows up to see all the content!
8.1.3. Instance variables and constructors¶
Below is the constructor for our MHCArrayList class:
// Constructor: creates a list with a default capacity of 10
@SuppressWarnings("unchecked") // Generic array allocation
public MHCArrayList() {
elements = (E[]) new Object[10]; // Initialize elements array to 10 by default
capacity = elements.length;
size = 0;
}
We create a new empty array named elements that can hold 10 elements and initialize the capacity of the ArrayList to the length of the elements array. Because the programmer is creating a new MHCArrayList object, there are no data elements stored within it and so the size of the list begins at 0.
You’ll notice that there is something a little unusual going on in the initialization of the elements array:
elements = (E[]) new Object[10]; // Initialize elements array to 10 by default
Since the type E is generic, we actually cannot instantiate an array of type E.
We instead have to create an array of Object and cast or “convert” it to a type of E[], which is done with the parentheses: (E[]).
Note
We generally want to avoid using casting and instead use polymorphism to work with classes and subclasses. This is one of the few times we’ll see casting this semester!
You’ll also notice a line that begins with @ above the constructor, which is called an annotation:
@SuppressWarnings("unchecked") // Generic array allocation
We include this because the Java compiler knows that casting to an unknown type E[] is a risky operation, so it will display a warning message if we compile the code.
The annotation tells Java not to worry, and that we really do want to make this cast. But this again goes to show that casting should be used sparingly, if at all!
Note
Don’t worry about the specific details of this constructor – we have to use this syntax because of the way Java handles generic types. This is the only time we’ll see this syntax this semester.
8.1.4. Adding elements to a given position: add(int index, E o)¶
Because the array-based list implementation is defined to store list
elements in contiguous cells of the array, the add and remove
methods must maintain this property.
8.1.4.1. add() Interactive Exericse¶
8.1.5. Adding elements to end of list: add(E o)¶
Note
Notice that we can define two methods named add() with different behaviors.
That’s because the two methods have different parameters, so Java can differentiate between which method is being called by the parameter types being passed in.
This is known as overloading.
8.1.6. Removing elements at a given position: remove(int position)¶
Removing an element from the beginning of the list is
similar to add() in that all remaining elements must shift toward
the beginning by one position to fill in the gap.
If we want to remove the element at position \(i\), then
\(n - i - 1\) elements must shift toward the head, as shown in the
following widget.
In the worst case, insertion or removal each requires moving either \(n\) or \(n-1\) elements, which is \(O(n)\).