Data structures & algorithms
20 steps in 6 sets of C.
Data structures written out by hand, because in C that is the only way you get them. Sorting and searching, linked lists and stacks, trees and hash tables and heaps, then graphs.
The last set is bit manipulation, which is closer to the metal than anything else here and still turns up in real code more than you would expect. Twenty steps, and it doubles as an algorithms refresher.
Sorting & searching
- Bubble sortThe sort nobody should use and everybody should have written once.
- Insertion sortSorting in place by growing a sorted prefix.
- Binary searchHalve the range each step; a thousand items takes ten comparisons.
- QuicksortPartition around a pivot, then sort the two halves.
- Merge sortSplit, sort each half, then merge the two sorted runs.
Lists & stacks
- Linked list nodesThe self-referential struct behind a linked list.
- A doubly linked listTwo pointers per node, so insertion and removal need no traversal.
- Reversing a list in placeThree pointers walk the list once, flipping each link as they pass.
- An array-backed stackA fixed-capacity stack with push and pop.
- A queue on an arrayTwo indices chase each other around a fixed buffer.
Trees, tables & heaps
- A binary search treeInsert descends left or right; search follows the same path.
- Walking a treeIn-order, depth, and freeing: three recursions with the same shape.
- A hash table with chainingA bucket array of linked nodes: hash to a bucket, then walk the short chain.
- A binary heapThe array is the tree: children of i live at 2i+1 and 2i+2.
Graphs
- Breadth-first searchAn adjacency matrix, a queue of frontier nodes, and a visited array.
- Depth-first searchThe same graph, a recursive walk, and a different visiting order.
Bit manipulation
- Bit flagsSetting, clearing, and testing individual bits.
- Bit-counting tricksClassic bit hacks with & and subtraction.
Encore
- matrix.cMultiply two 3x3 integer matrices and print the result.
- hash_index.cA word index built on a chained hash table, with counts and a clean teardown.