S6 ICT | Data Structures: Arrays, Linked Lists, Stacks, Queues, Trees and Graphs

Data structures is the chapter in S6 ICT that joins how data is stored to how fast a program runs. The same task solved with an array and with a linked list can look identical in code yet differ by tens of times in running time and memory. The exam does not test names; it tests whether you can use operation counts to explain why one structure wins in one situation.

What this chapter tests

• Linear structures: an array is contiguous and indexed from zero; a linked list joins nodes with pointers, so random access walks node by node while insertion at the head rewires a single pointer.
• Restricted linear structures: a stack is last in first out and serves undo, bracket matching and depth first search; a queue is first in first out and serves printer jobs and breadth first search.
• Trees: in a binary search tree every key on the left is smaller than the root and every key on the right is larger, so an in order traversal is sorted; level n holds at most two to the power n minus one nodes, and n levels hold two to the n minus one in total.
• Graphs: an adjacency matrix costs n squared cells and answers lookups fast, while an adjacency list stores two entries per undirected edge and saves memory for sparse graphs.

Three threads

The first is order: last in first out and first in first out follow from the number of openings, since a stack has one and a queue has an entry and an exit. The second is cost: every operation answers three numbers, how many elements shift, how many nodes are walked and how many comparisons are made. The third is degeneration: sorted input turns a binary search tree into a chain, so its height grows from log n to n and searching a thousand nodes falls from ten comparisons to a thousand.

Three habits earn marks: write out the real state of the structure after each push, pop or dequeue; turn Big-O into a concrete count, because a thousand items give a million steps at n squared and about ten thousand at n log n; and keep the unit straight, since a matrix is counted in cells, an adjacency list in entries and a queue in items.

Where marks are lost

• Treating array indices as starting at one, so the largest index of five items is written as five.
• Confusing the two orderings and calling a stack first in first out.
• Counting a circular queue as rear minus front and forgetting to add one.
• Claiming a linked list is simply faster without saying which operation, namely O(1) at the head and O(n) for random access.

Practice papers

Three papers build up in difficulty, ten items each, with answers and a one-line explanation; every figure is computed and checked by script, so they work as independent practice or as tutor preparation.

Need a tutor for this chapter? Register here and we match a tutor to your school’s progress.

Frequently asked

Why must a binary search start from sorted data?
Because it discards half the range on the assumption that everything beyond the middle is larger, and unsorted data can hide the target in the discarded half.

Matrix or adjacency list?
Judge by density. A graph with a hundred vertices and three hundred edges needs ten thousand cells as a matrix but only six hundred entries as a list, so a list wins for sparse graphs.