Skip to main content

5.2 List Implementations: ArrayList vs LinkedList vs Vector

← Back to Chapter 5: Collections Framework

A List is an ordered collection allowing duplicates and positional index access.

1. ArrayList: Dynamic Resizable Array​

An ArrayList<E> encapsulates an internal contiguous array Object[] elementData.

Internal Growth Policy (Java 8–21)​

  • Default initial capacity: 10 (lazily allocated upon first add()).
  • Growth factor: newCapacity = oldCapacity + (oldCapacity >> 1) (1.5x growth).
  • Array resizing copies existing elements to a newly allocated array using intrinsic native call System.arraycopy().
List<String> list = new ArrayList<>(100); // Pre-size to eliminate rehashing
list.add("Java");
list.add("Spring");
String item = list.get(0); // O(1) random pointer arithmetic

2. LinkedList: Doubly-Linked List​

A LinkedList<E> consists of independent Node<E> objects scattered across the heap:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Memory Overhead & CPU Cache Locality​

  • Each node creates 24–32 bytes of heap overhead (object header + 2 reference pointers).
  • Lacks CPU cache spatial locality compared to ArrayList, causing L1/L2 cache misses during traversal.
  • ArrayList virtually always outperforms LinkedList in practical production environments even for element insertions.

3. Vector and Stack: Legacy Synchronization​

  • Vector<E>: Every method is synchronized with method-level intrinsic monitor locks (synchronized). Obsolete since Java 2.
  • Stack<E>: Extends Vector, inheriting synchronous overhead and violating encapsulation (allows inserting at arbitrary indexes via add(index, element)).
  • Modern Recommendation: Use ArrayList for non-thread-safe lists, ArrayDeque for LIFO stack operations, and CopyOnWriteArrayList for thread-safe read-heavy iteration.