ArrayList vs LinkedList: When Each Data Structure Truly Shines

Test Results

The author measured the time required to insert and search 100,000 elements at the head, tail, and middle of both ArrayList and LinkedList.

Note: Tail insertions were performed on an empty list, while head and middle insertions were tested on a list already containing 100,000 elements.

Test Conclusions

ArrayList provides excellent lookup performance regardless of element position.

ArrayList performs well for tail insertions (the later the position, the better), but its performance degrades sharply for head and middle insertions.

LinkedList offers fast head and tail insertions/lookups, yet its middle‑position operations are dramatically slower and not comparable to ArrayList.

Source Code Analysis

ArrayList and LinkedList are Java implementations of a sequential list and a doubly linked list, respectively. Before diving into the code, we briefly review the key concepts of these data structures.

Sequential list: Requires contiguous memory; inserting or deleting in the middle shifts subsequent elements.

Doubly linked list: Uses node pointers; insertion/deletion does not move elements, only updates pointers.

Thus we often assume "ArrayList is fast for lookup and slow for modifications, while LinkedList is the opposite"—let's verify this.

Test Program

The test code itself is omitted; only the execution results are presented for analysis.

Execution Results

ArrayList tail insertion of 100,000 elements: 26ms LinkedList tail insertion of 100,000 elements: 28ms ArrayList head insertion of 100,000 elements: 859ms LinkedList head insertion of 100,000 elements: 15ms ArrayList middle insertion of 100,000 elements: 1848ms LinkedList middle insertion of 100,000 elements: 15981ms ArrayList head read of 100,000 elements: 7ms LinkedList head read of 100,000 elements: 11ms ArrayList tail read of 100,000 elements: 12ms LinkedList tail read of 100,000 elements: 9ms ArrayList middle read of 100,000 elements: 13ms LinkedList middle read of 100,000 elements: 11387ms

ArrayList Tail Insertion

add(E e)

method

public boolean add(E e) {<br/>    // check capacity<br/>    ensureCapacityInternal(size + 1);<br/>    // insert at tail<br/>    elementData[size++] = e;<br/>    return true;<br/>}

Tail insertion requires no extra work.

LinkedList Tail Insertion

LinkedList defines head and tail nodes.

transient Node<E> first;<br/>transient Node<E> last;

add(E e)

calls linkLast(e).

public boolean add(E e) {<br/>    linkLast(e);<br/>    return true;<br/>}

linkLast(E e)

appends directly using the stored tail reference.

void linkLast(E e) {<br/>    final Node<E> l = last;<br/>    final Node<E> newNode = new Node<>(l, e, null);<br/>    last = newNode;<br/>    if (l == null)<br/>        first = newNode;<br/>    else<br/>        l.next = newNode;<br/>    size++;<br/>    modCount++;<br/>}

ArrayList Head Insertion

add(int index, E element)

shifts elements with System.arraycopy.

public void add(int index, E element) {<br/>    rangeCheckForAdd(index);<br/>    ensureCapacityInternal(size + 1);<br/>    System.arraycopy(elementData, index, elementData, index + 1, size - index);<br/>    elementData[index] = element;<br/>    size++;<br/>}

LinkedList Head Insertion

add(int index, E element)

delegates to linkLast if inserting at the tail, otherwise to linkBefore.

public void add(int index, E element) {<br/>    checkPositionIndex(index);<br/>    if (index == size)<br/>        linkLast(element);<br/>    else<br/>        linkBefore(element, node(index));<br/>}

The node(int index) method walks from the head or tail depending on the index.

Node<E> node(int index) {<br/>    if (index < (size >> 1)) {<br/>        Node<E> x = first;<br/>        for (int i = 0; i < index; i++) x = x.next;<br/>        return x;<br/>    } else {<br/>        Node<E> x = last;<br/>        for (int i = size - 1; i > index; i--) x = x.prev;<br/>        return x;<br/>    }<br/>}

linkBefore(E e, Node<E> succ)

inserts a new node before the given successor.

void linkBefore(E e, Node<E> succ) {<br/>    final Node<E> pred = succ.prev;<br/>    final Node<E> newNode = new Node<>(pred, e, succ);<br/>    succ.prev = newNode;<br/>    if (pred == null)<br/>        first = newNode;<br/>    else<br/>        pred.next = newNode;<br/>    size++;<br/>    modCount++;<br/>}

Summary

For LinkedList, both head and tail insertions run in O(1) time.

ArrayList head insertions shift many elements, resulting in high cost.

When inserting in the middle, ArrayList is nearly ten times faster than LinkedList.

ArrayList & LinkedList Lookup

ArrayList offers O(1) random access via index.

LinkedList lookup relies on the node() traversal; head/tail lookups are fast, but middle lookups degrade in performance.