Describe and apply advanced data structures and algorithms: linked lists, trees and their traversals, recursion, and advanced searching and sorting.

What this dot point is asking

WJEC wants you to go beyond the AS data structures to advanced structures and the algorithms that operate on them: linked lists built from pointers, binary tree traversals (pre-order, in-order, post-order), recursion applied to structures, and advanced searching and sorting with their efficiency. This is core A2 content in Unit 3 and is examined both by tracing operations and by explaining how pointer-based structures work.

The answer

Linked lists and pointers

The trade-off is that you cannot jump straight to the nth item as you can with an array index; you must follow the pointers from the head. Linked lists suit data that changes size often and is processed in sequence.

Binary tree traversals

The choice of traversal matters: in-order gives sorted output, pre-order is used to copy a tree or produce prefix expressions, and post-order is used to delete a tree safely or evaluate postfix expressions.

Recursion on structures

Recursion is the natural way to process trees and linked lists: the structure is defined in terms of smaller versions of itself (a tree is a node with two subtrees), so the algorithm mirrors that definition with a base case (an empty subtree or null pointer) and a recursive case.

Advanced searching and sorting

Advanced algorithms are judged by efficiency: binary search is O(log n) on sorted data, merge sort and quicksort are O(n log n), far better than the O(n squared) of bubble or insertion sort on large data.

Examples in context

Example 1. A music playlist as a linked list

A playlist where songs are inserted and removed constantly suits a linked list: adding a track in the middle just reassigns two pointers, with no need to shuffle a large array. This shows why dynamic, frequently edited sequences favour linked structures over arrays.

Example 2. In-order traversal to print a sorted index

A binary search tree storing words can be printed alphabetically simply by an in-order traversal, with no separate sort. The structure does the ordering, so the algorithm is just a recursive walk, illustrating why the choice of traversal is tied to the task.

Example 3. Why quicksort beats bubble sort at scale

Sorting a million records with quicksort takes about a million times twenty operations; bubble sort takes about a million squared. The advanced algorithm is not merely tidier but transforms an impractical task into a quick one, which is the point of studying efficiency in Unit 3.

Try this

Q1. State which tree traversal outputs the values of a binary search tree in ascending order. [1 mark]

• Cue. In-order traversal (left, node, right).

Q2. State one advantage of a linked list over an array. [1 mark]

• Cue. It can grow and shrink dynamically, with insertion and deletion by reassigning pointers (no shifting of other items).