Array Lists

The ListDeque Application

The examples in this and the subsequent two documents all part of the Java Application ListDeque. Download the source archive ListDeque.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Like others, the ListDeque project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

User-defined data structures

Why would we want to write our own implementations of data structures when Java already has everything we need? There are several goals: In this document we will focus on the ArrayList class. We will follow a method suggested by these steps:
  1. Create illustrative examples to see the Java Collections ArrayList member functions work.
  2. Create a "dummy" class, called AListAdapter, which implements all the relevant interfaces and member functions that ArrayList implements, but with implementation functions which effectively say "not implemented."
  3. Create an extension of AListAdapter called AList in which implements the member functions by overriding the AListAdapter definitions. Because AList is an extension of the "working" class, AListAdapter, there is no need to define every function, only those of interest to us.

ArrayList Demo

Start by observing and running the main class demo.AListDemo.
demo.AListDemo  
Observe how we express the list declaration operation:
List<String> L = new ArrayList<>();
Abstractly, we might say the statement is of the form:
Interface obj = new Implementation();
We conceivable could use this:
ArrayList<String> L = new ArrayList<>();
In general, the former declaration (using the List interface) is preferred because it allows the application to change the implementation very easily, since it is presumed that the only operations used are those specified by the interface.

If we do use some ArrayList-specific operation we wish to use we would need to cast the object:
((ArrayList<T>) L).operation
Of course, by doing so would lose the implementation-independency of the code.

Explicit and Implicit operations

In the demo program, we see the usage of common list member functions:
add, size, get, set, remove, clear, isEmpty
Additionally, there are several operations which are used implicitly:

ArrayList Implementation

We're going to construct our own implementation of ArrayList called AList. The basic idea is that it is simply a wrapper around an array which resizes as necessary in a manner transparent to the usage.

AListAdapter

The basis of our construction is an adapter class, AListAdapter.
adapter.AListAdapter  
The idea of an adapter class is that it implements all the ArrayList functions, but only in a vacuous manner. The functions are all implemented in the sense that their only code is to throw an UnsupportedOperationException. Our user-defined AList class then will be an extension of AListAdapter and we can pick and choose the functions we want to implement.

AListAdapter implicitly implements the Collection and Iterator interfaces as well because they super-interfaces of List. The Serializable interface requires no implementations and implies that an AListAdapter object can be written to a file or sent through the network. The RandomAccess interface also requires no implementations and is only used to guarantee for users of this class that "get/set" member functions are constant time, O(1).

AList Implementation

