Micro-Drill #242 — Array vs linked list tradeoffs

ARRAY vs LINKED LIST TRADEOFFS
──────────────────────────────
                ARRAY       LINKED LIST
Access [i]:     O(1)        O(n)
Search:         O(n)/O(logn) O(n)
Insert front:   O(n)        O(1)
Insert end:     O(1)*       O(1)**
Insert middle:  O(n)        O(1)***
Delete:         O(n)        O(1)***
Memory:         contiguous  scattered + pointer overhead
Cache:          excellent   poor (pointer chasing)

* amortized with dynamic array
** with tail pointer
*** given pointer to position

USE ARRAY when:
  □ Need random access (a[i])
  □ Cache performance matters
  □ Fixed or mostly-append workload
  □ Binary search needed

USE LINKED LIST when:
  □ Frequent insert/delete at arbitrary positions
  □ Need O(1) insert/delete given position
  □ Implementing LRU cache (doubly linked + hash)
  □ Merging sorted lists