Arrays & Lists
The problem
Most real data isn't a single value but a sequence of them — a list of users, a row of pixels, a queue of tasks. Arrays and lists give a way to store, index, and iterate over an ordered collection of values as a single unit.
Why now
Types and values gives us individual values; variables gives us a name for one value at a time. Neither explains how to hold an arbitrary, ordered many — that requires a new structure that combines indexing (a function from position to value) with contiguous or linked storage.
Mental model
An array is a function from index to value, made concrete: array[i] is exactly evaluating that function at i. Fixed-size, contiguous arrays give O(1) access because the position IS the address (a direct computation, no searching); linked lists trade that for O(1) insertion by chaining nodes instead.
Requires
- Types & ValuesProgramming Fundamentals
An array or list holds elements of some type; you need a notion of value and type before you can talk about a collection of them.
- Functions & RelationsMathematical Thinking
Indexing (array[i]) is precisely a function from index to value; understanding it as a function explains why out-of-bounds access is asking a function outside its domain.
Helps
- Number Systems & BasesMathematical Thinking
Contiguous array indexing is address = base + index × element_size, a direct application of positional arithmetic — helpful for understanding why arrays are fast, not required to use them.
Unlocks
- Stacks & QueuesComputer Science Fundamentals
- Hash TablesComputer Science Fundamentals
- Heaps & Priority QueuesComputer Science Fundamentals
- Union-Find (Disjoint Set)Computer Science Fundamentals
- Sliding Window & Two PointersComputer Science Fundamentals
- Mutability & ReferencesProgramming Fundamentals
- Strings & TextProgramming Fundamentals
- Higher-Order FunctionsProgramming Fundamentals
- Keys & ListsReact
Related
Used in
- Arrays/lists/vectors in every programming language's standard library
- Database result sets (rows returned as an ordered sequence)
- Rendering lists of UI components (React lists, table rows)
- Contiguous memory layout underlying most data structures (strings, buffers, matrices)
Projects
- Implement a fixed-size array-backed stack (push/pop) and a singly linked list, then benchmark random access on each
- Write your own map/filter/reduce from scratch using only a for-loop and an array
Examples
- users[3] retrieves the 4th element by direct address computation — O(1), not a search
- A linked list node { value, next } trades direct indexing for cheap insertion anywhere
Resources
Mastery checklist
- I can explain why array indexing is O(1) in terms of address computation
- I can explain the space/time tradeoff between arrays and linked lists
- I can implement basic list operations (append, insert, remove) by hand
- I can identify when a problem calls for indexed access versus sequential traversal