Here is the Java implementation class:
util.AList  
Try it out by making the code change in main of the AListDemo program:
  public static void main(String[] args) {
//    List<String> L = new ArrayList<>();
    List<String> L = new AList<>();

Basic ArrayList Features

The array has as certain capacity, but the actual content is controlled by the current size. The private data members used to handle that are these:
private int size = 0;
private E[] data;
It is assumed that all member functions keep track of size correctly so that we can give these definitions:
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
public void clear() { size = 0; }
The primary constructor is this:
public AList(int capacity) {
  data = (E[]) new Object[capacity];
}
Observe how we must deal with creating an array of the unknown generic type E. If a user doesn't care to specify the capacity, these are used:
private static final int DEFAULT_CAPACITY = 10;
 
public AList() { this(DEFAULT_CAPACITY); }
The most basic capacity handler is a private function which creates a new array and copies over the old one:
private void increaseCapacity(int new_capacity) {
  if (new_capacity <= data.length) {
    return;
  }
  E[] new_data = (E[]) new Object[new_capacity];
  for (int i = 0; i < capacity; ++i) {
    new_data[i] = data[i];
  }
  data = new_data;
}
The most basic member function is the add function which adds to the array's end:
public boolean add(E elt) {
  if (size == data.length) {
    increaseCapacity( data.length * 2 );  
  }
  data[size++] = elt;
  return true;
}

Constant-time add operation

If an add operation does not increase the capacity, it is a constant-time cost, O(1), to do the operation. If, however, an add operation causes the capacity to increase, the cost is O(n) based on the size, n of the array due to the need of copying over the array. We want to argue that if the capacity is increased by doubling, the average cost of an operation is still O(1).

Consider the operation of filling an empty ArrayList with values by using the add operation. The initial capacity is 10 and whenever size would exceed capacity, we increase the capacity by calling:
increaseCapacity( 2 * capacity ); // change array size and copy over
Let overhead(n) be the total number of element copy operations which have taken place when the array size has just exceeded n elements. Consider the values
n = 10, 20, 40, 80, 160 ....
and observe that overhead(n) satisfies this recurrence relation:
overhead(10) = 10
overhead(n)  = overhead(n/2) + n,  n ≥ 20
We can prove by induction that
overhead(n) ≤ 2 * n
Since this is the total overhead for n adds, the average overhead for a single add operation is:
overhead(n)/n ≤ 2
We conclude that the average time to add is O(1) even with the overhead.

Search-related Operations

One of the key notions of a List is that it keeps track of the position of elements. The search operations use a linear searche front to rear or vice-versa since there is no presumed structure on the data.
public int indexOf(Object obj) {
  for (int i=0; i < size; ++i) {
    if (data[i].equals(obj)) return i;
  }
  return -1;
}
 
public int lastIndexOf(Object obj) {
  for (int i=size; i > 0; --i) {
    if (data[i-1].equals(obj)) return i-1;
  }
  return -1;
}
 
public boolean contains(Object obj) {
  return indexOf(obj) != -1;
}

null values

We noted in the Analysis section that null values can cause probles using the equals operator. Our code above implicitly assumes that there are no null values in the list. To avoid this assumption, the gimmick is to treat obj=null as a special case, thus rewriting indexOf like this:
public int indexOf(Object obj) {
  if (obj == null) {
    for (int i=0; i < size; ++i) {
      if (data[i] == null) {
        return i;
      }
    }
  }
  else {
    for (int i=0; i < size; ++i) {
      if (obj.equals(data[i])) {
        return i;
      }
    }
  }
  return -1;
}
An analogous thing would be done with lastIndexOf.

Equality in User-defined classes

If you want to use your own user-defined classes in Java Lists, the only catch is that you have to have a correctly defined equals method for the search-related operations. Here is a demo program which illustrates two classes, Person and User, The Person equals definition is correct, whereas the User equals definition is incorrect regarding searches of lists of these classes.
demo.ListElementEquality  

Positional add/remove

The other operations are insertion or removal at a position which causes the data to the right of the insert or remove position to be shifted right or left, respectively.
public void add(int index, E elt) {
  if (index > size || index < 0) {
    throw new
      IndexOutOfBoundsException("Index: " + index + ", " + "Size: " + size);
  }
  if (size == data.length) {
    increaseCapacity(data.length*2); 
  }
  for (int i = size; i > index; --i) { // shift these up
    data[i] = data[i-1];
  }
  data[index] = elt; // insert this one
  ++size;
}
 
public E remove(int index) {
  if (index >= size || index < 0) {
    throw new
      IndexOutOfBoundsException("Index: " + index + ", " + "Size: " + size);
  }
  E saved = data[size];
  for (int i=index; i < size-1; ++i) {  // shift elements down
    data[i] = data[i+1];
  }
  --size;
  return saved;
}
 
public boolean remove(Object o) {
  int i = indexOf(o);
  if (i == -1) {
    return false;
  }
  remove(i);
  return true;
}

The iterator and other operations

We mentioned above about the implicitly used member functions iterator and toString. In order to handle these situations we use the following functions:
public Object[] toArray() { 
  return Arrays.copyOf(data, size); 
}
 
public String toString() { 
  return Arrays.toString(toArray()); 
}
 
public ListIterator<E> listIterator() {
  return Arrays.asList( (E[]) toArray() ).listIterator();
}
 
public Iterator<E> iterator() { 
  return listIterator(); 
}
The textbook goes to pains to illustrate how to define the iterator. We have side-stepped the issue by:

Creating the iterator from scratch

If we want to define these ourselves, we can either defined the iterator function which returns an implementation of the Iterator interface with these functions:
public boolean hasNext()
public E next()
public void remove()
or define the listIterator function which returns an implementation of the extended ListIterator interface with these additional functions:
public int nextIndex()
public E previous()
public int previousIndex()
public void add(E elt)
public void set(E elt)
public boolean hasPrevious()
The add and remove operations are potentially the most difficult, but, according to the Java documentation, these operations are "optional", which means that we can implement them by saying that they're not implemented, which in Java terms means:
throw new UnsupportedOperationException();
The other point noted in the textbook is that the implementation class needs to be an inner class so that it can access the private data. Since this class need never be reused, we'll make it an anonymous inner class, giving us a definition like this:
public ListIterator<E> listIterator() {
  return new ListIterator<E>() {
    private int index = 0;
 
    public boolean hasNext() { return index < size; }
    public E next() { return data[index++]; }
 
    public int nextIndex() { return index+1; }
    public int previousIndex() { return index-1; }
    public E previous() { return data[--index]; }
    public void set(E elt) { data[index] = e; }
    public boolean hasPrevious() { return index > 0; }
 
    public void remove() { 
      throw new UnsupportedOperationException(); 
    }
    public void add(E elt) { 
      throw new UnsupportedOperationException();
    }
  };
}


© Robert M. Kline