[Advanced Java] ArrayList vs LinkedList vs Vector: Comparing List Implementations

Part 1 of this course was about the language and how to design with it. Part 2 turns to the library you design against: the Collection Framework, in depth. It opens here with the three List implementations in java.util, continues into sets and maps, then queues, deques and iteration.

This article is titled as a performance comparison, and it publishes no milliseconds. That is a deliberate choice, explained in full in the second section: a hand-rolled Java microbenchmark is usually wrong, and a wrong number in a tutorial is worse than no number. Everything below is built from structure instead: byte counts read out of a live JVM, operation counts produced by instrumented code, and the marker interface the JDK itself branches on.

Every number, output line and disassembly below was produced on OpenJDK 21.0.6 for arm64. The everyday List API is assumed; this is the second pass, about what each implementation costs.

Three implementations of one interface

All three store an ordered sequence and all three implement List. What they do underneath is not the same, and the runtime will tell you so:

import java.util.*;

public class Shape {
    static void show(Class<?> c) {
        StringBuilder sb = new StringBuilder(c.getSimpleName() + " -> ");
        for (Class<?> i : c.getInterfaces()) sb.append(i.getSimpleName()).append(" ");
        Class<?> sup = c.getSuperclass();
        if (sup != null) sb.append("| extends ").append(sup.getSimpleName());
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args) {
        show(ArrayList.class);
        show(LinkedList.class);
        show(Vector.class);
        show(Stack.class);
        show(java.util.concurrent.CopyOnWriteArrayList.class);
    }
}

ArrayList -> List RandomAccess Cloneable Serializable | extends AbstractList
LinkedList -> List Deque Cloneable Serializable | extends AbstractSequentialList
Vector -> List RandomAccess Cloneable Serializable | extends AbstractList
Stack -> | extends Vector
CopyOnWriteArrayList -> List RandomAccess Cloneable Serializable | extends Object

Three facts fall out of five lines. Vector has the same shape as ArrayList - an array-backed List that implements RandomAccess. LinkedList implements Deque instead of RandomAccess, which is the whole comparison in one line. And Stack extends Vector, which is why Stack inherits every problem in this article; it is a legacy class and article 10 of this course covers it properly alongside Deque.

Every row in that table is verified further down by running something.

Why this article publishes no milliseconds

There are two reasons, and the second is the one worth your attention.

The first is local: this machine is running several jobs in parallel while these programs execute, so any elapsed time measured here is inflated noise. That is a reason not to trust these numbers.

The second is general, and it is a reason not to trust most published Java numbers. A microbenchmark written as a for loop around System.nanoTime() measures the JVM's compilation state at least as much as it measures your code. Four mechanisms conspire against it:

Tiered compilation. Your method starts interpreted, gets compiled by C1, then by C2, and the earlier versions are thrown away mid-run. -XX:+PrintCompilation shows it happening to an ordinary indexed loop over an ArrayList:

12   14       3       java.util.ArrayList::get (15 bytes)
12   17       4       java.util.ArrayList::get (15 bytes)
12   14       3       java.util.ArrayList::get (15 bytes)   made not entrant
13   18 %     3       Warmup::sum @ 4 (38 bytes)
14   19       3       Warmup::sum (38 bytes)
14   20 %     4       Warmup::sum @ 4 (38 bytes)
15   18 %     3       Warmup::sum @ 4 (38 bytes)   made not entrant
15   21       4       Warmup::sum (38 bytes)
16   19       3       Warmup::sum (38 bytes)   made not entrant

The first column is a millisecond timestamp of the compilation event, not a measurement of anything the list does. The column that matters is the tier: 3 is C1, 4 is C2. ArrayList::get is compiled twice and the first version is discarded; Warmup::sum is compiled four times. A benchmark that starts its stopwatch before this settles is timing the interpreter.

On-stack replacement. The % on three of those lines marks an OSR compilation: the JVM replaced the method while a loop inside it was still running, because the loop was hot before the method had been called often enough. OSR code is compiled under different assumptions from a normal compilation, so a benchmark whose work sits in one long loop can measure a version of the code that never runs in production.

