List: ArrayList & LinkedList

ArrayList is backed by a dynamic array with O(1) get and cache-friendly memory layout; LinkedList is a doubly-linked list with O(1) add/remove at the ends but O(n) random access. Use ArrayList as the default.

ArrayList uses an Object[] array that starts at capacity 10 and grows by 1.5x when full, copying all elements to a new array each time it resizes.

ArrayList expands when size equals capacity: it creates a new array at 1.5x the old capacity and copies all elements, giving amortized O(1) add performance.

LinkedList is a doubly-linked list where each Node holds the element, a reference to the previous node, and a reference to the next node, with head and tail pointers for O(1) operations at both ends.

Use ArrayList as the default; use LinkedList only when you need O(1) insert/remove at the current ListIterator position during traversal, and never for random access or queue/stack operations.

Vector is a legacy synchronized ArrayList from Java 1.0 that locks every method and grows by 2x; use ArrayList for single-threaded code and ConcurrentHashMap patterns for multi-threaded code instead.

subList(fromIndex, toIndex) returns a view into the parent list, not a copy; writes propagate both ways, and structural changes to the parent invalidate the sublist with ConcurrentModificationException.