[Code Compare] 1. ArrayList vs Collections.singletonList

I am starting a new thread to compare different ways to code the same functionality. In this post, I'll compare two common methods to create a simple list with only one element. Specifically, I'll examine the most commonly used List implementation constructor and the Collections.singletonList, a straightforward Factory Method for creating an immutable list containing a single element.

Array List

Everytime you initialize an ArrayList without specifying its initial capacity, it starts with an empty array. When you add the first element, the ArrayList resizes using a relatively havy algorithm that involves copying the array. Let's take a look at the ArrayList structure:

  private static final int DEFAULT_CAPACITY = 10;
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

  public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
  }

  private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
  }

  private Object[] grow() {
      return grow(size + 1);
  }

  private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                      newCapacity(minCapacity));
  }

  private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
  }

Here's what happens step-by-step:

1. An initial empty array elementData is created.
2. When you add the first element, the current size (which is zero) is compared to the length of the array.
3. Since it found out that the its size is zero, the array needs to grow to accomodate the new element.
4. The grow method is called, which calculates the new capacity.
5. The newCapacity is initially increased by half the old capacity, which let us with 0 + 0/2 = 0.
6. Since newCapacity is not sufficient to accomodate the element, it continues.
7. As it found out that elementData is the same initial empty array, it finally returns maximum between the required size (1) and the DEFAULT_CAPACTIY (10), resulting in an array of size 10.

This resizing process is quite complex when you only need a simple list that will always contain a single element.

That said, let's talk about our alternative!

Collection::singletonList

Method signature:

public static <T> List<T> singletonList(T o)

Description

This method returns an immutable list containing only the specified object. Introducted in Java 1.3, singletonList has several advantages:

1. Inline implementation: You can initialize it with the desired element in a single line.

2. Immutability: Let's take a look at its implementation:
   

   private static class SingletonList<E> extends AbstractList<E>
       implements RandomAccess, Serializable {
   
     private final E element;
   
     SingletonList(E obj) {
       element = obj;
     }
     ...
   }
   

   The AbstractList, from which SingletonList inherits, defines all mutable methods like this:
   

     public boolean add(E e) {
       add(size(), e);
       return true;
     }
   
     public void add(int index, E element) {
       throw new UnsupportedOperationException();
     }
   
     public E remove(int index) {
       throw new UnsupportedOperationException();
     }
   
     public E set(int index, E element) {
         throw new UnsupportedOperationException();
     }
   

   This ensures that it's impossible to chante the list's size or the content of its single element.

   Immutability is a highly advantageous feature. While I won't delve into it here, interested developers can learn more from this article.

3. Memory Allocation: The SingletonList class contains only one simple field to accommodate the single element, unlike ArrayList, which uses an array that, using simple ArrayList simple constructor, will leave us with an array with size of 10 after element addition.

4. CPU usage: The SingletonList constructor accepts the single element as a parameter, requiring no resizing, array copy or maniputalion. This is far more efficient compared to the ArrayList add method.

Conclusion

In this post, we compared two ways to create a simple list with a single element: using the ArrayListconstructor and the Collection.singletonList method. While ArrayList is a flexible and commonly used data structure, it comes with some unnecessary overhead, particularly in terms of memory allocation and CPU usage when adding elements. This overhead includes resizing and copying arrays, which can be redundant for a list that is meant to hold only one element. However, if you need to change this element, ArrayList is a suitable solution.

On the other hand, Collection.singletonList offers a more efficient alternative for creating a single-element list. This method is not only more concise and easier to use but also ensures immutability, which can be a significant advantage in many scenarios. It has a minimal memory footprint and requires almost no CPU resources compared to ArrayList.

In summary, for a simple, immutable list containing only one element, Collection.singletonList is a superior choice due to its efficiency, simplicity, and immutability. However, if you need to modify the element in the list, the ArrayList could be an more appropriate choice.

On the next post I'll compare another alternative for a single-element list: List.of factory method. See you later!