Data Structures
Build every core data structure in C, node by node: arrays, linked lists, stacks, queues, trees, heaps, hash tables and graphs, with every pointer drawn as your code runs.
- Level
- Intermediate
- Time
- About 45 hours
- Modules
- 6
- Lessons
- 19
- Exercises
- 60
A data structure is a way of arranging data so that the operations a program needs are fast. The same thousand records can sit in an array, a linked list, a tree or a hash table, and that choice decides whether a search takes one step or a thousand. This course builds each structure from nothing in C, so you see exactly what it costs and why.
You start with arrays and the idea of counting steps, then build linked lists, stacks and queues, and move on to trees, heaps, hash tables and graphs. The last part covers tries, union-find, segment trees and self-balancing trees. You can step through every example and watch the nodes and pointers change, and each exercise is checked against hidden tests. Every reference solution also compiles cleanly with a real C compiler.
What you will learn
- Describe the cost of an operation with Big-O
- Build linked lists, stacks and queues with pointers and with arrays
- Build and traverse binary trees, search trees and heaps
- Store and find data with hash tables
- Represent graphs, and traverse them breadth-first and depth-first
- Choose a suitable structure for a problem, and explain the choice
Skills you will gain
- Reasoning about time and memory costs
- Changing pointers without memory errors
- Thinking recursively about trees
- Testing edge cases such as empty and one-item structures
- Reading and drawing diagrams of linked structures
Before you start
- The C course, up to structs, pointers and malloc
- Writing and calling functions, including recursive ones
- School-level arithmetic, including powers of two
Where it is used
- Databases and search engines
- Operating systems, compilers and networks
- Maps, social networks and recommendation systems
- Technical interviews and programming contests
Modules
Module 1: Arrays and linked lists
How to count the cost of an operation, what arrays make cheap and expensive, and how linked lists give up indexing in return for easy insertion.
- 1
What a data structure is
A way to store data so the operations you need are fast, and how to count the cost of an operation.
- 2
Arrays: insert, delete and 2D arrays
Insert and delete by shifting, keep a count next to the capacity, and see how a 2D array sits in memory.
- 3
Singly linked lists
Append with a tail pointer, search, and delete a value while keeping the chain joined.
- 4
Doubly and circular linked lists
Nodes with prev and next pointers, removing a node in O(1), and a circle of nodes for the Josephus problem.
Module 2: Stacks and queues
Two structures that limit where items go in and come out, and the classic problems they solve: matching brackets, postfix expressions and fair waiting lines.
- 1
Stacks
Last in, first out: a stack on an array with push, pop, overflow and underflow.
- 2
Using stacks: brackets and postfix
Check that brackets match, evaluate postfix expressions, and turn infix into postfix.
- 3
Queues
First in, first out: a circular array queue that wraps around, and a linked queue with front and rear.
Module 3: Trees and heaps
Structures that branch: binary trees and their traversals, search trees that keep keys in order, and heaps that always know their smallest item.
- 1
Binary trees
Nodes with left and right children, preorder, inorder and postorder traversal, and recursive height and count.
- 2
Binary search trees
Smaller keys to the left, larger to the right: insert, search, and delete with its three cases.
- 3
Heaps and priority queues
A complete binary tree stored in an array: push with sift-up, pop the minimum with sift-down, and build a heap in O(n).
Module 4: Hash tables and graphs
Finding a value by its key in constant time with a hash table, and modelling connections with graphs that are searched breadth-first or depth-first.
- 1
Hash tables
A hash function picks a bucket: collisions handled by chaining and by linear probing, and why the table must not get too full.
- 2
Graphs
Vertices and edges, directed and undirected, stored as an adjacency matrix or as adjacency lists.
- 3
Graph traversal: BFS and DFS
Breadth-first search with a queue finds the fewest edges to every vertex; depth-first search goes deep with recursion.
Module 5: Choosing structures and finding bugs
How to match a problem to a structure by the operations it needs, and how to find the memory and index bugs that data structure code attracts.
Module 6: Advanced structures
Four structures for harder problems: tries for words, union-find for groups, segment trees for ranges, and AVL trees that keep themselves balanced.
- 1
Tries: prefix trees Intermediate
Store words letter by letter in a tree, so finding a word, or every word that starts with a prefix, costs only the length of the word.
- 2
Disjoint sets (union-find) Intermediate
Keep track of which items are in the same group, merging groups in almost constant time with union by size and path compression.
- 3
Segment trees and Fenwick trees Advanced
Answer range-sum questions and change single values in O(log n) each, where a plain array or prefix sums make one of the two slow.
- 4
AVL trees: self-balancing search trees Advanced
Keep a binary search tree's height close to log n by checking every node's balance after an insert and repairing it with rotations.
Projects
- A line editor with undo Build a small text editor that keeps the lines of a document in a doubly linked list, and can undo every change.
- A city route planner Build a program that reads a map of cities and roads, and finds the route with the fewest roads between any two cities.
What to learn next
- Algorithms Searching, sorting, recursion, greedy choices, dynamic programming and graph algorithms, with the cost of each one counted.
- Coding Interview Prep How coding interviews work, and the patterns behind most questions: hashing, two pointers, sliding windows, stacks, binary search, lists, trees, graphs, DP and backtracking.
- Competitive Programming Online judges and time limits, prefix sums, two pointers, binary search on the answer, greedy, DP and graphs with the STL, and contest math.