Dead-code elimination. If a loop computes a result nothing reads, C2 is entitled to delete the loop. The classic symptom is a benchmark that reports an impossibly small time and gets faster when you add work to it.

Allocation and the collector. LinkedList allocates one object per element and ArrayList allocates in bursts, so any comparison between them is partly a comparison of garbage collectors, of heap size, and of whether a collection happened to land inside the measured window.

This is exactly why JMH exists. It is the OpenJDK's own benchmark harness, and its whole design is a list of these traps: @Warmup and @Measurement separate the warm-up iterations from the measured ones, @Fork runs each benchmark in a fresh JVM so one benchmark cannot poison another's profile, @State keeps the input out of the timed code, Blackhole consumes results so they cannot be optimised away, and -prof gc reports allocation rate next to the time so you can see when you are measuring the collector.

A correct comparison of these three classes would have to control for all of it: warm-up to steady state, a fresh JVM per case, inputs built outside the measured region, results consumed, a fixed heap and collector, several forks to expose run-to-run variance, and error bars reported rather than a single number. That is a serious piece of work, and its output is still specific to one machine and one JDK build.

So this article uses evidence that does not move when the machine is busy:

• counts - how many element copies, pointer hops and allocations one call performs, measured by instrumented code that reproduces the JDK's own algorithms;
• bytes - the real per-element memory cost, read out of the running JVM through field offsets and confirmed by a heap measurement;
• structure - what the JDK's own source does differently for one implementation and not the other.

Where structure decides the answer, it says so. Where only a benchmark could decide, it says that too.

What one element costs in memory

The single most reliable statement about these classes is a memory statement, and it can be derived exactly rather than estimated. Unsafe reports the field offsets the JVM actually chose:

import java.lang.reflect.Field;

public class Layout {
    public static void main(String[] args) throws Exception {
        Field theUnsafe = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafe.setAccessible(true);
        sun.misc.Unsafe u = (sun.misc.Unsafe) theUnsafe.get(null);

        Class<?> node = Class.forName("java.util.LinkedList$Node");
        for (Field f : node.getDeclaredFields())
            System.out.printf("  %-6s %-8s offset %d%n",
                    f.getName(), f.getType().getSimpleName(), u.objectFieldOffset(f));

        System.out.println("arrayBaseOffset(Object[]) = " + u.arrayBaseOffset(Object[].class));
        System.out.println("arrayIndexScale(Object[]) = " + u.arrayIndexScale(Object[].class));
    }
}

  item   Object   offset 12
  next   Node     offset 16
  prev   Node     offset 20
arrayBaseOffset(Object[]) = 16
arrayIndexScale(Object[]) = 4

That is the whole derivation. The first field of a Node sits at offset 12, so the object header is 12 bytes. Each of the three references occupies 4 bytes, because this JVM runs with UseCompressedOops enabled - confirmed with java -XX:+PrintFlagsFinal -version. The last byte used is 23, and ObjectAlignmentInBytes is 8, so a Node is exactly 24 bytes. An Object[] has a 16-byte header and 4 bytes per slot, so an element in an ArrayList costs 4 bytes plus a share of the array header.

A heap measurement agrees to the byte. Both lists are filled from the same array of Integer objects, so only the list structure is counted:

import java.util.*;

public class Footprint {
    static Object keepAlive;
    static long used() {
        Runtime r = Runtime.getRuntime();
        for (int i = 0; i < 8; i++) { System.gc(); try { Thread.sleep(80); } catch (Exception e) {} }
        return r.totalMemory() - r.freeMemory();
    }

