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.
What you are learning — 6 topics
Arrays and dynamic arrays
A block of memory holding items one after another with no gaps. A is one that quietly grows when it runs out of room. A Python list is a dynamic .
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 array 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.
Inserting at the front is genuinely slow: every existing item has to shuffle one place along. If you find yourself inserting at the front repeatedly, you want a different structure — which is the next concept.
One thing Big-O does not capture: arrays are unusually fast in practice because processors fetch memory in chunks, so walking through neighbouring items is far quicker than jumping around. This is why an array often beats a theoretically-equal structure in a real benchmark.
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).
Where you meet it in real softwareImage pixel buffers, query results, anything you read far more often than you rearrange.
A chain of small boxes, each holding a value and a reference to the next box. There is no jumping to position 47 — you have to walk there.
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 12, formalised. A singly 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.
The famous real use is the LRU cache, which throws away whatever was used least recently. It pairs a hash table with a doubly linked list: the hash table finds any item instantly, and the linked list lets you move that item to the front in constant time. Neither structure can do it alone. That combination is worth studying properly; it is a genuinely elegant piece of engineering.
In everyday Python you will rarely write one, because lists and collections. cover the ground. You build one here so that trees make sense, because a tree is the same idea with two next references instead of one.
What it costsReaching position n: O(n). Inserting or deleting when you already hold the node: O(1). Searching: O(n).
Where you meet it in real softwareLRU caches, undo and redo history, the free-space lists inside memory allocators, playlists that loop.
A collection where you only add to the top and only take from the top. The last thing in is the first thing out.
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 13 is a stack: each function call pushes, each return pops. Understanding stacks and understanding are the same understanding approached from two directions.
The classic exercise is checking whether brackets match in a piece of text. Push every opening bracket; on every closing bracket, pop and check it matches. If the stack is empty when you need to pop, or non-empty at the end, the brackets are wrong. That is roughly how a compiler catches your missing bracket.
Any depth-first exploration can be written with a stack instead of recursion — which is exactly how you avoid the recursion depth limit on a very deep structure.
What it costsPush, pop and peek are all O(1).
Where you meet it in real softwareThe function call stack, browser back buttons, undo in editors, bracket matching in compilers, evaluating arithmetic expressions.
A queue takes from the front and adds at the back — first in, first out. A deque allows both ends. A hands you the most important item next, regardless of arrival order.
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.
A priority queue is different enough to deserve care. It does not keep everything sorted, which would be expensive; it only guarantees that the most important item is cheap to get at. In Python this is the heapq module, and the structure underneath is a heap, which you meet properly in week 20.
One warning: using a plain Python list as a queue works but is slow, because removing from the front shuffles everything. Use collections.deque, which is built for exactly this.
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).
Where you meet it in real softwareTask queues, print spoolers, , request buffering in web servers, operating-system scheduling.
The machinery underneath a Python dictionary. It calculates where an item should live from the label itself, so finding it again is instant instead of a search.
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.
This is why the worst case is O(n). If a bad hash function put everything in one slot, every lookup would walk one long list, and you would have a slow linked list wearing a dictionary's clothes. Good hash functions spread things out, which is why the average case is the one people quote.
The table also has to grow. When it gets too full, collisions become frequent, so it makes a bigger table and rehashes everything into it — the same doubling trick as a dynamic array.
Building this from scratch is the centrepiece of this stage. Once you have written the hashing, the collision handling and the resizing, dictionaries stop being magic permanently, and you gain real intuition about when they are the wrong choice.
What it costsLookup, insert and delete are O(1) on average, and O(n) in the worst case if hashing goes badly.
Where you meet it in real softwareDatabase indexes, caches like Redis and Memcached, symbol tables inside compilers, deduplication, counting anything.
Text, stored as a sequence of characters. In Python a string cannot be changed once made — you can only build new ones.
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.
This is a good early example of a general lesson: the slow version and the fast version look almost identical, and only knowing what happens underneath tells you which is which.
What it costsJoining a list of pieces is O(total length). Repeatedly adding in a loop is O(n²) — avoid it.
Where you meet it in real softwareLog parsing, search, validation, breaking input into tokens.
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.