Data Structures by Hand: Arrays, Stacks, Queues & Ring Buffers, Linked Lists, Binary Heaps, Search Trees and Sorting Passes

What you'll build

What you will be able to do

Each lab ends with a concrete result that you build yourself and the checker confirms, cell by cell.

• Read a value by its 0-based position, work out the memory address of an element from the start address and the element size, rebuild the array after an insert in the middle and count how many elements had to move.
• Continue a log of pushes and pops, track the stack size after every step, find the value on top with MAXIFS and INDEX, and use the depth of a line of brackets to find the first close bracket that has no opener.
• Run a fictional print queue stored in a ring buffer of five slots, move the tail and head pointers with MOD so they wrap around, count the jobs waiting and flag the moments when the buffer is full or empty.
• Follow next-pointers through a sorted linked list whose nodes are scattered over eight slots, read the value at every step, find where a new value belongs and set its next-pointer with INDEX and MATCH, then compare the work with an array.
• Read a min-heap stored in an array, calculate parent and child indices with INT and 2i + 1, then insert a new key at the end and sift it up round by round until its parent is smaller.
• Calculate the level of every node in a small search tree, follow the path of comparisons that places a new key, and compare the average search steps with a degenerate tree built from sorted input.
• Run bubble sort on six values pass by pass, count the swaps in each pass, count the shifts insertion sort needs for every element, and merge two sorted runs into one sorted list.
• Turn n into the number of tree levels, multiply a fictional hourly workload by the toy step counts of four structures with SUMPRODUCT, name the structure with the fewest steps and chart the totals.