    public static void main(String[] args) {
        int n = 2_000_000;
        Integer[] shared = new Integer[n];
        for (int i = 0; i < n; i++) shared[i] = Integer.valueOf(i);
        keepAlive = shared;

        long b1 = used();
        List<Integer> al = new ArrayList<>(n);
        for (int i = 0; i < n; i++) al.add(shared[i]);
        keepAlive = new Object[]{shared, al};
        long a1 = used();

        long b2 = used();
        List<Integer> ll = new LinkedList<>();
        for (int i = 0; i < n; i++) ll.add(shared[i]);
        keepAlive = new Object[]{shared, al, ll};
        long a2 = used();

        System.out.printf("  ArrayList  structure = %,d bytes = %.2f bytes per element%n",
                a1 - b1, (a1 - b1) / (double) n);
        System.out.printf("  LinkedList structure = %,d bytes = %.2f bytes per element%n",
                a2 - b2, (a2 - b2) / (double) n);
    }
}

  ArrayList  structure = 8,000,176 bytes = 4.00 bytes per element
  LinkedList structure = 48,000,544 bytes = 24.00 bytes per element

Six times the memory, and identical across repeated runs. The keepAlive field is not decoration: without it the JVM is free to collect shared while the last measurement is being taken, and the LinkedList figure comes out 4 bytes per element too low.

Two honest qualifications. This ArrayList was constructed with its final size, so it carries no spare capacity; a list grown by repeated add ends up with some. Building 100,000 elements without a size hint leaves a capacity of 106,710, so 6.7% slack, taking the real figure to about 4.27 bytes an element. And both figures exclude the elements themselves, which are shared here and identical in both cases.

This is where the cache-locality argument comes from, and it is structural rather than measured. A cache line on a modern CPU is 64 bytes. Sixteen consecutive ArrayList references fit in one line, so walking the list touches memory the prefetcher can predict. A LinkedList walk follows next from one 24-byte object to another wherever the allocator put it, and each hop is a dependent load: the address of the next node is not known until the current one has arrived. That is the real reason ArrayList usually wins in practice, and it is an argument about layout, not a stopwatch reading.

Counting the work: copies, hops and allocations

Operation counts are reproducible on any machine under any load. The counts below come from a program that replays the JDK's own code with counters attached - System.arraycopy of size - index references for ArrayList.add(int, E), of size - 1 - index for remove(int), and for LinkedList the same node(int) walk that starts from whichever end is nearer:

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

The replay is checked against the real classes before anything is counted: the same sequence of add, add(int, E) and remove(int) calls is applied to both, and the resulting contents compared.

replay matches ArrayList : true
replay matches LinkedList: true

On a list of 100,000 elements, one call costs this much:

Read the middle rows carefully, because they are the ones the usual advice gets wrong. Removing from the middle costs LinkedList exactly the same count as ArrayList: 49,999 either way. LinkedList spends it walking instead of copying, and a walk is the more expensive of the two - System.arraycopy is one bulk move over contiguous memory, while 49,999 pointer hops are 49,999 dependent loads across separately allocated objects. Equal on the counter, not equal on the hardware.

Where LinkedList wins outright is the head. add(0, e) and remove(0) cost it nothing at all, while ArrayList moves the entire array. Where it wins nothing at all is the tail, because appending to an ArrayList is already free most of the time.

Indexed reads are the other half of the picture. LinkedList.get(i) starts from the nearer end, which halves the worst case without changing its shape:

LinkedList.get(i) pointer hops, size 100000
  get(0     ) = 0 hops
  get(1     ) = 1 hops
  get(25000 ) = 25000 hops
  get(49999 ) = 49999 hops
  get(50000 ) = 49999 hops
  get(75000 ) = 24999 hops
  get(99998 ) = 1 hops
  get(99999 ) = 0 hops

⚠️ Reading a whole list with for (int i = 0; i < list.size(); i++) list.get(i) costs an ArrayList 100,000 array reads and a LinkedList 2,499,950,000 pointer hops. The indexed loop is linear on one and quadratic on the other. The enhanced for loop is linear on both, because the iterator keeps its position instead of re-walking from an end.

Allocation is the last axis, and it is the one where the two classes differ most in character:

building 100000 elements with add(e)
  ArrayList : 24 array allocations, 320123 slots allocated in total, 213413 references copied
  LinkedList: 100000 Node allocations, 0 references copied

