Array Lists

An array list is implemented using an array. An array is a fixed-size data structure. Once an array is created, its size cannot be changed.
Nevertheless, you can still use arrays to implement dynamic data structures. The trick is to create a larger new array to replace the current array, if the current array cannot hold new elements in the list.

Initially, an array, say data of E[] type, is created with a default size. When inserting a new element into the array, first make sure that there is enough room in the array. If not, create a new array twice as large as the current one. Copy the elements from the current array to the new array. The new array now becomes the current array. Before inserting a new element at a specified index, shift all the elements after the index to the right and increase the list size by 1, as shown in Figure below.

The data array is of type E[]. Each cell in the array actually stores the reference of an object.

To remove an element at a specified index, shift all the elements after the index to the left by one position and decrease the list size by 1, as shown in Figure below.

MyArrayList uses an array to implement MyAbstractList, as shown in Figure below. Its implementation is given in the code below.

package demo;

public class MyArrayList<E> extends MyAbstractList<E> {
    public static final int INITIAL_CAPACITY = 16;
    private E[] data = (E[]) new Object[INITIAL_CAPACITY];

    /** Create a default list */
    public MyArrayList() {}

    /** Create a list from an array of objects */
    public MyArrayList(E[] objects) {
        for(int i = 0; i < objects.length; i++)
            add(objects[i]); // Warning: don't use super(objects)!
    }

    @Override /** Add a new element at the specified index */
    public void add(int index, E e) {
        ensureCapacity();

        // Move the elements to the right after the specified index
        for(int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        // Insert new element to data[index]
        data[index] = e;

        // Increase size by 1
        size++;
    }

    /** Create a new larger array, double the current size + 1 */
    private void ensureCapacity() {
        if(size >= data.length) {
            E[] newData = (E[])(new Object[size * 2 + 1]);
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }

    @Override /** Clear the list */
    public void clear() {
        data = (E[])new Object[INITIAL_CAPACITY];
        size = 0;
    }

    @Override /** Return true if this list contains the element */
    public boolean contains(E e) {
        for(int i = 0; i < size; i++)
            if(e.equals(data[i])) return true;

        return false;
    }

    @Override /** Return the element at the specified index */
    public E get(int index) {
        checkIndex(index);
        return data[index];
    }

    private void checkIndex(int index) {
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException
            ("index " + index + " out of bounds");
    }

    @Override /** Return the index of the first matching element
    in this list. Return -1 if no match. */
    public int indexOf(E e) {
        for(int i = 0; i < size; i++)
            if(e.equals(data[i])) return i;

        return -1;
    }

    @Override /** Return the index of the last matching element
    in this list. Return -1 if no match. */
    public int lastIndexOf(E e) {
        for(int i = size - 1; i >= 0; i--)
            if(e.equals(data[i])) return i;

        return -1;
    }

    @Override /** Remove the element at the specified position
    in this list. Shift any subsequent elements to the left.
    Return the element that was removed from the list. */
    public E remove(int index) {
        checkIndex(index);

        E e = data[index];

        // Shift data to the left
        for(int j = index; j < size - 1; j++)
            data[j] = data[j + 1];

        data[size - 1] = null; // This element is now null

        // Decrement size
        size--;

        return e;
    }

    @Override /** Replace the element at the specified position
    in this list with the specified element. */
    public E set(int index, E e) {
        checkIndex(index);
        E old = data[index];
        data[index] = e;
        return old;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("[");

        for(int i = 0; i < size; i++) {
            result.append(data[i]);
            if(i < size - 1) result.append(", ");
        }

        return result.toString() + "]";
    }

    /** Trims the capacity to current size */
    public void trimToSize() {
        if(size != data.length) {
            E[] newData = (E[])(new Object[size]);
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        } // If size == capacity, no need to trim
    }

    @Override /** Override iterator() defined in Iterable */
    public java.util.Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements java.util.Iterator<E> {
        private int current = 0; // Current index

        @Override
        public boolean hasNext() {
            return (current < size);
        }

        @Override
        public E next() {
            return data[current++];
        }

        @Override
        public void remove() {
            MyArrayList.this.remove(current);
        }
    }
}

The constant INITIAL_CAPACITY (line 4) is used to create an initial array data (line 5). 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 created in line 5 and cast into E[].

Note that the implementation of the second constructor in MyArrayList is the same as for MyAbstractList. Can you replace lines 12–13 with super(objects)?

The add(int index, E e) method (lines 17–29) inserts element e at the specified index in the array. This method first invokes ensureCapacity() (line 18), 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 21–22). After the element is added, size is incremented by 1 (line 28). Note that the variable size is defined as protected in MyAbstractList, so it can be accessed in MyArrayList.

The ensureCapacity() method (lines 32–38) checks whether the array is full. If so, the program creates a new array that doubles the current array size + 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 41–44) creates a new array using the size as INITIAL_CAPACITY and resets the variable size to 0. The class will work if line 42 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 automatically collected by the JVM.

The contains(E e) method (lines 47–52) 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 55–58) checks if index is within the range and returns data[index] if index is in the range.

The checkIndex(int index) method (lines 60–64) checks if index is within the range. If not, the method throws an IndexOutOfBoundsException (line 62).

The indexOf(E e) method (lines 68–73) 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 77–82) 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 87–102) shifts all the elements after the index one position to the left (lines 93–94) and decrements size by 1 (line 99). The last element is not used anymore and is set to null (line 96).

The set(int index, E e) method (lines 106–111) simply assigns e to data[index] to replace the element at the specified index with element e.

The toString() method (lines 114–123) overrides the toString method in the Object class to return a string representing all the elements in the list.

The trimToSize() method (lines 126–132) creates a new array whose size matches the current array-list size (line 128), copies the current array to the new array using the System.arraycopy method (line 129), and sets the new array as the current array (line 130). 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 135–137). 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).

The code below 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 MyArrayList implements Iterable, the elements can be traversed using a for-each loop (lines 38–39).

(1) [America]
(2) [Canada, America]
(3) [Canada, America, Russia]
(4) [Canada, America, Russia, France]
(5) [Canada, America, Germany, Russia, France]
(6) [Canada, America, Germany, Russia, France, Norway]
(7) [America, Germany, Russia, France, Norway]
(8) [America, Germany, France, Norway]
(9) [America, Germany, France]
(10) AMERICA GERMANY FRANCE