Exam Board:
OCR A-Level
Specification:
Computer Science H446
3.1e - Data Structure Algorithms
Watch on YouTube:
Stacks
Queues
Linked Lists
Trees
Tree traversal
Being able to read, trace and write code for data structure algorithms (stacks, queues, linked lists and trees) is vital.
Stacks
A stack stores data in a last in, first out (LIFO) order, meaning the most recently added item is the first one to be removed. It works much like a stack of plates - you can only add or remove from the top.
​
Two integral functions are push and pop. The push operation adds (or “pushes”) a new item onto the top of the stack. The pop operation removes (or “pops”) the item from the top of the stack.
​
Stacks are commonly used in undo features, function calls and expression evaluation, where tracking the most recent item first is important.
Queues
A queue stores items in a first in, first out (FIFO) order, meaning the first item added is the first one removed.
​​​
New items are added at the rear of the queue using an enqueue operation, and items are removed from the front using a dequeue operation.
​
Queues are often used in task scheduling, print spooling and data buffering, where operations must occur in the same order they were requested.
Linked Lists
A linked list is a dynamic data structure made up of a series of elements called nodes, where each node contains data and a pointer to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations, making it easy to insert or delete items without having to shift other elements.
​
The head is the first node in the list, and the last node usually points to null, indicating the end of the list.
Trees
A tree is a hierarchical data structure made up of nodes connected by branches, starting from a single root node. Each node can have child nodes, and nodes without children are called leaf nodes. Trees are useful for representing data with natural hierarchies, such as file systems or organisational charts.
​
A binary search tree is a special type of tree where each node has at most two children - a left and a right. All values in the left subtree are smaller than the parent node, and all values in the right subtree are larger. This structure allows for efficient searching, insertion and deletion of data, often much faster than in lists or arrays.
Tree Traversal
'Tree traversal' refers to the method used to visit every node in a tree data structure in a specific, organised order.
​
Depth-first (also called post-order) traversal explores a tree by moving as far down one branch as possible before backtracking, visiting nodes in a deep, top-to-bottom manner. It uses a stack to keep track of nodes still to explore, pushing new branches onto the stack and popping them when backtracking.
Breadth-first traversal explores the tree level by level, visiting all nodes on one level before moving down to the next. It uses a queue to hold nodes in the order they should be visited, ensuring the traversal expands outward evenly from the root.
Questo's Key Terms
Stacks and Queues: stack, queue, last in first out (LIFO), first in first out (FIFO), push, pop, enqueue, dequeue, pointer
Linked Lists: linked list, null
​
Trees: tree, binary tree, binary search tree, root node, branch, depth-first traversal, breadth-first traversal
Did You Know?
Spotify playlists work like linked lists because each song links to the next, allowing tracks to be added, removed or reordered instantly without reshuffling the whole playlist. This makes the app fast and efficient even when handling huge playlists with thousands of songs.