ArrayList allocates 24 times while growing to 100,000, copying about 2.13 references per element in total across the whole build - that is what "amortised constant time" means in practice. LinkedList never copies anything and never reallocates, and pays for it with 100,000 separate object allocations, each of which is 24 bytes of live heap the collector has to trace.

RandomAccess: the marker the JDK actually branches on

RandomAccess has no methods. Its entire content is its javadoc, which states the rule of thumb precisely: a List should implement it if, for typical instances, an indexed loop runs faster than an iterator loop. ArrayList and Vector implement it, LinkedList does not:

ArrayList            instanceof RandomAccess : true
Vector               instanceof RandomAccess : true
LinkedList           instanceof RandomAccess : false
List.of(1, 2)        instanceof RandomAccess : true
Arrays.asList(1, 2)  instanceof RandomAccess : true

This is not documentation. java.util.Collections mentions RandomAccess sixteen times: ten of those choose between an indexed algorithm and an iterator-driven one, and the other six choose which wrapper class to hand back. The difference is observable. The test below wraps the same 10,000 elements in two delegating lists whose class bodies are identical - the only difference is that one implements the marker - and counts how the JDK reaches the elements:

static class Counting extends AbstractList<Integer> {
    final List<Integer> delegate;
    int getCalls, setCalls, iteratorCalls, toArrayCalls;
    Counting(List<Integer> d) { delegate = d; }
    public Integer get(int i) { getCalls++; return delegate.get(i); }
    public Integer set(int i, Integer v) { setCalls++; return delegate.set(i, v); }
    public int size() { return delegate.size(); }
    public ListIterator<Integer> listIterator() { iteratorCalls++; return delegate.listIterator(); }
    public ListIterator<Integer> listIterator(int i) { iteratorCalls++; return delegate.listIterator(i); }
    public Object[] toArray() { toArrayCalls++; return delegate.toArray(); }
}

/** Identical class body. The only difference is the marker interface. */
static class CountingRA extends Counting implements RandomAccess {
    CountingRA(List<Integer> d) { super(d); }
}

Collections.binarySearch
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=0
  RandomAccess get(i)=13     set(i,e)=0      listIterator()=0  toArray()=0
Collections.shuffle
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=1
  RandomAccess get(i)=9999   set(i,e)=19998  listIterator()=0  toArray()=0
Collections.fill
  plain List   get(i)=0      set(i,e)=0      listIterator()=1  toArray()=0
  RandomAccess get(i)=0      set(i,e)=10000  listIterator()=0  toArray()=0

Two completely different algorithms, chosen by an instanceof check. The marked list gets a binary search that jumps to 13 indices; the unmarked one gets a search driven by a ListIterator. The marked list gets an in-place Fisher-Yates shuffle over indices; the unmarked one gets copied to an array, shuffled there, and written back through an iterator - which is the JDK protecting a linked list from 10,000 walks.

The source is a one-line branch, repeated with different thresholds:

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

The practical consequence is for code you write. If you accept a List parameter and reach elements by index in a loop, you have written an algorithm that is quadratic on half the implementations that could be passed to you. The JDK's answer is either to check instanceof RandomAccess and take a different path, or to use an iterator and be linear everywhere.

When LinkedList genuinely wins

There are two cases, and both are narrower than the folklore.

You already hold the position. LinkedList's cheap insert requires a cursor, not an index. If your code says list.add(i, x), the walk is back, because the walk is how the cursor is found. If it says it.add(x) on a ListIterator you are already carrying, there is no walk at all. Inserting a separator before every element of a 20,000-element list, three ways:

ArrayList,  by index          :     400,052,697 element copies
LinkedList, by index          :     133,320,000 pointer hops
LinkedList, at a held cursor  :               0 pointer hops
all three produced 40000 / 40000 / 40000 elements

Zero. Not "fewer" - zero. Both other approaches do hundreds of millions of units of work to achieve the same result. That is the case LinkedList was designed for, and it is entirely invisible to code that reaches elements by index:

