Data structures and algorithms in C
You write arrays, lists, stacks, queues, hash tables and trees from scratch in C, measure their cost and test them without leaving memory bugs.
Level 201 · 21 lessons · 21 practice labs
Lessons
Linear structures
- A growable array: capacity and resizing
- A doubly linked list: insert, delete, traverse
- A stack: with an array and a list
- Queues and the ring buffer
- A generic container with void*
- Short task: an undo stack
Searching and sorting
- Complexity: measuring cost with Big O
- qsort and bsearch with comparison functions
- Writing merge sort
- Quicksort and choosing a pivot
- Binary search and boundary bugs
- Short task: compare three sorts
Key-value and trees
- Hash functions: FNV-1a and distribution
- A hash table with chaining
- A table that resists collision flooding: seeded hashing
- A binary search tree: insert, find, delete
- Tree traversal: pre-, in- and post-order
- The heap data structure and priority queues
- Graphs: adjacency lists and breadth-first search
- Short task: build a word index
Capstone
- Capstone: an IP counter built on a hash table
Practice labs
- A growable integer array: Write an integer array that doubles its capacity when full and passes the push and get tests.
- A ring buffer for telemetry: Write a ring buffer that keeps the last 64 readings and overwrites the oldest when full, testing the wrap-around.
- Checking bracket balance with a stack: Check the balance of (), [] and {} in a config expression with a stack and return the position of the first error.
- Back and forward navigation history: Write a history structure supporting back and forward navigation with two stacks and no memory leaks.
- bsearch in a sorted price list: Write a function that finds a price by product code in a sorted array with bsearch and test a missing code.
- Fixing a boundary bug in binary search: Fix a binary search that returns the wrong position with repeated values so it finds the first match.
- Replacing a slow sort with merge sort: Replace an insertion sort that takes minutes on a hundred thousand records with merge sort and measure the time.
- Finding the median without a full sort: Find the median of response times with quickselect, working correctly on sorted and repeated inputs too.
- Measuring bucket spread with FNV-1a: Write the FNV-1a hash function and print how a thousand keys spread across buckets as a histogram.
- Deleting safely from a chained table: Write the delete operation of a chained hash table so records at the head and middle of a chain are removed correctly.
- Growing the table as it fills: Write a resize that doubles the buckets and rehashes when the load factor passes 0.75, without leaks.
- A table that resists collision flooding: Move a fixed-hash table to a randomly seeded hash and show a prepared list of colliding keys no longer slows it down.
- The height of a binary search tree: Write recursive functions that return a BST's minimum, maximum and height.
- Deleting a node with two children: Complete BST deletion for the two-children case and test that the in-order output stays sorted.
- Scheduling tasks with a priority queue: Write a scheduler that picks the earliest task with an array-based min-heap, keeping insertion order for equal times.
- Finding the fewest hops with BFS: Compute the fewest hops between network devices given as an adjacency list using BFS.
- Counting connected components: Find the number of connected groups in a friendship graph with DFS.
- Finding a build order with topological sort: Derive a valid build order from module dependencies and report the modules in the cycle if there is one.
- Adding insertion and shrinking to a growable array: Add insert-in-the-middle and remove operations to a growable integer array, halving capacity when it falls below a quarter full and losing no data when realloc fails.
- Finding the first bad build by bisection: Write a function that finds the first build where the test fails in an ordered build list using the fewest trials, also returning correctly when no build is bad and when all are.
- Sorting records stably: Sort a small array of student records by grade with insertion sort, keeping records with equal grades in their input order.
About this course
You write arrays, lists, stacks, queues, hash tables and trees from scratch in C, measure their cost and test them without leaving memory bugs.
What you will learn
- Linear structures
- Searching and sorting
- Key-value and trees
- Capstone
Prerequisites
Finishing the level 101 courses of the same path, or knowing those topics, is enough.
Lab environment
Lessons run in your own Kali Linux terminal that opens in the browser. Nothing to install; the lab starts clean in every lesson.
Frequently asked questions
- Is this course right for my level?
- The course is at level 201; it assumes you know the topics of the lower-level courses.
- Is there anything to install?
- No. Every lesson runs in your own lab environment that opens in the browser.
- How do lessons work?
- Each lesson has 8 to 10 steps and a short quiz. Early steps show the command to type, later steps give less help; if two attempts fail, the solution opens.
- Can I try it for free?
- Yes. The first three lessons of every course are free.