ArrayList vs LinkedList

ArrayList stores elements in an array: get(i) is $O(1)$, inserting/deleting in the middle is $O(n)$ due to shifting. LinkedList: get(i) is $O(n)$, inserting/deleting at known positions is $O(1)$.

Rule of thumb: many indexed accesses and rare middle insertions -> ArrayList. Many structural changes at the ends or with iterator position -> LinkedList.

Measurements challenge prejudices: the locality of arrays often wins in practice.

Backend and Android: almost always ArrayList/ArrayDeque. LinkedList is rarely worthwhile; cache misses and object headers dominate. Point of reference: many insertions in the middle with already known node position (rare in application code).

Depth

A dynamic array stores references contiguously and allows direct indexed access. In contrast, a linked structure follows node references. Big-O notations alone do not capture the advantages of cache locality and lower object overhead of the array.

Inserting in the middle requires shifts for the array, while for the linked list, it only involves reference changes at a known position. However, if the position is first searched via an index, linear work also incurs there. The claimed constant insertion time thus only applies with a suitable cursor.

For small to medium-sized collections, the dynamic array is often practically faster. Linked list is particularly sensible when stable node positions or frequent local changes via existing iterators are required.

Difficulty levels

1. Compare indexed access and end insertion.
2. Evaluate search and modification costs separately.
3. Include cache behavior and memory overhead in the choice of structure.

Pitfalls

The statement "insertion is constant" often overlooks the search for the position. Similarly, asymptotically equal runtimes do not imply the same real runtime with different memory access patterns.