# Arrays, Lists, and Memory Layout

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/arrays-lists-and-memory-layout

## Memory Layout & Arrays

The two fundamental sequence structures differ in **memory layout**, and everything about their performance follows from it.

An **array** stores elements in a single **contiguous** block of memory. Because elements are adjacent and equally sized, the address of element $i$ is computed directly as $\text{base address} + (i \times \text{element size})$, giving $O(1)$ **random access** to jump to any index instantly.

The cost is rigidity: inserting or removing in the middle requires shifting all following elements, which takes $O(n)$ time, and a fixed array cannot grow beyond its allocated size.

## Linked Lists & Trade-offs

A **linked list** stores each element in a separate **node** holding a **pointer** to the next node. Nodes sit anywhere in memory; the chain is held together by pointers.

| Operation | Array | Linked list |
|---|---|---|
| Access element i | $O(1)$ | $O(n)$ |
| Insert/remove at known position | $O(n)$ | $O(1)$ |
| Grow beyond capacity | Costly / fixed | Easy |

> **Common pitfall:** assuming linked lists are faster because insertion is $O(1)$. That $O(1)$ insertion assumes you **already hold** the position; finding it takes $O(n)$, and arrays are far more cache-friendly.

## Practice questions

3 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Inserting at the **front** of an array is O(n) and at the front of a linked list is O(1). Why does that reverse the usual verdict between the two structures?

A. Because the operation is rare enough that the difference does not matter
B. Because contiguity, which makes indexing instant, forces every element to shift
C. Because arrays cannot insert at position zero without reallocating
D. Because linked lists store elements in reverse order internally

**Answer:** B. Because contiguity, which makes indexing instant, forces every element to shift

**Why:** Contiguity is a single design choice paying off in one direction and charging in the other: computable addresses require everything in order, so a front insert moves everything. Neither structure dominates, which is why the choice is made from the workload rather than from a table.

Page: https://tryals.app/practice/computer-science-i/arrays-lists-and-memory-layout/inserting-at-the-front-of-an-array-is-o-n-and-at-the-front-of-a

### 2. Select every statement the lesson supports about the claim that linked lists are faster than arrays.

A. Linked lists index by position faster than arrays do
B. Finding a position in a linked list is still O(n)
C. Neither structure is universally better
D. Insertion is only O(1) once you already hold the position
E. Arrays scan more cache-friendly because their elements are adjacent

**Answer:** B. Finding a position in a linked list is still O(n); C. Neither structure is universally better; D. Insertion is only O(1) once you already hold the position; E. Arrays scan more cache-friendly because their elements are adjacent

**Why:** The constant-time insertion is real but conditional, finding the spot is still a walk, and contiguity makes array scanning genuinely faster in practice. Only the indexing claim is backwards: computing an address beats following pointers, and reversing that is the misconception the pitfall targets.

Page: https://tryals.app/practice/computer-science-i/arrays-lists-and-memory-layout/select-every-statement-the-lesson-supports-about-the-claim-that

### 3. Removing a node from a singly linked list is O(1) once you hold a reference to that node.

**Answer:** False

**Why:** False. Unlinking needs the *predecessor*, whose next pointer must be redirected, and finding it in a singly linked list is an O(n) walk. A doubly linked list stores that back pointer and does make it O(1), which is the whole reason to pay for the extra pointer per node.

Page: https://tryals.app/practice/computer-science-i/arrays-lists-and-memory-layout/removing-a-node-from-a-singly-linked-list-is-o-1-once-you-hold-a