LinkedList<String> real = new LinkedList<>(List.of("a", "b", "c"));
for (ListIterator<String> it = real.listIterator(); it.hasNext(); ) {
    it.next();
    it.add("-");
}
System.out.println(real);

[a, -, b, -, c, -]

The same loop on an ArrayList produces the same list and does not save anything, because ArrayList's ListIterator.add still shifts the tail of the array. Holding a cursor helps the implementation that stores positions as objects; it does nothing for the one that stores positions as offsets.

You are working at both ends. LinkedList implements Deque, so addFirst, addLast, removeFirst and removeLast are all a couple of pointer assignments with no shifting and no reallocation, ever. Article 10 of this course covers Deque and its implementations properly, including the array-backed alternative that is usually the better choice when you do not also need List.

Everything else that gets attributed to LinkedList does not survive the counting. It does not save memory - it uses six times as much per element. It does not make removal cheap in general - only removal at a position you already hold. And it does not make contains or indexOf any faster; both are linear scans on either class.

ensureCapacity and trimToSize

ArrayList exposes two methods that touch the backing array directly, and reflection makes their effect visible:

new ArrayList<>()            size=0 capacity=0
  ensureCapacity(8)          size=0 capacity=0
  ensureCapacity(11)         size=0 capacity=11
new + ensureCapacity(1000)   size=0 capacity=1000
  after 1000 adds            size=1000 capacity=1000
  add #1001                  size=1001 capacity=1500
1000 adds, no hint           size=1000 capacity=1234
  trimToSize()               size=1000 capacity=1000
  clear()                    size=0 capacity=1000
  trimToSize()               size=0 capacity=0
  add after trim             size=1 capacity=1

Four things in that trace are worth knowing.

ensureCapacity(8) did nothing. On a list still holding the shared default-capacity array, the JDK ignores any request up to 10, because the first add would allocate 10 anyway:

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

ensureCapacity(1000) allocated exactly 1000 slots, and the 1001st add grew it to 1500 - the ordinary 1.5x rule takes over once a real array exists. A size hint prevents the growth sequence; it does not change the policy afterwards.

clear() does not release the array. Capacity stayed at 1000 with size 0, which is the right default - a list you emptied is a list you are probably about to refill - but it means a long-lived ArrayList that once held a million elements still holds a million slots.

trimToSize() on an empty list gives the array back completely, and the next add then allocates one slot rather than ten. That is not a bug; trimToSize swaps in EMPTY_ELEMENTDATA, which is a different sentinel from the DEFAULTCAPACITY_EMPTY_ELEMENTDATA that a fresh list carries, and only the latter triggers the default of 10.

Vector has both methods too, plus a public capacity() that ArrayList deliberately does not expose. Needing to read the capacity of a list is almost always a sign that the abstraction has leaked.

Vector: every call locked, and what that does not buy

Vector predates the Collection Framework - it shipped in Java 1.0 and was retrofitted onto List in 1.2. Its own javadoc says what to do about that:

As of the Java 2 platform v1.2, this class was retrofitted to implement the List
interface, making it a member of the Java Collections Framework. Unlike the new
collection implementations, Vector is synchronized. If a thread-safe
implementation is not needed, it is recommended to use ArrayList in place of
Vector.

The synchronization is real and it is thorough. Counting the modifiers with reflection:

Vector                 public instance methods = 49  synchronized = 38
ArrayList              public instance methods = 38  synchronized = 0
CopyOnWriteArrayList   public instance methods = 43  synchronized = 0

The eleven that are not marked are not gaps. javap shows the pattern, abridged to the interesting rows:

  public synchronized int size();
  public synchronized boolean isEmpty();
  public boolean contains(java.lang.Object);
  public int indexOf(java.lang.Object);
  public synchronized E get(int);
  public synchronized E set(int, E);
  public synchronized boolean add(E);
  public boolean remove(java.lang.Object);
  public void add(int, E);
  public synchronized E remove(int);
  public void clear();

