IMPLEMENTING LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 904

The constant INITIAL_CAPACITY (line 2) is used to create an initial array data (line 3).
Owing to generics type erasure, you cannot create a generic array using the syntax new
e[INITIAL_CAPACITY] . To circumvent this limitation, an array of the Object type is cre-
ated in line 3 and cast into E[] .
Note that the implementation of the second constructor in MyArrayList is the same as for
MyAbstractList . Can you replace lines 11-12 with super(objects) ? See Checkpoint
Question 24.8 for answers.
The add(int index, E e) method (lines 16-28) inserts element e at the specified
index in the array. This method first invokes ensureCapacity() (line 17), which ensures
that there is a space in the array for the new element. It then shifts all the elements after the
index one position to the right before inserting the element (lines 20-21). After the element
is added, size is incremented by 1 (line 27). Note that the variable size is defined as
protected in MyAbstractList , so it can be accessed in MyArrayList .
The ensureCapacity() method (lines 31-37) checks whether the array is full. If so, the
program creates a new array that doubles the current array size

add

ensureCapacity

1, copies the current array
to the new array using the System.arraycopy method, and sets the new array as the current
array.
The clear() method (lines 40-43) creates a new array using the size as
INITIAL_CAPACITY and resets the variable size to 0 . The class will work if line 41 is
deleted. However, the class will have a memory leak, because the elements are still in the
array, although they are no longer needed. By creating a new array and assigning it to data ,
the old array and the elements stored in the old array become garbage, which will be automati-
cally collected by the JVM.
The contains(E e) method (lines 46-51) checks whether element e is contained in the
array by comparing e with each element in the array using the equals method.
The get(int index) method (lines 54-57) checks if index is within the range and
returns data[index] if index is in the range.
The checkIndex(int index) method (lines 59-63) checks if index is within the range.
If not, the method throws an IndexOutOfBoundsException (line 61).
The indexOf(E e) method (lines 67-72) compares element e with the elements in the
array, starting from the first one. If a match is found, the index of the element is returned;
otherwise, -1 is returned.
The lastIndexOf(E e) method (lines 76-81) compares element e with the elements in
the array, starting from the last one. If a match is found, the index of the element is returned;
otherwise, -1 is returned.
The remove(int index) method (lines 86-101) shifts all the elements after the index
one position to the left (lines 92-93) and decrements size by 1 (line 98). The last element is
not used anymore and is set to null (line 95).
The set(int index, E e) method (lines 105-110) simply assigns e to data[index]
to replace the element at the specified index with element e .
The toString() method (lines 113-122) overrides the toString method in the Object
class to return a string representing all the elements in the list.
The trimToSize() method (lines 125-131) creates a new array whose size matches
the current array-list size (line 127), copies the current array to the new array using the
System.arraycopy method (line 128), and sets the new array as the current array (line 129).
Note that if size == capacity , there is no need to trim the size of the array.
The iterator() method defined in the java.lang.Iterable interface is
implemented to return an instance on java.util.Iterator (lines 134-136). The
ArrayListIterator class implements Iterator with concrete methods for hasNext ,
next , and remove (lines 143-155). It uses current to denote the current position of the
element being traversed (line 140).
Listing 24.4 gives an example that creates a list using MyArrayList . It uses the
add method to add strings to the list and the remove method to remove strings. Since

+

clear

contains

checkIndex

indexOf

lastIndexOf

remove

set

toString

trimToSize

iterator