Questions: Array Data Structure: Representation and Operations

Question 1

A lookup table stores 1 million integer entries. A program reads entries by index billions of times per second but almost never inserts or deletes. Why are arrays the ideal data structure for this use case?

• A. Arrays keep elements sorted, making binary search faster
• B. Arrays support O(1) random access via address arithmetic and exploit cache locality, making reads extremely fast regardless of array size
• C. Arrays have O(1) insertion at any position, minimizing the rare write overhead
• D. Arrays use less memory per element than any other data structure

Answer: (B)

O(1) access via base_address + i × element_size means any element is reachable in one arithmetic step. Cache locality amplifies this: sequential or repeated accesses to nearby indices hit the L1/L2 cache, which is orders of magnitude faster than main memory. For a read-heavy workload, these properties make arrays nearly unbeatable. The O(n) insertion cost is irrelevant here because insertions are rare.

Question 2

You insert a new element at index 0 of an array containing 10,000 elements. How many elements must be moved, and why?

• A. 1 — only the inserted element is placed
• B. About 5,000 on average — half the array, since indices below and above 0 exist
• C. 10,000 — every existing element must shift one position to the right to make room
• D. 0 — arrays store a pointer to the new element, so no shifting is needed

Answer: (C)

Every element at indices 0 through 9999 must shift right by one to vacate index 0. This is O(n) in the worst case (insertion at position 0), and also O(n) on average for insertion at a random position (n/2 shifts). This is the direct cost of contiguous memory: creating a gap at any position requires moving everything after it. Linked lists avoid this by using pointers instead of adjacency.

Question 3

Appending to the end of a Python list (dynamic array) usually takes O(n) time because the array may need to be resized.

• T. True
• F. False

Answer: False

Appending takes amortized O(1) time. When the array is full, it reallocates to a new block roughly twice as large and copies all n elements — that resize is O(n). But because capacity doubles, the next n appends each take O(1) with no copying. Spreading the O(n) resize cost over those n appends gives an amortized cost of O(1) per append. The occasional expensive resize does not change the long-run average.

Question 4

Array traversal (iterating over all elements in order) is often faster in practice than linked-list traversal, even though both are O(n) in Big-O notation.

• T. True
• F. False

Answer: True

Big-O hides constant factors and hardware effects. Arrays store elements contiguously, so iterating sequentially triggers the CPU's prefetcher and loads entire cache lines at once — many elements arrive in L1 cache with a single memory access. Linked-list nodes are scattered across the heap; each 'next' pointer dereference risks a cache miss, requiring a round-trip to main memory that can be 100x slower than a cache hit. Arrays exploit hardware locality that Big-O analysis ignores.

Question 5

Why does contiguous memory layout make array random access O(1) and insertion O(n)? Explain how the same property causes both.

Model answer: Contiguous layout means every element is at a predictable offset from the base address: element i is at base + i × element_size. This single arithmetic computation gives any element in constant time — O(1) — regardless of array size. But the same layout means there are no gaps: elements must be packed adjacently. Inserting at position i requires every element from i to the end to shift one slot right to create the needed space, which takes O(n) time in the worst case. The structure that makes access instant (fixed offsets) makes arbitrary insertion expensive (no free gaps).

This tradeoff is fundamental and cannot be engineered away within the contiguous-memory constraint. Linked lists flip the tradeoff: pointer-based layout enables O(1) insertion (just relink pointers) but loses O(1) random access (must follow n pointers to reach position i).