Each of the unmarked ones delegates to a marked one - contains(o) is indexOf(o, 0) >= 0, add(int, E) is insertElementAt, clear() is removeAllElements() - or takes the monitor with an explicit synchronized (this) block, as addAll(Collection) does. Every public operation on a Vector is guarded.

What that guarantee actually is

One call on a Vector is atomic with respect to other calls on the same Vector, and it publishes its writes to whoever calls next. That is genuinely useful and it is genuinely all you get. It does not extend to two calls, and almost nothing you want to do is one call.

The canonical example is check-then-act:

static void addIfAbsent(Vector<String> v, String s) {
    if (!v.contains(s)) {
        v.add(s);
    }
}

contains takes the lock, answers, and releases it. add takes the lock, appends, and releases it. Between the two there is a moment where nobody holds anything. The compiler makes this completely explicit:

static void addIfAbsent(java.util.Vector<java.lang.String>, java.lang.String);
    Code:
       0: aload_0
       1: aload_1
       2: invokevirtual #7    // Method java/util/Vector.contains:(Ljava/lang/Object;)Z
       5: ifne          14
       8: aload_0
       9: aload_1
      10: invokevirtual #13   // Method java/util/Vector.add:(Ljava/lang/Object;)Z
      13: pop
      14: return

There is no monitorenter in that method and no monitorexit. The locking all happens inside the callees, which is exactly the problem: the sequence is unguarded. Taking the lock yourself changes the bytecode:

static void addIfAbsent(Vector<String> v, String s) {
    synchronized (v) {
        if (!v.contains(s)) {
            v.add(s);
        }
    }
}

       0: aload_0
       1: dup
       2: astore_2
       3: monitorenter
       4: aload_0
       5: aload_1
       6: invokevirtual #7    // Method java/util/Vector.contains:(Ljava/lang/Object;)Z
       9: ifne          18
      12: aload_0
      13: aload_1
      14: invokevirtual #13   // Method java/util/Vector.add:(Ljava/lang/Object;)Z
      17: pop
      18: aload_2
      19: monitorexit
      20: goto          28
      23: astore_3
      24: aload_2
      25: monitorexit
      26: aload_3
      27: athrow
      28: return

monitorenter at 3, monitorexit at 19 on the normal path and again at 25 on the exception path. Now the pair is one operation. Note what this means: the moment you need a compound operation, you write the same synchronized block you would have written around an ArrayList, and Vector's own locking becomes redundant work performed inside a lock you are already holding.

That is the false comfort. Vector in a declaration reads like a decision about correctness, and it decides much less than it appears to.

And the cost

Locking is not free. Every call pays for a monitor acquire and release even in a program with one thread, and a synchronized method is a harder target for the JIT than a plain one. How much that costs in a given program is exactly the sort of question this article refuses to answer with a fabricated number - it depends on inlining, on lock elision, on the JVM, and it would need a proper JMH benchmark to answer honestly. What can be said without measuring is that the cost is paid on every call, and in a single-threaded program it buys nothing at all.

Vector's growth policy against ArrayList's

Both classes grow through the same helper, and pass it a different preference. ArrayList:

int oldCapacity = elementData.length;
int newCapacity = ArraysSupport.newLength(oldCapacity,
        minCapacity - oldCapacity, /* minimum growth */
        oldCapacity >> 1           /* preferred growth */);

Vector:

int oldCapacity = elementData.length;
int newCapacity = ArraysSupport.newLength(oldCapacity,
        minCapacity - oldCapacity, /* minimum growth */
        capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                   /* preferred growth */);

oldCapacity >> 1 is half, so ArrayList grows by 1.5x. oldCapacity is the whole thing, so Vector doubles - unless you passed a capacityIncrement to the constructor, in which case it grows by that fixed number of slots. Reading elementData out of both after every add shows all three policies:

