Collections

63. List Implementations Compared

ArrayList is the default general-purpose list (O(1) random access); LinkedList is a doubly-linked list (O(1) insert/remove at ends, O(n) access); Vector is legacy and synchronised — avoid it.

Java 21 (core language)

Explanation

ArrayList backed by a resizable array: get(i) is O(1), add(last) is amortised O(1), add(middle) is O(n) (shifts elements), remove(middle) is O(n). Default initial capacity: 10. Grows by 50% when full.

LinkedList is a doubly-linked list: getFirst()/getLast() are O(1), get(i) is O(n) (traversal), add/remove at known positions (via iterator) are O(1), but you pay a pointer overhead of ~40 bytes per node (vs ~8 bytes per reference in an ArrayList). Implements both List and Deque.

In practice, ArrayList outperforms LinkedList in most scenarios — even sequential traversal — due to CPU cache locality (array elements are contiguous in memory; linked nodes are scattered). Only prefer LinkedList if you exclusively add/remove from the head or tail and rarely access by index.

Vector is like ArrayList but every method is synchronized. It's a legacy class from Java 1.0 — do not use. If you need a synchronised list, use Collections.synchronizedList(new ArrayList<>()) or CopyOnWriteArrayList.

Example

import java.util.*;

public class ListImplementations {
    public static void main(String[] args) {
        // ArrayList: best for random access and most general use
        List<String> arrayList = new ArrayList<>();
        arrayList.add("a"); arrayList.add("b"); arrayList.add("c");
        System.out.println("get(1): "  + arrayList.get(1)); // O(1)
        arrayList.add(1, "x");                               // O(n) shift
        System.out.println("After insert: " + arrayList);

        // Pre-size to avoid reallocation
        List<Integer> presized = new ArrayList<>(1000);
        for (int i = 0; i < 1000; i++) presized.add(i);

        // LinkedList: efficient head/tail ops, poor random access
        LinkedList<String> linked = new LinkedList<>();
        linked.addFirst("start"); linked.addLast("end");
        linked.add(1, "middle");
        System.out.println("Linked: " + linked);
        System.out.println("First: " + linked.getFirst()); // O(1)
        System.out.println("Get(1): " + linked.get(1));    // O(n)!

        // LinkedList as Deque (double-ended queue)
        Deque<String> deque = new LinkedList<>();
        deque.offerFirst("head");
        deque.offerLast("tail");
        System.out.println("Deque: " + deque);

        // Performance comparison: ArrayList wins for indexed access
        int N = 10_000;
        List<Integer> al = new ArrayList<>(N);
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < N; i++) { al.add(i); ll.add(i); }

        long t1 = System.nanoTime();
        for (int i = 0; i < N; i++) al.get(i);
        long t2 = System.nanoTime();
        for (int i = 0; i < N; i++) ll.get(i);
        long t3 = System.nanoTime();

        System.out.printf("ArrayList get: %d ns, LinkedList get: %d ns%n", t2-t1, t3-t2);
    }
}

Sources