Simplified ArrayList Implementation

An ArrayList stores a collection of references to objects.

This page assumes you already understand arrays.

• The Java Collections Framework provides a few classes that implement the List<E> interface.
• The ArrayList<E> class.
  • This is basically a souped up array.
  • You can think of this class as containing one instance variable that is a reference to an array and a number of methods that implement the List<E> interface.
  • The actual ArrayList<E> implementation is more involved, but a simplified version of the ArrayList<E> class might look something like this:

    public class ArrayList<E> implements List<E>, RandomAccess {
        private E[] elements = null;
    
        @Override
        public boolean isEmpty() {
            return elements!=null;
        }
    
        @Override
        public void clear() {
            elements = null;
        }
    
        @Override
        public int size() {
            return elements==null ? 0 : elements.length;
        }
    
        @Override
        public boolean add(E element) {
            E[] temp = (E[])new Object[size()+1];
            for(int i=0; i < size(); ++i) {
                temp[i] = get(i);
            }
            temp[size()] = element;
            elements = temp;
            return true;
        }
    
        @Override
        public E get(int index) {
            checkIndexOutOfBounds(index);
            return elements[index];
        }
    
        @Override
        public E set(int index, E element) {
            checkIndexOutOfBounds(index);
            E oldElement = get(index);
            elements[index] = element;
            return oldElement;
        }
    
        private void checkIndexOutOfBounds(int index) {
            if(index < 0 || index>=size()) {
                throw new IndexOutOfBoundsException("Index: " + index + " Size: " + size());
            }
        }
    
        // Other methods of the List interface ...
    
    }
    

  • We can create an ArrayList and add some items to it:

    List<String> list = new ArrayList<>();
    list.add("dog");
    list.add(null);
    list.add("pig");
    list.add("cat");
    list.add("cow");
    list.add(null);
    

  • Here is a memory diagram for an ArrayList:

    

  • Again, this is a very simplified version of what really goes on.
  • A more legitimate version of the ArrayList<E> class would not force a new array to be created each time add(E) was called.
  • Instead, it is typical to
    • Create an array that is larger than what is currently required (the size of the array is often referred to as the capacity of the array).
    • An additional attribute is stored in the ArrayList<E> that keeps track of the size of the ArrayList<E>.
    • Whenever add(E) is called, the size is compared with the capacity in order to determine if it is necessary to create a new array.
    • Such an implementation is much more efficient.