Differences Between Java List Implementations: ArrayList, LinkedList, Vector, and Stack

In the previous articles of the series we introduced the overall architecture of Java containers; this article focuses on the differences among the concrete classes that implement the List interface.

01. List Overview

"The List data structure is a sequence that stores elements in a contiguous block of memory, mapping each index to an address."

The simple inheritance diagram shows that ArrayList , LinkedList , Vector and Stack are the four main implementations of List .

AbstractCollection is an abstract class that implements most of the Collection interface, providing methods such as toArray() and remove() .

AbstractList extends AbstractCollection and implements all List methods except size() and get(int) , providing iterator support.

AbstractSequentialList extends AbstractList and implements the operations needed for linked‑list based lists.

ArrayList is a dynamic array with fast random access but slower insertions/deletions in the middle.

LinkedList is a doubly‑linked list that can also act as a stack, queue or deque; it has slow random access but fast insertions/deletions.

Vector is also a dynamic array; unlike ArrayList it is thread‑safe.

Stack extends Vector and follows the LIFO (first‑in‑last‑out) principle.

Below we analyse the core methods of each implementation.

02. ArrayList

"ArrayList implements List as a sequential container; elements are stored in the order they are added, null values are allowed, and the underlying structure is an array. It is not synchronized, unlike Vector ."

Since Java 1.5 generics are available, but they are only compile‑time syntactic sugar; the actual array is an Object[] to hold any type.

2.1 get method

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

/**
 * Checks whether the given index is within bounds
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

2.2 set method

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

2.3 add methods

ArrayList provides add(E e) and add(int index, E e) . Both may trigger a capacity check and automatic growth via the grow() method.

private void grow(int minCapacity) {
    // overflow‑conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5×
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The addAll() variants insert multiple elements either at the end or at a specified position; their time complexity is linear in the number of inserted elements and the insertion position.

2.4 remove methods

remove(int index) deletes the element at the given position, shifts subsequent elements left, and nulls the freed slot for GC.

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

remove(Object o) scans for the first matching element and removes it.

public boolean remove(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null) {
                fastRemove(i);
                return true;
            }
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i])) {
                fastRemove(i);
                return true;
            }
    }
    return false;
}

03. LinkedList

"LinkedList implements both List and Deque , so it can be used as a sequential container, a queue, or a stack."

It is built on a doubly‑linked list with first and last references.

public class LinkedList
extends AbstractSequentialList
implements List
, Deque
, Cloneable, java.io.Serializable {
    transient int size = 0;
    transient Node
first;
    transient Node
last;
    ...
}

private static class Node
{
    E item;
    Node
next;
    Node
prev;
    Node(Node
prev, E element, Node
next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

3.1 get method

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3.2 set method

public E set(int index, E element) {
    checkElementIndex(index);
    Node
x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

3.3 add methods

add(E e) appends at the tail in constant time using the last reference.

public boolean add(E e) {
    linkLast(e);
    return true;
}

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

add(int index, E element) inserts at a specific position after locating the node.

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

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

3.4 remove methods

Both remove(int index) and remove(Object o) locate the target node and delegate to unlink(Node<E> x) .

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

public boolean remove(Object o) {
    if (o == null) {
        for (Node
x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node
x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node
x) {
    final E element = x.item;
    final Node
next = x.next;
    final Node
prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

04. Vector

Vector is a legacy class introduced in JDK 1.0; it implements List and adds thread safety by synchronizing its methods.

4.1 get method

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

4.2 set method

public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

4.3 add method

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

4.4 remove method

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

05. Stack

Stack represents a LIFO structure and extends Vector . Its typical operations are push , peek , and pop .

5.1 push

public E push(E item) {
    addElement(item);
    return item;
}

5.2 peek

public synchronized E peek() {
    int len = size();
    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

5.3 pop

public synchronized E pop() {
    E obj;
    int len = size();
    obj = peek();
    removeElementAt(len - 1);
    return obj;
}

06. Summary

ArrayList : dynamic array, fast random access, slower insert/delete except at the end.

LinkedList : doubly‑linked list, slower random access, fast insert/delete anywhere.

Vector : synchronized dynamic array, generally slower than ArrayList ; rarely used in new code.

Stack : extends Vector , LIFO; modern code prefers ArrayDeque from the Deque hierarchy.

07. References

1. JDK 1.7 & JDK 1.8 source code

2. CarpenterLee – Java collection analysis

3. Blog园 – Comparison of ArrayList, LinkedList, Vector, Stack

--- Promotional content omitted in the academic summary.