# Data Structures, Explained

> The handful of containers you actually use day to day - arrays/lists, maps, sets, stacks, queues, and linked lists - what each one is really good at, and how to pick the right one without overthinking it.


---

# Data Structures, Explained

You can already write code - loop over things, store a value in a variable, call a function. But somewhere
along the way someone said "use a hash map here" or "that should be a set," and it landed like a foreign
language - you nodded, picked whatever you already knew, and moved on. That works right up until the day
your program crawls to a halt and you have no idea why.

Here's the secret: you don't need to memorize a textbook of exotic structures. In everyday code you reach
for the same **three or four containers** over and over. Once you understand what each one is actually
*doing under the hood* - not the formal definition, the working picture - choosing between them stops being
a guess and becomes obvious. That's the whole goal of this guide.

We'll keep the examples in Python because it's readable, but every idea here exists in every language
(JavaScript calls a map an `Object` or `Map`, Java calls it a `HashMap`, and so on). The container has
different names; the mental model is identical.

## How to read this

- **Want it to finally make sense?** Read in order - each phase builds the picture one container at a time,
  and the last phase ties them together into a decision you can make in seconds.
- **Just need to pick one right now?** Jump to [Phase 3: Choosing the Right One](03-choosing-the-right-one.md)
  and use the decision questions and the comparison table near the top.

## The phases

