ArrayList vs LinkedList
ArrayList is backed by a dynamic array — O(1) random access, O(n) insertion/removal in the middle. LinkedList is a doubly-linked list — O(n) random access (no index), O(1) insertion/removal at a known node.
ArrayList = a bookshelf with numbered slots (instant access by position). LinkedList = a treasure hunt where each clue points to the next. Fast to insert a clue mid-chain, but finding clue #50 means following 49 clues first.
In practice, ArrayList outperforms LinkedList for most workloads due to cache locality — array elements are contiguous in memory, enabling CPU prefetching. LinkedList nodes are scattered in heap; each node traversal is a pointer dereference that likely causes a cache miss. LinkedList wins only when you have a persistent iterator positioned at the insertion point and perform frequent insertions at that position. LinkedList implements Deque and can be used as a stack or queue. ArrayList.add() is amortized O(1) — occasionally triggers a resize (new array at 1.5x capacity, copy all elements).
Modern hardware makes LinkedList's theoretical O(1) insert advantage largely irrelevant for small to medium lists because cache misses dominate. Memory overhead: each LinkedList node adds 24 bytes of object overhead (prev pointer, next pointer, object header) vs ArrayList's 4 bytes per reference. ArrayDeque is preferred over LinkedList as a queue/deque — it's backed by a resizable circular array and avoids per-element allocation overhead. For high-throughput queues, consider Disruptor's ring buffer (lock-free, cache-friendly).
In theory LinkedList has O(1) insert/remove at known positions vs ArrayList's O(n). In practice ArrayList almost always wins due to cache locality — contiguous array memory is prefetched efficiently by CPUs, while LinkedList's scattered nodes cause cache misses on every traversal. Use ArrayList as the default; LinkedList only when you have a persistent iterator pointing to the insert location and are doing many such operations. For queue semantics, use ArrayDeque.
Calling LinkedList.get(index) is O(n) — the list traverses from the head or tail each time. A loop that calls get(i) in a for loop over a LinkedList is O(n²).