Describe and use arrays, records, lists, stacks, queues, trees and hash tables, and explain their operations and uses.

What this dot point is asking

WJEC wants you to know the common data structures, how their operations work, and the situations each suits. You should be able to trace operations on a stack and queue by hand, describe how a binary tree stores ordered data, and explain why a hash table gives fast lookup. Data structures sit at the centre of Unit 1 because algorithms (the next topic) operate on them, so a clear grasp here pays off across the whole paper.

The answer

Arrays and records

An array is ideal when you have many items of one type and want fast access by position; a record is ideal when you want to keep related but differently typed facts about one thing together, such as a student's name (text), age (integer) and average mark (real).

Stacks and queues

Stacks model anything that unwinds in reverse order, such as the call stack that stores return addresses or an undo history. Queues model anything served in arrival order, such as a print queue or keyboard buffer. Both are abstract data types: defined by their operations rather than their underlying storage.

Lists, trees and hash tables

A list is an ordered sequence that can usually grow and shrink at run time, often built from nodes linked by pointers. A binary tree stores data so each node has at most two children, with smaller keys to the left and larger to the right, which keeps searching, inserting and ordered traversal efficient.

A hash table stores each item at a location computed from its key by a hash function, giving near constant-time lookup. When two keys hash to the same slot, a collision occurs and is resolved by chaining (a linked list at the slot) or by probing for the next free slot.

Examples in context

Example 1. The call stack during recursion

When a program calls a procedure, the return address and local variables are pushed onto a stack. A recursive routine pushes a new frame for each call; as each call finishes, its frame is popped. This LIFO behaviour is exactly why a runaway recursion causes a stack overflow, and it shows the stack is not an academic toy but the mechanism behind procedure calls.

Example 2. A print queue in an office

Documents sent to a shared printer join a queue at the rear and are printed from the front in arrival order. If the structure were a stack instead, the most recently sent document would print first and early jobs could wait indefinitely, so the FIFO discipline of a queue is what makes the system fair.

Example 3. Indexing a dictionary with a hash table

A spell-checker stores its word list in a hash table so that checking whether a word exists is near instant, regardless of how many thousands of words it holds. A binary search of a sorted list would be slower, and a linear search slower still, which is why hashing is the standard choice when fast membership tests matter more than keeping items in order.

Try this

Q1. State whether a stack or a queue would be used to reverse the order of a sequence of items, and justify your choice. [2 marks]

• Cue. A stack: pushing then popping every item returns them in reverse order because of its LIFO behaviour.

Q2. A binary search tree contains the keys 60, 40, 80, 30. State where the key 35 would be inserted. [2 marks]

• Cue. 35 is less than 60 then greater than 40 then greater than 30, so it becomes the right child of 30.