ArrayList capacity        : 0, 10, 15, 22, 33, 49, 73, 109, 163, 244, 366
Vector capacity           : 10, 20, 40, 80, 160, 320
Vector(10, 25) capacity   : 10, 35, 60, 85, 110, 135, 160, 185, 210, 235, 260, 285, 310
Vector(1) capacity        : 1, 2, 4, 8, 16, 32, 64
ArrayList(1) capacity     : 1, 2, 3, 4, 6, 9, 13, 19, 28, 42

The first two lines also show a difference at index zero. A new ArrayList starts at capacity 0 - it shares a static empty array and allocates nothing until the first add. A new Vector allocates ten slots in the constructor whether you use them or not.

Doubling versus a half is a real trade, and it goes both ways:

building 100000 elements with add(e)
  ArrayList  grows=24  references copied=213413  copies/element=2.13  final capacity=106710  slack=6710
  Vector     grows=14  references copied=163830  copies/element=1.64  final capacity=163840  slack=63840
  new ArrayList<>(100000)  grows=0  references copied=0

Vector reallocates ten fewer times and copies 50,000 fewer references - and ends up holding 63,840 unused slots against ArrayList's 6,710. Doubling buys fewer copies with wasted memory; 1.5x buys tighter memory with more copies. Neither is wrong, and ArrayList's choice is the better default because the copies are a bulk memory move while the waste is permanent.

capacityIncrement is the option to avoid. A fixed increment turns geometric growth into linear growth, and the total copying becomes quadratic:

Vector(10, 0    ) grows=14     references copied=        163,830 final capacity=163840
Vector(10, 100  ) grows=1000   references copied=     49,960,000 final capacity=100010
Vector(10, 1000 ) grows=100    references copied=      4,951,000 final capacity=100010

Three hundred times the copying to save 63,830 slots. The tight final capacity looks appealing until you see the price; if you want a tight array, size the list correctly at construction or call trimToSize() at the end.

What to use instead of Vector

Nothing about Vector is unfixable - it is just that every reason to reach for it has a better answer now.

Collections.synchronizedList is Vector's locking applied to a list of your choosing, and it keeps the marker interface when it can:

synchronizedList class       : java.util.Collections$SynchronizedRandomAccessList
synchronizedList(LinkedList) : java.util.Collections$SynchronizedList
synchronizedList RandomAccess: true
its iterator class           : java.util.ArrayList$Itr

Look at the last line. The wrapper's iterator() returns the underlying list's iterator, which is not synchronized at all - and its javadoc says so in as many words:

It is imperative that the user manually synchronize on the returned list when
traversing it via Iterator, Spliterator or Stream:

 List list = Collections.synchronizedList(new ArrayList());
     ...
 synchronized (list) {
     Iterator i = list.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
 }

Which is the same conclusion as before: per-call locking never covers a sequence, whether it comes from Vector or from a wrapper.

CopyOnWriteArrayList takes the opposite approach, and its cost is easy to demonstrate. Its private array field is replaced on every single write:

  add(0) -> array length 1, same array object as before: false
  add(1) -> array length 2, same array object as before: false
  ...
  add(9) -> array length 10, same array object as before: false
array replaced 10 times in 10 adds

Ten adds, ten fresh arrays, no spare capacity ever. Its javadoc is blunt about when that is acceptable - "ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations". A listener registry read on every event and written twice at startup is the shape it fits; a list you append to in a loop is not.

Vector's iterators are fail-fast in the same way ArrayList's are, which article 11 of this course covers in detail. It is worth noting only because "synchronized" and "safe to iterate while another thread modifies it" are different claims, and Vector makes only the first.

Choosing between the three

The rule is short, and none of it depends on a stopwatch.