1. **[Arrays & Lists - Ordered Collections](01-arrays-and-lists.md)** - an indexed, ordered sequence: what's
   cheap (grabbing item #5, adding to the end) and what quietly costs you (inserting in the middle).
2. **[Maps & Sets - Lookup by Key](02-maps-and-sets.md)** - dictionaries (key → value, near-instant lookup)
   and sets (a bag of unique things), plus a gentle picture of the "hashing" trick that makes them fast.
3. **[Choosing the Right One](03-choosing-the-right-one.md)** - a practical decision guide and a side-by-side
   table of what's fast vs slow for each, so the next time someone says "use a map" you'll already know why.
4. **[Stacks, Queues & Linked Lists](04-stacks-queues-and-linked-lists.md)** - two access-restricted variants
   on a list (LIFO and FIFO), plus linked lists: nodes chained by pointers instead of packed in a row.

> This guide covers the containers you use daily, including stacks, queues, and linked lists in Phase 4.
> Trees get their own guide - [Trees & Binary Search Trees](/guides/trees-and-binary-search-trees) - and the
> formal math of *why* operations are fast lives in
> [Big-O Without the Math Panic](/guides/big-o-without-the-math-panic).


---

# Arrays & Lists - Ordered Collections

The very first container almost everyone meets is the list - a row of names, a sequence of scores, the
lines of a file. It feels simple, and most of the time it is. But there's a quiet trap: some things you do
to a list are basically free, and others look just as innocent but get slower as the list grows. By the end
of this phase you'll be able to look at a line of code and *feel* which kind you're doing.

📝 **Terminology.** An **array** is a fixed row of numbered slots laid out one after another in memory. A
**list** is the friendlier, everyday version most languages hand you (Python's `list`, JavaScript's
`Array`) - it grows and shrinks for you and hides the bookkeeping. The mental model below is the same for
both; we'll say "list" from here on, and call out the array detail only where it matters.

## The mental model: a row of numbered slots

**What it actually is.** A list is a row of slots, side by side, each holding one item, and each with a
number called its **index**. Picture a row of lockers:

```mermaid
flowchart LR
  S0["Mo<br/>index 0"]:::first --> S1["Tu<br/>index 1"] --> S2["We<br/>index 2"] --> S3["Th<br/>index 3"] --> S4["Fr<br/>index 4"]:::last
  classDef first fill:#1a3a2a,stroke:#3a7a5a;
  classDef last fill:#1a3a2a,stroke:#3a7a5a;
```

📝 **Terminology.** The **index** is the slot number. Almost every language starts counting at **0**, not
1 - so the first item is at index `0`, and a list of five items has indexes `0` through `4`. This
off-by-one feeling confuses everybody at first; you stop noticing it within a week.

**Why the order matters.** A list *remembers the order you put things in*. Monday stays before Tuesday
until you change it. That's the defining feature: a list is for when sequence means something - steps in a
recipe, messages in a chat, rows in a spreadsheet.

## Reaching for an item by index - basically free

**What it does in real life.** Because the slots are laid out in a neat row, the computer can jump
*straight* to any slot just from its number. It doesn't walk past slots 0, 1, 2 to reach slot 3 - it
computes where slot 3 lives and lands on it directly. Slot #3 and slot #3000 cost the same.

```python runnable
days = ["Mo", "Tu", "We", "Th", "Fr"]

print(days[0])   # the first item
print(days[3])   # the fourth item
```
```console
Mo
Th
```
*What just happened:* `days[3]` means "give me whatever is in slot number 3." The computer went straight
there and handed it back. This jump-to-a-slot move is the list's superpower, and it's why lists are the
default container for "I have a bunch of things in order and I want item number N."

💡 **Key point.** Access *by index* is the thing lists are fastest at. If your code spends its life saying
"give me item number N," a list is exactly right.

## Adding to the end - cheap

**What it does in real life.** Sticking a new item onto the *end* of a list is usually quick: there's
almost always room just past the last slot, so the item drops into place and the list's length ticks up by
one.

```python runnable
days = ["Mo", "Tu", "We", "Th", "Fr"]
days.append("Sa")
print(days)
```
```console
['Mo', 'Tu', 'We', 'Th', 'Fr', 'Sa']
```
*What just happened:* `append` put `"Sa"` in the next slot after `"Fr"` and nothing else had to move. The
existing items kept their slots and their indexes. Appending is the natural, cheap way to grow a list.

📝 **Terminology.** "Cheap" / "fast" here means *the cost doesn't grow as the list gets bigger* - appending
to a 10-item list and a 10-million-item list feel the same. (Occasionally a growing list needs a bigger
stretch of memory and copies itself, but averaged out, appending stays cheap - see
[Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) for the full picture.)

## Inserting or removing in the *middle* - this is the costly one

Here's the trap. Adding to the *end* is cheap. Adding to the *middle* is not - and the code looks almost
identical, which is exactly why it bites people.

**Why it costs.** Remember the slots are a tight row with no gaps. To squeeze a new item into slot 1,
*every item from slot 1 onward has to shuffle one slot to the right* to make room. The bigger the list, the
more items have to move.

```mermaid
flowchart LR
  A[A] --> X["X - inserted at index 1"] --> B[B] --> C[C] --> D[D]
```
*Inserting `X` at index 1 shoves `B`, `C`, `D` each one slot to the right to make room.*

```python runnable
letters = ["A", "B", "C", "D"]
letters.insert(1, "X")   # put "X" at index 1, shove the rest over
print(letters)
```
```console
['A', 'X', 'B', 'C', 'D']
```
*What just happened:* `insert(1, "X")` placed `"X"` at index 1 and quietly moved `B`, `C`, and `D` each one
slot to the right. For four items that's nothing - but for a list of a million items where you keep
inserting near the front, all that shuffling adds up to real, noticeable slowness. Removing from the middle
works the same way in reverse: everything after the gap shuffles *left* to close it.

⚠️ **Gotcha.** A list inserting/removing at the *end* is cheap; doing it at the *front or middle* gets
slower as the list grows. They look like the same operation in your code - `append` vs `insert(0, ...)` -
but one is free and the other isn't. If you find yourself constantly inserting at the front of a big list,
that's a signal you might want a different structure - see
[Phase 4: Stacks, Queues & Linked Lists](04-stacks-queues-and-linked-lists.md) for the "queue," which is
built exactly for cheap add/remove at *both* ends.

## Searching for a value - you have to look through them

One more plain limitation. A list is fast at "give me item number N," but it's *not* fast at "is the value
`"We"` in here, and where?" To answer that, the computer has no shortcut - it walks the slots one by one,
checking each, until it finds a match or runs out.

```python runnable
days = ["Mo", "Tu", "We", "Th", "Fr"]
print("We" in days)        # is it present?
print(days.index("We"))    # at which slot?
```
```console
True
2
```
*What just happened:* `"We" in days` made the computer scan from the front, comparing each item, until it
hit `"We"` at slot 2. On a short list that's instant, but on a huge list, searching by *value* this way gets
slower the bigger it grows - every item is a potential stop along the walk.

Hold onto that limitation, because it's the exact pain the next phase solves. When your real question is
"do I have this thing, and what's attached to it?" - a list makes you walk the whole row, and there's a
container built to answer that *instantly* instead.

## Recap

1. A **list** is an ordered row of numbered **slots**; the slot number is its **index** (counting from `0`).
2. **Order is preserved** - use a list when sequence matters.
3. **Access by index** (`days[3]`) is basically free, no matter how big the list is.
4. **Appending to the end** is cheap.
5. **Inserting/removing in the middle or front** is costly - everything after has to shuffle over.
6. **Searching by value** (`"We" in days`) means walking the list item by item - fine for small lists,
   slow for big ones.

That last point - slow lookup by value - is the doorway to the next container. Let's open it.

---

Append is cheap; inserting at the front shifts everything. Click a box to see index access is instant:

```playground-ds
array
```


---

# Maps & Sets - Lookup by Key

Last phase ended on a frustration: a list makes you *walk* through everything to answer "do I have this, and
what's attached to it?" - fine for ten items, miserable for ten million. This phase is about the container
built precisely to kill that walk - the **map** - and its close cousin, the **set**. Once these click, a
huge amount of everyday code suddenly looks obvious.

## The mental model: a labeled value you can jump to

**What a map actually is.** A **map** stores pairs: a **key** and a **value** that belongs to it. You look
things up *by the key*, and you get the value back without searching. Think of a coat check at a theater:
you hand over your coat (the value) and get a numbered ticket (the key). When you come back, you don't dig
through every coat - you hand over ticket #42 and the attendant goes *straight* to hook 42.

```mermaid
flowchart LR
  K1["key: ada"] -->|value| V1["ada@mail.io"]
  K2["key: linus"] -->|value| V2["linus@x.org"]
  K3["key: grace"] -->|value| V3["grace@navy"]
```

📝 **Terminology.** A map goes by many names. Python calls it a **dict** (dictionary); JavaScript has
objects and a `Map`; Java calls it a `HashMap`; other languages say "hash," "associative array," or
"hashtable." They're the same idea: **key → value, fast lookup by key.** We'll say "map" or "dictionary."

## Using a map - set a value, get it back

```python runnable
emails = {
    "ada": "ada@mail.io",
    "linus": "linus@x.org",
}

emails["grace"] = "grace@navy.mil"   # add a new pair
print(emails["ada"])                 # look up by key
```
```console
ada@mail.io
```
*What just happened:* The `{ ... }` created a map with two pairs. `emails["grace"] = ...` added a third pair
- the key `"grace"` now points at her email. Then `emails["ada"]` asked "what value is filed under the key
`ada`?" and got it back **without** scanning the other entries. That's the move a list couldn't do: direct
lookup by something meaningful, not by a slot number.

⚠️ **Gotcha.** Asking for a key that isn't there is a classic stumble - in Python it raises a `KeyError`
and stops your program:

```python
print(emails["nobody"])
```
```console
KeyError: 'nobody'
```
*What just happened:* There's no pair filed under `"nobody"`, so the map couldn't hand anything back and
raised an error. The safe way to ask is `emails.get("nobody")`, which returns `None` instead of crashing -
reach for `.get()` whenever you're not certain a key exists.

## Why it's fast: hashing, the gentle version

Here's the one piece of magic worth understanding, because it explains *everything* about why maps are fast
and lists aren't.

**The idea.** When you give the map a key like `"ada"`, it runs the key through a little function called a
**hash function**, which turns the key into a number that says *which shelf* the value lives on. So instead
of searching, the map *computes the location* from the key itself and goes straight there.

```mermaid
flowchart LR
  Key["key: ada"] --> Hash["hash function"] --> Shelf["shelf #7"] --> Go["go directly to shelf 7"]
```

Compare that to last phase's list, where finding a value meant walking every slot. A map skips the walk
entirely: the key tells it where to look. That's the whole secret.

📝 **Terminology.** **Hashing** is turning a key into a number that points at a storage spot. You almost
never call the hash function yourself - the map does it for you on every lookup and every insert. You just
need the picture: *the key is a label that jumps you near the value.*

💡 **Key point.** Looking up by key in a map stays fast *no matter how many pairs it holds* - 10 entries or
10 million, fetching one by its key feels the same. That "doesn't slow down as it grows" quality is the
reason maps exist.

A couple of plain caveats, so the picture is true and not a fairy tale:

- ⚠️ **Keys must be unique.** Assign to a key that already exists and you *overwrite* its old value rather
  than adding a second one. A map holds at most one value per key.
- A map does **not** keep a meaningful order the way a list does. (Modern Python happens to remember
  insertion order, but you shouldn't lean on a map for "what came 3rd" - that's a list's job.)

## Sets - the same trick, for uniqueness

Now the cousin. Sometimes you don't care about a value attached to a key - you only care *whether you've
seen a thing*. That's a **set**.

**What a set actually is.** A set is a bag of items where (a) **each item appears at most once** and (b)
checking "is this in the bag?" is fast. It's a map that kept only the keys and threw away the values - so it
inherits the same hashing speed.

```python runnable
seen = set()
seen.add("ada")
seen.add("linus")
seen.add("ada")        # already there - silently ignored

print(seen)
print("ada" in seen)   # fast membership check
print(len(seen))       # how many unique items?
```
```console
{'ada', 'linus'}
True
2
```
*What just happened:* Adding `"ada"` a second time did nothing - a set refuses duplicates by design, which
is exactly the point. `"ada" in seen` answered instantly (same hashing jump as a map, no walking), and
`len(seen)` is 2 because there are only two *unique* items even though we called `add` three times.

**What it does in real life.** Sets shine for two jobs: **deduplicating** ("give me the unique values") and
**fast membership** ("have I already processed this ID?"). A common one-liner removes duplicates from a list
by passing it through a set:

```python runnable
ids = [3, 7, 3, 1, 7, 7]
unique_ids = set(ids)
print(unique_ids)
```
```console
{1, 3, 7}
```
*What just happened:* Building a set from the list dropped every repeat automatically - there's no value to
store, just "is this item present?", and a set only keeps one copy of each. Order isn't preserved, because,
like a map, a set is organized by hashing, not by sequence.

## How these three fit together

You now have the everyday trio. Here's the one-line version of each, which is really the whole guide in
miniature:

- **List** - ordered; jump to item #N fast; finding a *value* means walking.
- **Map** - key → value; fetch a value by its key fast; no real order.
- **Set** - unique items; "is it in here?" fast; no values, no order.

Notice the trade running through all three: lists give you *order* but slow value-lookup; maps and sets give
you *fast lookup* but drop ordering. There's no single best container - there's the right one for the
question you're asking. The next phase turns that into a decision you can make in seconds.

## Recap

1. A **map** (dict / hash map) stores **key → value** pairs and fetches a value by its key without scanning.
2. The speed comes from **hashing**: the key is run through a function that points straight at the value's
   spot - a label that jumps you near the value.
3. Map lookup by key stays fast no matter how big it grows; **keys are unique** (re-assigning overwrites).
4. A **set** is the same trick minus the values: a bag of **unique** items with **fast membership** checks.
5. Use sets to **dedupe** and to answer "**have I seen this?**" quickly.
6. Maps and sets trade away **order** for speed - when order matters, that's a list's job.

---

Set keys and click a row to "get" by key - no scanning. Switch the tab to a set to see uniqueness:

```playground-ds
map
```


---

# Choosing the Right One

You've met the three containers and seen what each is built for. This phase is the payoff: a way to pick the
right one in a few seconds, and the comparison table to glance at when you forget. There's no clever theory
here - picking a data structure comes down to clearly answering what your code keeps *asking* of the data.

If you're here mid-task and just need an answer, the three questions below and the table will get you sorted.
If you want the reasoning, it's all underneath.

## The cheat-card: three questions

Ask these in order. The first "yes" usually points you at your container.

```mermaid
flowchart TD
  Q1{"Order or position<br/>matters?"} -->|yes| List[use a LIST]
  Q1 -->|no| Q2{"Look up by KEY<br/>for a value?"}
  Q2 -->|yes| Map[use a MAP / dict]
  Q2 -->|no| Q3{"Only care if present,<br/>no duplicates?"}
  Q3 -->|yes| Set[use a SET]
```

Most everyday code is one of these three. When two seem to fit, ask which question your code asks *most
often* - that's the operation you want to be fast.

## The comparison table

Here's what each container is fast and slow at, side by side. "Fast" means the cost barely changes as the
data grows; "slow" means it gets worse the bigger the collection gets.

| Operation | List | Map (dict) | Set |
|---|---|---|---|
| Get item by **index/position** (`x[3]`) | **fast** | n/a | n/a |
| Get value by **key** (`x["ada"]`) | n/a | **fast** | n/a |
| Check "**is this value present?**" (`v in x`) | slow (walks it) | **fast** (by key) | **fast** |
| **Add to the end** | **fast** | **fast** | **fast** |
| **Insert/remove in the middle or front** | slow (shuffles) | n/a | n/a |
| Keeps **order**? | **yes** | no | no |
| Allows **duplicates**? | yes | keys: no | no |

Read the table as a map of strengths, not a scoreboard. Each container is *fast at the thing it's for* and
slower at (or doesn't do at all) the things it isn't for - there's no winner, only a fit.

## Big-O, as intuition only

You'll hear people describe these speeds with **Big-O notation** - terms like `O(1)` and `O(n)`. Don't let
the symbols scare you; for now they're just two plain ideas:

- 📝 **"Constant"** (written `O(1)`) - the cost **doesn't grow** as the collection gets bigger. Grabbing
  `list[3]` or fetching `map["ada"]` costs the same whether there are 10 items or 10 million. This is the
  "fast" in the table above.
- 📝 **"Grows with size"** (written `O(n)`) - the cost **gets bigger as the collection grows**, because the
  work scales with the number of items. Searching a list by value, or inserting at its front and shuffling
  everything over, is this kind. This is the "slow" in the table.

That's genuinely all you need to choose well: *is this operation constant, or does it grow with size, and is
it the operation I do most?* The formal definitions, the math, and the in-between speeds belong to
[Big-O Without the Math Panic](/guides/big-o-without-the-math-panic) - chase them when you're optimizing real
code, not before.

## The classic slowdown: a list where you needed a map

Here's the mistake that quietly tanks more beginner programs than any other, and now you can see exactly why
it happens.

Say you have a big list of users and you keep checking "is this user already in here?" A list feels like the
obvious home for "a bunch of users," so people write:

```python
users = ["ada", "linus", "grace", ...]   # imagine 100,000 names

# called over and over in a loop:
if "grace" in users:
    ...
```
*What just happened:* every single `"grace" in users` makes the computer **walk the list** from the front,
comparing names one at a time (that's the "grows with size" cost from Phase 1). Do that check thousands of
times over a list of a hundred thousand, and your program slows to a crawl - not because anything is
*broken*, but because you picked a container that's slow at the exact question you keep asking.

The fix is to ask: *what does this code keep doing?* It keeps checking membership. That's question 3 - so it
wants a **set**:

```python
users = {"ada", "linus", "grace", ...}   # a set, built for membership

if "grace" in users:                     # fast, no walking
    ...
```
*What just happened:* the membership check now uses hashing to jump straight to the answer instead of
scanning (the "constant" cost from Phase 2). Same-looking code, the bottleneck gone. If you also needed
*data attached* to each user - their email, their last login - you'd reach for a **map** (`users["grace"]`)
for the same reason.

⚠️ **Gotcha.** Reaching for a list when you needed a map or set is *the* classic beginner slowdown. The
tell: you're repeatedly doing `something in my_list` or scanning a list to find a matching item. Both are
"grows with size" on a list and "constant" on a set/map. When you catch yourself searching a list by value
again and again, that's your cue to switch containers - and you'll often watch a sluggish program turn
instant.

## Putting it all together

You came in able to write code but unsure which container to grab. Now you have a real model:

- A **list** is an ordered row of slots - perfect when **sequence or position** matters, fast to read by
  index and to append, slow to search by value or edit the middle.
- A **map** files **values under keys** - perfect when you look things up by a meaningful key and want the
  value back instantly.
- A **set** keeps **unique items** with **fast membership** - perfect for deduping and "have I seen this?"
- The deciding question is never "which is best" but "**what does my code keep asking?**" Match the container
  to that question and the right one is usually obvious.

That's the everyday toolkit. When you're ready to go deeper, [Phase 4](04-stacks-queues-and-linked-lists.md)
covers stacks, queues, and linked lists, and [Trees & Binary Search Trees](/guides/trees-and-binary-search-trees)
picks up from there. Until then, you have more than enough to choose well and write code that stays fast as
it grows.

## Recap

1. **Three questions** decide it: order/position → **list**; lookup by key → **map**; uniqueness/membership
   → **set**.
2. The **comparison table** shows each container is fast at what it's *for* and slow at what it isn't.
3. **Big-O is just intuition** for now: **"constant"** (doesn't grow) vs **"grows with size."**
4. The **classic slowdown** is using a list where you needed a map or set - repeatedly searching a list by
   value is "grows with size"; a set/map makes it "constant."
5. Always ask **"what does my code keep doing?"** and make *that* operation the fast one.

---

A preview of two more structures - push/pop a stack (LIFO) versus enqueue/dequeue a queue (FIFO). Phase 4
covers what's happening here in full:

```playground-ds
```

**Related guides:** [Programming from Zero](/guides/programming-from-zero) · [What Happens When Code Runs](/guides/what-happens-when-code-runs)


---

# Stacks, Queues & Linked Lists

The first three phases covered the containers you reach for daily. This phase covers three more you'll meet
constantly once you start looking - not because they're exotic, but because they're the *same* row-of-items
idea from Phase 1, restricted in a way that makes one specific pattern of use fast and predictable.

## Stack: last in, first out (LIFO)

**What it actually is.** A stack only lets you add or remove from *one* end - the "top." The last thing you
put on is the first thing you take back off.

**Real-world analogy.** A stack of plates. You put a clean plate on top and you take the top plate off to
use it - you never pull one from the middle without knocking the rest over. Your browser's back button
works the same way: each page you visit gets pushed on, and "back" pops the most recent one off.

```python runnable
history = []
history.append("home")      # push
history.append("search")    # push
history.append("product")   # push

print(history.pop())         # pop - "product", the most recently added
print(history.pop())         # pop - "search"
print(history)                # "home" is all that's left
```
```console
product
search
['home']
```
*What just happened:* `append` and `pop` (with no index) both operate on the *end* of the list - which is
exactly the "cheap" end from Phase 1. That's why a plain list makes a perfectly good stack: push and pop are
both `O(1)`, no shuffling required.

💡 **Key point.** Reach for a stack whenever "undo the most recent thing" is the operation you need: undo
history, matching brackets/parentheses, backtracking through a maze, or - not coincidentally - how your
program's own function calls are tracked (the "call stack" you've heard of in every stack-overflow error).

## Queue: first in, first out (FIFO)

**What it actually is.** A queue adds at one end and removes from the *other* - whatever went in first comes
out first.

**Real-world analogy.** A line at a coffee shop. The first person to join is the first person served. A
print queue, a task queue, a chat's "next message to process" - all the same shape: process things in the
order they arrived.

```python runnable
from collections import deque

line = deque()
line.append("Ana")     # enqueue
line.append("Ben")     # enqueue
line.append("Cy")      # enqueue

print(line.popleft())   # dequeue - "Ana", the first one in
print(line.popleft())   # dequeue - "Ben"
print(list(line))        # "Cy" is still waiting
```
```console
Ana
Ben
['Cy']
```
⚠️ **Gotcha.** A plain Python `list` is a *bad* queue: `list.pop(0)` removes from the front, and removing
from the front of a list means shuffling every remaining item down one slot - the costly `O(n)` operation
from Phase 1's "inserting/removing in the middle" trap. `collections.deque` (double-ended queue) is built
specifically so *both* ends are cheap, which is why it's the right tool the moment you need FIFO behavior.

💡 **Key point.** Reach for a queue whenever fairness or arrival order matters: processing requests in the
order they came in, breadth-first traversal, any "first come, first served" scheduling.

## Linked lists: nodes chained by pointers

Every container so far has been a tight row of slots sitting next to each other in memory - that's *why*
index access is instant (Phase 1) and *why* inserting in the middle is costly (everything has to shuffle to
keep the row tight). A **linked list** breaks that assumption entirely.

**What it actually is.** Instead of one contiguous row, a linked list is a chain of separate **nodes**
scattered anywhere in memory. Each node holds a value *and a pointer to the next node* (see
[Pointers & References](/guides/pointers-and-references) if "a pointer" is new to you). To find anything, you
start at the first node (the "head") and follow the chain, one pointer at a time.

```mermaid
flowchart LR
  A["Mo | ●"] --> B["Tu | ●"] --> C["We | ●"] --> D["Th | ∅"]
```
*Each node points to the next; the last node's pointer is empty (often called `null`/`None`), marking the end.*

```python runnable
class ListNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def traverse(head):
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next        # follow the pointer to the next node
    return values

head = ListNode("Mo", ListNode("Tu", ListNode("We")))
print(traverse(head))
```
```console
['Mo', 'Tu', 'We']
```
*What just happened:* there's no single array underneath - just three separate `ListNode` objects, each
holding a value and a `next` pointer to the following one. `traverse` doesn't jump to "position 2"; it walks
`head → head.next → head.next.next`, following pointers until it hits `None`.

**Why insert here.** Because nodes aren't packed tightly, inserting a new one is just re-pointing two
pointers - nothing else in the chain has to move.

```python runnable
# insert "Fri" right after "Tu" - once you're at the right node, this is O(1)
node = head
while node.value != "Tu":
    node = node.next
node.next = ListNode("Fri", node.next)   # splice in: Tu -> Fri -> (old next)

print(traverse(head))
```
```console
['Mo', 'Tu', 'Fri', 'We']
```
*What just happened:* `node.next` used to point straight from `"Tu"` to `"We"`. Splicing in `"Fri"` meant
creating one new node whose `next` is the old `"We"` node, then pointing `"Tu"`'s `next` at it. Nothing
shuffled - contrast that with Phase 1's `list.insert(1, "X")`, which had to physically shove every later item
over.

**The trade you make.** A linked list flips the array's strengths and weaknesses:

| Operation | Array / List | Linked List |
|---|---|---|
| Access by index (`x[3]`) | **fast** - jump straight there | slow - must walk from the head |
| Insert/remove once you're *at* the right node | slow - shuffles everything after | **fast** - just re-point two pointers |
| Insert/remove at the very front | slow (shuffle) | **fast** |

⚠️ **Gotcha.** The catch that trips people up: *getting to* the right node in a linked list still means
walking from the head, one pointer at a time - there's no shortcut to "node number 500." So a linked list
only wins when you already hold a reference to the node you're inserting near (e.g., you're already walking
the chain) - if you have to search for that node first, you've paid the `O(n)` walk anyway. That's exactly
why arrays remain the default: most everyday code accesses by position or appends at the end, both of which
arrays already do for free.

## Putting these three together

- A **stack** restricts a list to one end (LIFO) - reach for it whenever you need "undo the most recent
  thing."
- A **queue** restricts a list to add-one-end/remove-other-end (FIFO) - reach for it whenever arrival order
  must be preserved.
- A **linked list** trades away fast index access for cheap insertion anywhere you already have a pointer -
  the mirror image of the array's trade-off from Phase 1.

None of these replace the list/map/set decision from Phase 3 - they're refinements you reach for once you
know *which specific access pattern* your code actually needs.

Push and pop a stack, enqueue and dequeue a queue - see both side by side:

```playground-ds
```

```quiz
[
  {
    "q": "What does LIFO mean for a stack?",
    "choices": ["First in, first out", "Last in, first out", "Items are sorted automatically", "Only one item can ever be stored"],
    "answer": 1,
    "explain": "The most recently added item is the first one removed - like a stack of plates."
  },
  {
    "q": "Why is `collections.deque` preferred over a plain `list` for a queue?",
    "choices": ["deque uses less memory", "list.pop(0) has to shift every remaining item, which is O(n); deque makes both ends O(1)", "list can't hold strings", "deque sorts items automatically"],
    "answer": 1,
    "explain": "Removing from the front of a list means shuffling everything after it down one slot - deque is built so both ends are cheap."
  },
  {
    "q": "Why is inserting into the middle of a linked list cheap once you're at the right node, but array insertion isn't?",
    "choices": ["Linked lists are always shorter", "A linked-list insert just re-points two pointers; an array insert has to shuffle every later item", "Arrays don't support insertion at all", "Linked lists store data in sorted order automatically"],
    "answer": 1,
    "explain": "Nodes aren't packed contiguously, so splicing one in only touches the two neighboring pointers - no shifting required."
  }
]
```