Compare arrays and singly linked lists as ways of storing a sequence.
Your answer should cover:
- How each is laid out in memory, and what that layout makes cheap or expensive.
- The Big-O cost of: indexing (get the k-th element), search, insertion/deletion at the front, and insertion/deletion in the middle (in both structures).
- Why arrays are usually faster in practice even for operations with the same Big-O (mention CPU caches).
- One scenario where a linked list is genuinely the better choice.