• Use ArrayList. It is the right default for essentially all list code: 4 bytes an element, contiguous storage, free indexed access, amortised free append, and no locking you did not ask for.
• Use LinkedList only when you hold a cursor or work at both ends. A ListIterator parked where you want to edit, or a queue consumed from the front and appended at the back. If your code contains list.get(i) or list.add(i, x), you do not hold a cursor and the case does not apply.
• Do not use Vector in new code. Every reason to choose it is better served by ArrayList with a synchronized block you control, Collections.synchronizedList, or CopyOnWriteArrayList - and the first of those is what you end up writing anyway as soon as you need two operations to happen together.
• Size the list when you know the size. new ArrayList<>(n) removes the entire growth sequence for the cost of one integer.
• If you genuinely need a timing, measure it with JMH, on a quiet machine, on the JDK you deploy, with the data you actually hold. Do not trust a table of milliseconds in an article - including one you might have expected to find in this one.

FAQ

Is LinkedList really faster for insertion and deletion?

Only at a position you already hold. Counted on a list of 100,000, removing from the middle costs LinkedList 49,999 pointer hops and ArrayList 49,999 element copies - the same number, spent on the more expensive kind of work in LinkedList's case, because a chain of dependent loads across the heap is slower than one bulk arraycopy over contiguous memory. LinkedList wins outright only at the head, and wins spectacularly when the position comes from a ListIterator rather than an index: 0 hops against 133,320,000 for the same job.

How much more memory does LinkedList use?

Six times as much for the list structure, measured two independent ways on OpenJDK 21 with compressed oops. Each LinkedList$Node is 24 bytes - a 12-byte object header plus item, next and prev at 4 bytes each - against 4 bytes for one slot of an Object[]. A heap measurement over 2,000,000 elements agrees exactly: 48,000,544 bytes against 8,000,176.

Is Vector thread-safe?

Each individual method call is, and that is the whole guarantee. A sequence of calls is not, so if (!v.contains(x)) v.add(x) is not safe no matter how synchronized the two methods are - the bytecode has no monitor instruction between them. Any compound operation needs a synchronized block of your own, and once you are writing that block, Vector's locking is redundant.

Should I use Vector for anything in new code?

No. Its own javadoc recommends ArrayList when thread safety is not needed, and when it is needed, Collections.synchronizedList gives the identical per-call guarantee on any list, while CopyOnWriteArrayList gives a stronger one for read-dominated cases. Vector also doubles its capacity where ArrayList grows by half, so it holds 63,840 spare slots after 100,000 appends against ArrayList's 6,710. Existing code that uses it is fine; new code has better options.

Does ensureCapacity actually make a difference?

It removes the growth sequence, which is real but bounded. Building 100,000 elements without a hint costs 24 array allocations and 213,413 copied references, about 2.13 per element; new ArrayList<>(100000) costs zero of both. Worth doing when you know the size, not worth guessing at. Note that ensureCapacity(n) for any n up to 10 on a fresh list does nothing at all, by design.

Why does my ArrayList keep its memory after clear()?

Because clear() only nulls the slots and resets size; the array itself stays. A list that once held a million elements still owns a million-slot array afterwards. trimToSize() is the only thing that gives it back, and on an empty list it releases the array entirely - after which the next add allocates a single slot rather than the usual ten, because the sentinel array it swapped in is not the one that triggers the default capacity.

Conclusion

The three implementations divide cleanly once you stop asking which is fastest and start asking what each one stores. ArrayList keeps one reference per element in a shared array: 4 bytes each, contiguous, indexed access for free, appends amortised over 24 reallocations per 100,000 elements. LinkedList keeps a 24-byte Node per element: no shifting and no reallocation ever, at the price of six times the memory, an allocation per element, and a walk for every position that is not an end. Vector is ArrayList from 1996 with a monitor around every call and a doubling growth policy, and the monitor guards one call at a time - which is never the granularity a real program needs.

None of that required a stopwatch, which is the point. Field offsets, operation counts, an instanceof check inside Collections, and the presence or absence of monitorenter in the bytecode are all reproducible on any machine, under any load, on any build. A microbenchmark is not, which is why JMH exists and why the honest version of this comparison publishes counts instead of milliseconds.

Article 8 leaves ordered positions behind for membership: Set and its three implementations - HashSet, LinkedHashSet and TreeSet - what each one does about ordering, and what it costs to ask whether a value is already there.