Choose Between an Array and a Linked List

Compare arrays and linked lists as implementation choices. Explain their time complexity, memory layout, cache behavior, allocation overhead, and iterator or reference stability. Then choose a structure for each scenario below and justify the choice: 1. Frequent indexed reads over a mostly fixed collection. 2. Frequent insertion after a node that is already known. 3. A queue with millions of small elements on modern hardware. ### Constraints & Assumptions - Compare a contiguous dynamic array with a conventional pointer-based singly or doubly linked list. - Include real constant factors rather than relying only on asymptotic notation. - State when the claimed linked-list insertion complexity excludes the cost of locating the node. ### Clarifying Questions to Ask - Is the collection size known or bounded? - Must references to existing elements remain valid after insertion? - Are insertions specified by index or by an existing node handle? - Is memory locality or per-element overhead a limiting resource? ```hint Separate lookup from mutation An insertion can be constant time only after the insertion location has already been found. ``` ### What a Strong Answer Covers - Indexed access, traversal, insertion, deletion, and resizing costs. - Contiguous storage and cache locality versus pointer chasing. - Per-node pointers, allocator overhead, and fragmentation. - Nuanced choices for all three scenarios. ### Follow-up Questions - Why can a dynamic array outperform a linked list even when both operations are (O(n))? - When does a deque improve on both choices for queue operations? - How do intrusive lists change ownership and allocation trade-offs?