Choosing between an Array and a Linked List is one of the classic engineering trade-offs in software design. Neither structure is universally superior; each excels under opposite operational patterns.
The Head-to-Head Comparison Matrix
| Operational Characteristic | Array (or Dynamic Array) | Linked List (Singly / Doubly) | Winner |
|---|---|---|---|
Random Access (get(i)) | O(1) (Direct arithmetic) | O(n) (Sequential walk) | Array |
| Insert / Delete at Beginning | O(n) (Must shift all items) | O(1) (Update pointer) | Linked List |
| Insert / Delete at End | O(1) amortized | O(1) (with tail pointer) | Tie |
| Insert / Delete in Middle | O(n) (Shift elements) | O(1) after pointer is found | Linked List |
| Search by Value (Unsorted) | O(n) | O(n) | Tie |
| Search by Value (Sorted) | O(log n) (Binary Search) | O(n) (Cannot binary search!) | Array |
| Memory Overhead | Minimal (consecutive values) | High (4–8 bytes per pointer) | Array |
| Cache Locality | Excellent (spatial locality) | Poor (pointer hopping) | Array |
| Memory Fragmentation | Requires large contiguous block | Allocates small scattered nodes | Linked List |
Why You Almost Never Want LinkedList in Modern Software
In theoretical computer science textbooks, linked lists are praised for O(1) insertions and deletions. However, in modern systems engineering (Android, iOS, backend servers), ArrayList beats LinkedList in 95% of real-world use cases.
The Three Hardware Realities:
- To insert in the middle, you must find the position first:
While the pointer relink is
O(1), searching for indexktakesO(k)time. The search cost dominates! - CPU Cache Misses:
An array's
O(n)memory shift is performed using optimized hardware vector instructions (memmove/System.arraycopy), which operate inside L1 cache lines at gigabytes per second. A linked list'sO(n)traversal causes constant RAM stall cycles. - Garbage Collection Overhead: A linked list with 100,000 items creates 100,000 distinct heap objects. This puts massive pressure on the Android Garbage Collector (ART), causing GC pauses and dropped frames. An array list is just 1 heap object!
When SHOULD You Use a Linked List?
- Strict
O(1)Worst-Case Guarantee: When real-time constraints forbid the occasionalO(n)reallocation spike of dynamic arrays. - Frequent Head Insertions / Removals: Implementing Queues or Deques where items enter at one end and leave at the other.
- Splitting and Merging Lists:
Two linked lists can be spliced together in
O(1)time by reconnecting pointers, whereas combining two arrays requiresO(n)copying.
Summary
- Default to Arrays / ArrayLists for cache efficiency, random access, and low GC footprint.
- Use Linked Lists when splicing lists, implementing queues, or when holding direct node references for
O(1)removals (like LRU caches).