Compare Arrays and Linked Lists for Indexed Operations

Compare arrays and linked lists as representations of an ordered sequence. Explain how their memory layouts affect indexed reads, insertion, traversal, and real execution costs. ### Constraints & Assumptions - Distinguish a fixed-size array from a resizable contiguous array when discussing capacity growth. - State whether a linked-list operation starts with an index, a node pointer, or a pointer to the predecessor; those are different inputs. - Focus on the sequence operations that motivate storing several consecutive elements inside each linked-list node. ### Clarifying Questions to Ask - Are most reads indexed or sequential? - Is an insertion position already available as a node/iterator, or must it be located by index? - Must existing element addresses or iterators remain valid after growth or insertion? ```hint Include the cost of reaching the position An insertion can have constant-time pointer updates while still requiring a linear traversal to locate the insertion point. ``` ### What a Strong Answer Covers - Contiguous storage and constant-time indexed access for arrays. - Pointer traversal, per-node overhead, and cache locality for linked lists. - Insertion costs with and without an already-known position. - Capacity reallocation and amortized append for resizable arrays. - How grouping multiple values per linked node changes locality and pointer overhead without giving automatic constant-time indexed access. ### Follow-up Questions - What trade-off does an unrolled linked list make compared with one value per node? - Why can contiguous-array traversal beat linked-list traversal even when both are linear time?