Arrays, linked lists, stacks, queues and hash tables — the workhorses. Build each one yourself, then use the built-in version forever after.
Implement each one from scratch once, then learn the version your language already provides. The point of building it is not to use your version — it is that you can never again treat the built-in one as magic.
Why this stage exists
These five structures cover the large majority of what you will actually reach for as a working engineer. alone are probably the most-used non-trivial structure in software.
NeetCode 150 · complete category
Arrays & Hashing practice lab
Use direct indexing when position matters and a set or map when fast memory of earlier values matters.
9 problems
Pattern first
Hash maps: remember, then retrieve
bucket 0
bucket 1
bucket 2cat
bucket 3
bucket 4
Hash(cat) → bucket 2 — jump straight to one bucket instead of scanning a list.
Naive
A list lookup scans from the first item each time.
Why this works
Hashing sends a key to one bucket, making a bucket check average O(1).
Picture itWalking a line of people and asking each one to turn around and face the person behind them.
Conceptual blueprint
Carry three handles — previous, current, and the saved next — and flip one arrow per step.
Animated dry-runFrame 1
1 / 6
01▲ current
12
23
34
45
current at index 0
previous starts as None because the old head becomes the new tail, pointing at nothing.
previousNone
Lookup structure
arrows → 1→2→3→4→5
1def reverse(head):
2 previous = None
3 current = head
4 while current:
5 following = current.next
6 current.next = previous
7 previous = current
8 current = following
9 return previous
Check yourself before reading onCost it first
What does rewiring in place buy over copying the values out and rebuilding?
Find the bug
Why does this stop after one node?
def reverse(head):
previous = None
current = head
while current:
current.next = previous
following = current.next
previous = current
current = following
return previous
Predict the next step
current is node 2 and previous is node 1. What must be saved before 2's arrow is flipped?
Fill in the blanks
Recall each hidden line before revealing it. 3 left.
1def reverse(head):
2 previous = None
3 current = head
4 while current:
5
6
7 previous = current
8 current = following
9
Why the naive approach falls short
Copy every value into a list, reverse that, and rebuild the chain.
Why the optimized approach works
Each node's new successor is the node just visited, so one pass with a trailing handle is enough.
Time
O(n) — one pass, one arrow flipped per node.
Space
O(1) — three handles, no copy of the list.
What you are learning — 6 topics
Arrays and dynamic arrays
A numbered row of nearby slots, so the computer can jump straight to any slot.
Reach for it whenUse one when you read by position or append often; choose a or linked structure when you constantly add or remove at the front.
Think of it likeA row of numbered pigeonholes. Because they are evenly spaced and numbered, you can walk straight to number 47 without checking any of the others.
The items sitting next to each other in memory is the whole trick. The computer can work out exactly where item 47 lives with one multiplication, so reaching any position costs the same regardless of size.
Growing is where it gets interesting. When the block is full the does not extend in place — it allocates a bigger block, usually double the size, copies everything across, and abandons the old one. That copy is expensive, but because the size doubles it happens rarely, and the cost averaged over all the appends stays small. That averaging is what means.
Syntax you can use
nums = [10, 20, 30]
Creates an ordered, indexable run of values.
nums[1]
Reads an item by position in O(1) time.
nums.append(40)
Adds an item at the end, the usual cheap array operation.
nums[1:3]
Takes a slice from index 1 up to, but not including, 3.
Notice the empty capacity after the live values; that spare room is what makes most appends constant-time.
Several ways to see it
Its shapeAn index is arithmetic on an address
Equal-size slots sit consecutively, so slot `i` begins at base address plus `i` times slot width. The machine can jump there without looking through slots zero to `i - 1`.
What the machine doesGrowth happens in rare bulk copies
When capacity fills, a allocates a larger block, copies every reference, and releases the old block. Most appends touch one slot; the occasional expensive resize is spread across the cheap ones.
What it costsLocality can beat a prettier complexity table
Sequential array slots arrive in cache-friendly chunks, so scanning them uses hardware efficiently. A has the same O(n) scan on paper but often waits on scattered memory at every node.
In the wild
Python list — stores a resizable array of object references and grows by allocating more room.
WebGL buffers — store and pixel data in indexed, contiguous sequences for fast access.
PostgreSQL result sets — clients commonly receive ordered rows as an array-like sequence.
Commonly gets misread as
"Appending is always a copy." Correction: occasional resize copies are spread across many cheap appends.
"Arrays are slow because inserts cost O(n)." Correction: indexed reads and sequential scans are often extremely fast.
What it costsReaching a position: O(1). Searching for a value: O(n). Adding at the end: O(1) amortised. Inserting or deleting at the front: O(n).
A chain of separate boxes where each box tells you where the next one is.
Reach for it whenUse one when you already hold the item to splice and order changes often; use an array when you need fast access by number.
Think of it likeA treasure hunt. Each clue tells you where the next clue is. You cannot skip to the fifth clue without following the first four.
This is the Node chaining exercise from week 13, formalised. A singly linked list has each node pointing forward only. A doubly linked list has each node pointing both forward and back, which costs more memory and lets you walk in either direction. A circular one has the last node point back at the first.
The trade against arrays is exact and worth memorising. Arrays give instant access by position and slow insertion in the middle. Linked lists give slow access by position and instant insertion once you are holding the right node — because you only rewire two references, with no shuffling.
Syntax you can use
node.next = Node(value)
Links a new node after the current one.
new.next = head
head = new
Inserts a node at the front in O(1) time.
current = head
while current is not None:
current = current.next
Walks every node from the head to the end.
slow = fast = head
Starts slow and fast pointers, useful for detecting a cycle or finding a middle.
Notice that logical neighbours are separated by gaps; the arrows, not physical adjacency, preserve order.
Several ways to see it
Its shapeOrder lives in arrows, not addresses
Nodes may be scattered anywhere in memory; each next reference supplies the sequence. Rewiring two references can remove or insert a known node without shifting the rest.
What it costsCheap splicing is useless if finding the splice is expensive
Insertion beside a node you already hold is constant-time, but locating position 500 still requires following 500 links. Arrays win when access by position dominates; lists win only when the traversal cost is already paid.
How it breaksOne lost link can discard the entire tail
Assigning `current.next` before saving its old value may make the remaining chain unreachable. updates should be written in a deliberate order and tested at the empty list, head, tail, and single-node cases.
In the wild
Redis — uses linked-list-like quicklists to support efficient list operations at both ends.
Linux kernel — uses intrusive linked lists to connect scheduler, cache, and device records.
Python functools.lru_cache — uses a linked ordering alongside a dictionary to track recent use.
Commonly gets misread as
"Linked lists make insertion fast anywhere." Correction: finding the insertion point is still linear unless you already have its node.
"They replace arrays." Correction: pointer chasing makes indexed reads and scans worse.
What it costsReaching position n: O(n). Inserting or deleting when you already hold the node: O(1). Searching: O(n).
A deliberately one-ended pile: the most recently added thing is the next thing you can take.
Reach for it whenUse it when work must be undone in reverse order or when you need to remember the path you took through nested work.
Think of it likeA pile of plates. You take the one you put down most recently.
Three operations and no more: push to add, pop to remove and return the top, peek to look without removing. That deliberate poverty is the point — the restriction is what makes it useful.
You are already using one constantly. The from week 14 is a stack: each function call pushes, each return pops. Understanding stacks and understanding are the same understanding approached from two directions.
Syntax you can use
stack = []
Creates a stack using a Python list.
stack.append(value)
Pushes value onto the top.
value = stack.pop()
Pops and returns the most recently pushed value.
if stack:
Checks that a stack has something to pop.
Notice that C leaves first because all work happens at the same end where C arrived last.
Several ways to see it
Why it existsNested unfinished work demands reverse order
When one task starts another, the inner task must finish before the outer one can resume. A last-in, first-out stack is the minimal structure that remembers that nesting.
What the machine doesPush and pop touch one boundary
An array-backed stack appends and removes at the end, so existing items do not shift. The top item is both the next value returned and the only value removed.
Against the alternativeA stack remembers depth; a queue remembers arrival
Use a stack for undo, parsing nested delimiters, or where the newest possibility comes next. Use a queue when older work must not be starved by newer arrivals.
In the wild
JavaScript engines — use call stacks to remember active function calls and where each returns.
VS Code — keeps undo operations in reverse chronological order.
TypeScript parser — tracks nested delimiters and parser state while reading source.
Commonly gets misread as
"A stack is just any list." Correction: its one-end rule is what guarantees simple, constant-time operations.
"Recursion has no stack." Correction: recursive calls use the program's call stack.
A queue gives work its turn; a deque lets either end take a turn; a lets urgency cut the line.
Reach for it whenUse a queue for arrival order, a deque for both-end operations, and a priority queue when the next job is the most important rather than the oldest.
Think of it likeA queue is the line at a shop. A priority queue is a hospital waiting room, where the most urgent patient is seen first no matter who arrived when.
Queues are the natural structure whenever fairness or arrival order matters. Job queues, print spoolers, and requests waiting for a web server are all queues.
A circular buffer is a queue built into a fixed block of memory that wraps around when it reaches the end, reusing space rather than growing. It is what you want when memory is limited and old data can be discarded — streaming audio is the standard example.
Syntax you can use
from collections import deque
Imports Python's efficient queue type.
queue = deque([start])
Creates a queue with its first item already waiting.
queue.append(item)
Adds item at the back of the queue.
item = queue.popleft()
Takes the oldest item from the front in O(1) time.list.pop(0) shifts every remaining item. Use deque when you remove from the front in a loop.
Notice that queue work enters at the top but leaves at the base, preserving arrival order.
Several ways to see it
Its shapeThe removal rule defines three different structures
A queue opens at opposite ends, a deque opens at both ends, and a priority queue removes the best-ranked item regardless of arrival position. Their APIs look related, but their promised order is the real distinction.
What the machine doesA deque avoids shifting the whole line
Python's deque stores blocks that can grow at either boundary, so removing the leftmost item does not move every remaining reference. `list.pop(0)` performs that shift and becomes costly as the queue grows.
How it breaksPriority does not automatically settle ties
Heap entries with equal priorities may compare their payloads, which can fail or produce an unwanted order. Add a monotonically increasing counter when equal-priority work must remain first-come, first-served.
In the wild
Node.js event loop — processes scheduled callbacks through task queues.
Linux scheduler — uses priority-oriented run queues to select work.
Dijkstra's algorithm — uses a priority queue to repeatedly expand the nearest unsettled node.
Commonly gets misread as
"A priority queue keeps everything sorted." Correction: it only makes the next highest-priority item cheap to access.
"A Python list is a fine queue." Correction: removing its first item shifts every later item.
What it costsQueue and deque: adding and removing at either end is O(1). Priority queue: adding and removing the top item is ; looking at the top is O(1).
A fast label-to-slot lookup desk that remembers where it put each thing.
Reach for it whenUse one for exact lookups, membership checks, counts, or deduplication; choose a tree when you need sorted order or ranges.
Think of it likeA cloakroom that works out your peg number from your surname. Nobody searches the rails — the name tells you where to look.
A takes any label and produces a number. The same label always produces the same number. Take that number, divide by the number of slots, keep the remainder, and you have a slot to store the item in. Retrieval repeats exactly the same calculation, so it goes straight to the right slot.
Two different labels can produce the same slot. This is a collision, and it is not a bug — it is unavoidable, because there are more possible labels than slots. The table needs a plan for it. The most common plan is chaining: each slot holds a small list, and anything landing there joins that list.
Syntax you can use
seen = set()
Creates a hash set for fast membership checks.
counts = {}
Creates a dictionary, Python's hash table.
counts[value] = counts.get(value, 0) + 1
Counts occurrences without a separate missing-key branch.
from collections import defaultdict
Imports a dictionary that creates a default value for new keys.
groups = defaultdict(list)
Creates buckets that begin as empty lists.
Notice that fast lookup survives a collision only because the shared bucket keeps both keys for an equality check.
Several ways to see it
What the machine doesHashing narrows the search; equality finishes it
A hash sends a key toward a small region of the table, but different keys can share that destination. The table must still compare keys within a collision chain or probe sequence before returning a value.
What it costsEmpty space is part of the speed budget
As load factor rises, collisions and probe lengths rise with it. Resizing spends O(n) time and extra memory occasionally so ordinary lookup can remain close to O(1).
How it breaksHostile collisions can erase the constant-time promise
If many keys produce the same placement, operations degrade toward a linear scan. Real runtimes randomize string hashing and use collision strategies because public input can otherwise turn a dictionary into a denial-of-service target.
In the wild
Python dict — maps hashed keys to values for average constant-time lookup.
Redis — stores hash values as field-to-value maps.
Git — uses content hashes as stable object identifiers in its object store.
Commonly gets misread as
"Hashes never collide." Correction: collisions are normal and the table must resolve them.
"A hash table is always O(1)." Correction: that is the expected case with good hashing and controlled load.
What it costsLookup, insert and delete are O(1) on average, and O(n) in the worst case if hashing goes badly.
Text is a sequence of characters, and in Python each finished string is a value you replace rather than edit in place.
Reach for it whenUse strings for finished text; collect many changing pieces in a list and join once instead of repeatedly rebuilding a growing string.
Because strings are , adding to one in a loop is a trap. Each addition builds an entirely new string and copies the old contents in, so a loop adding to a string ten thousand times does an enormous amount of copying. That is O(n²) hiding in three innocent-looking lines.
The fix is to collect the pieces in a list and join them at the end. One pass, one allocation.
Syntax you can use
word = "algorithm"
Creates an immutable sequence of characters.
word[::-1]
Returns the characters in reverse order.
word.lower()
Makes a lower-case copy before a case-insensitive comparison.
"".join(chars)
Builds one string from character pieces.Repeated text += piece in a large loop keeps making new strings; collect pieces and join once.
word.isalnum()
Checks that every character is a letter or number.
Notice that code-point slots are contiguous, yet two slots can combine into one symbol on screen.
Several ways to see it
Its shapeVisible characters are not always one indexed unit
Unicode text may encode a displayed symbol from multiple code points, such as a letter plus a combining accent. Python indexes code points, so slicing can separate pieces a reader perceives as one character.
What it costsRepeated concatenation can recopy a growing prefix
Strings are immutable, so producing a changed string generally allocates new storage. Accumulate many fragments in a list and call `''.join(parts)` once to make the total copying predictable.
Against the alternativeBytes preserve encoding; strings preserve text
Network and file boundaries carry bytes, while application logic usually wants decoded `str` values. Decode once at entry and encode once at exit so the chosen character encoding stays explicit.
Reading about this stage is not the same as finishing it. Type every one of these from a blank file rather than copying — the writing is the part that teaches.
Build a dynamic array
Start with a fixed-size block. Implement get, set and append. When append runs out of room, allocate a block twice the size, copy everything, and carry on. Then count how many copies happen across 1,000 appends and see the amortised cost for yourself.
Build singly and doubly linked lists
Insert at the front, insert at the end, delete by value, and find the length. Then the four classic problems: reverse the list, detect whether it loops back on itself using the tortoise-and-hare method, find the middle node in one pass, and merge two sorted lists.
Build a stack and a queue
Build each one twice — once on top of an array, once on top of a linked list — and compare which operations are cheap in each. Then use your stack to write a bracket matcher.
Build a hash map with chaining
The big one. Write your own hash function, use the remainder operator to pick a slot, handle collisions with a list at each slot, and resize when the table gets more than about 70 percent full. Then test it with keys designed to collide and watch performance degrade. This is the most valuable single exercise in the roadmap.
The standard hash-table problems
Two-sum, group anagrams, first non-repeating character, and subarray sum equals K. Each teaches the same lesson from a different angle: trading memory for speed by remembering what you have already seen.
You are done with this stage when
Exit checkYou can implement a dynamic array, a singly and a doubly linked list, a stack, a queue and a hash map with chaining — from a blank file, without looking anything up. Around 60 problems solved.
If you cannot do this, repeat the stage rather than moving on. Nothing later gets easier by skipping it.
This stage corresponds to DSA Phase 2 — Linear Data Structures in the source roadmap.