Performance Comparison of Java ArrayList and LinkedList

ArrayList and LinkedList are two classes in the Java Collections Framework that implement the List interface. A List is an ordered collection that allows duplicate and null values and provides index‑based access.

The article examines the performance differences between the two when adding, inserting, removing, and traversing elements.

Adding elements to the tail

ArrayList adds an element by ensuring capacity and placing the element at the end of the internal array:

public boolean add(E e) {
    ensureCapacity(size + 1);
    elementData[size++] = e;
    return true;
}

The ensureCapacity method expands the internal array when needed:

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object[] oldData = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity) newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

When the current capacity is sufficient, the add operation is very fast; only when the array must grow does it incur the cost of copying.

LinkedList adds an element by creating a new node and linking it before the header:

public boolean add(E e) {
    addBefore(e, header);
    return true;
}

The helper method creates a new Entry and updates the surrounding links:

private Entry
addBefore(E e, Entry
entry) {
    Entry
newEntry = new Entry<>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

Because LinkedList does not need to manage capacity, its add operation avoids array copying, but it must allocate a new node and update pointers.

Inserting elements at an arbitrary position

ArrayList must shift elements after the insertion point, which involves an array copy:

public void add(int index, E element) {
    if (index > size || index < 0) throw new IndexOutOfBoundsException();
    ensureCapacity(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

LinkedList inserts by linking a new node at the desired position without moving other elements:

public void add(int index, E element) {
    addBefore(element, (index == size ? header : entry(index)));
}

Thus, insertion cost is constant for LinkedList but can be costly for ArrayList, especially near the front of the list.

Removing elements

ArrayList removal also requires shifting subsequent elements:

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;
}

LinkedList removal finds the node and relinks its neighbors:

public E remove(int index) {
    return remove(entry(index));
}
private Entry
entry(int index) {
    // locate node from head or tail depending on index
    // ... (traversal code omitted for brevity)
    return e;
}

Both structures have O(1) removal at the tail, but removal near the front is cheaper for LinkedList.

Capacity considerations

ArrayList has an initial capacity (default 10) that can be set via a constructor; choosing an appropriate initial size reduces the number of costly expansions.

public ArrayList() { this(10); }
public ArrayList(int initialCapacity) {
    if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity:" + initialCapacity);
    this.elementData = new Object[initialCapacity];
}

Benchmarking shows constructing a list with a pre‑sized capacity (e.g., 1,000,000) is much faster than letting it grow automatically.

Iterating over the list

Three common iteration methods are compared: enhanced for‑each, iterator, and indexed for loop. Benchmarks reveal that for‑each is the slowest, iterator is moderate, and indexed for loop is fastest for ArrayList, while LinkedList performs poorly with random access.

String tmp;
long start = System.currentTimeMillis();
for (String s : list) { tmp = s; }
System.out.println("foreach spend:" + (System.currentTimeMillis() - start));
// iterator version
for (Iterator
it = list.iterator(); it.hasNext(); ) { tmp = it.next(); }
System.out.println("Iterator spend:" + (System.currentTimeMillis() - start));
// indexed for loop
int size = list.size();
for (int i = 0; i < size; i++) { tmp = list.get(i); }
System.out.println("for spend:" + (System.currentTimeMillis() - start));

Results show that random access on LinkedList is extremely slow and should be avoided.

Summary

ArrayList provides fast tail additions and efficient random access but suffers from costly shifts when inserting or deleting in the middle; it also wastes space due to unused capacity. LinkedList offers constant‑time insertions and deletions anywhere but has poor random‑access performance and higher per‑element memory overhead. Choose ArrayList for frequent random reads and tail appends, and LinkedList when many insertions or deletions occur near the front or middle of the list.