Data Structures and Their Operations
Beyond arrays and records, several standard abstract data types (ADTs) organise data for a given task. A stack is last-in-first-out (LIFO): Push adds to the top, Pop removes from the top. A queue is first-in-first-out (FIFO): Enqueue adds at the rear, Dequeue removes from the front; a circular queue implements this in a fixed-size array by wrapping front and rear back to index 0 with MOD, reusing freed space instead of shifting every element along. A linked list holds each item in a node containing its data and a pointer to the next node, allowing insertion and deletion without shifting elements. A binary tree holds each item in a node with up to two child pointers (left, right); traversing it in-order, pre-order or post-order visits every node in a defined sequence. A graph represents vertices connected by edges, directed and/or weighted, stored as an adjacency matrix or list.
Before you start
Make sure you're comfortable with these topics first:
Method
- Choose an ADT based on how the data actually needs to be accessed: LIFO order needs a stack, FIFO order needs a queue, arbitrary insertion/deletion without shifting needs a linked list, hierarchical data needs a tree, and networked/connected data needs a graph.
- For a stack, track a single 'top' pointer/index: Push increments it then writes the new value, Pop reads the current value then decrements it, and check IsEmpty before ever popping.
- For a circular queue implemented in a fixed-size array, track front, rear and a count, and calculate every new front or rear position with MOD (array size) so the pointer wraps back to index 0 once it passes the last index.
- For a linked list, trace pointers rather than array indices: to insert a node, point the new node at what its predecessor currently points to, then point the predecessor at the new node, in that order, so the rest of the list is never lost.
- For a binary tree, insert a new value by comparing it with the current node and moving left (smaller) or right (larger) until reaching an empty pointer, exactly as for a binary search tree.
- Traverse a binary tree recursively: in-order (left, node, right) visits a binary search tree's values in ascending order; pre-order (node, left, right) and post-order (left, right, node) visit the node itself at a different point in each pass.
- For a graph, choose the representation to match the density of connections: an adjacency matrix suits a densely connected graph and gives instant lookup of whether an edge exists; an adjacency list uses less memory for a sparse graph.
Worked example
A circular queue of size 5 (indices 0 to 4) starts empty, with front = 0, rear = -1 and count = 0. Enqueue adds an item at index (rear + 1) MOD 5 and increments count; Dequeue removes the item at index front, moves front to (front + 1) MOD 5, and decrements count. The following operations are carried out in order: Enqueue(10), Enqueue(20), Enqueue(30), Dequeue(), Enqueue(40), Enqueue(50), Enqueue(60), Dequeue(). State the final values of front, rear and count, and the contents of the underlying array.
- Enqueue(10), Enqueue(20), Enqueue(30) each increment rear by 1 (MOD 5) and store the value there: rear moves 0, 1, 2, storing queue[0]=10, queue[1]=20, queue[2]=30; count becomes 3.
- Dequeue() removes queue[front=0]=10 and moves front to (0+1) MOD 5 = 1; count decreases to 2.
- Enqueue(40), Enqueue(50) continue incrementing rear: rear moves to 3, then 4, storing queue[3]=40, queue[4]=50; count becomes 4.
- Enqueue(60) increments rear to (4+1) MOD 5 = 0, wrapping back to the start of the array: queue[0] is overwritten with 60 (the old value 10 there is no longer needed, since front has already moved past it); count becomes 5.
- Dequeue() removes queue[front=1]=20 and moves front to (1+1) MOD 5 = 2; count decreases to 4.
- Final answer: front = 2, rear = 0, count = 4, and the array holds [60, 20, 30, 40, 50] at indices [0,1,2,3,4], where the 4 logically valid elements, read from front to rear, are 30, 40, 50, 60.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1State whether a stack or a queue should be used to implement an 'undo' feature in a text editor, where the most recently made change should always be the first one undone.Show answer
Answer: A stack (LIFO), because the most recently pushed change needs to be the first one popped (undone).
Q2A stack-based array has top = 2 (0-indexed, meaning 3 items are currently stored). State the new value of top immediately after one more Push operation.Show answer
Answer: 3.
Q3In a singly linked list, state what a node's pointer field stores.Show answer
Answer: The memory address of (a reference to) the next node in the list, or a null/empty value if it is the last node.
Q4A circular queue of size 4 (indices 0 to 3) currently has rear = 3. State the index at which the next Enqueue will store its value, using (rear + 1) MOD 4.Show answer
Answer: 0 ((3+1) MOD 4 = 4 MOD 4 = 0, wrapping back to the start of the array).
Q5Define the term 'binary search tree'.Show answer
Answer: A binary tree in which, for every node, every value in its left subtree is smaller than the node's own value, and every value in its right subtree is larger (or, by convention, equal values go consistently to one side).
Q6State the order in which an in-order traversal (left, node, right) of a binary search tree visits its values.Show answer
Answer: Ascending (sorted) order.
Q7State whether an adjacency matrix or an adjacency list generally uses less memory to store a large, sparsely connected graph, and briefly explain why.Show answer
Answer: An adjacency list; an adjacency matrix always stores one cell for every possible pair of vertices whether or not an edge exists between them, whereas an adjacency list only stores an entry for each edge that actually exists.
Q8A queue implemented as a simple (non-circular) array, without shifting elements after a dequeue, is used heavily with many enqueue and dequeue operations. Explain the main problem this causes.Show answer
Answer: The front index keeps moving forward and the array positions before it are never reused, so usable space at the front of the array is wasted; eventually the rear index reaches the end of the array and no more items can be enqueued even though much of the array is logically empty, which is exactly the problem a circular queue solves by wrapping the pointers back to index 0.
Exam-style questions
Written in the style of a A Level Computer Science exam paper, with a full mark scheme.
A stack, implemented as an array with a 'top' index, currently holds the values [5, 9, 2] with top = 2 (0-indexed). State the sequence of values returned by two consecutive Pop operations, and state the value of top after both have completed.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 3 available
Insert the following values, in order, into an empty binary search tree: 8, 3, 10, 1, 6, 14, 4, 7, 13. Draw (or describe) the resulting tree, then state the sequence produced by a pre-order traversal (root, then left subtree, then right subtree).
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
A directed, weighted graph has vertices A, B, C and D, and edges A to B (weight 4), A to C (weight 2), B to D (weight 5) and C to D (weight 1). Draw (or describe) the adjacency matrix for this graph, using rows for the 'from' vertex and columns for the 'to' vertex, with 0 representing 'no edge'.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
See real A Level Computer Science past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the data structures and their operations worksheet pack - 11 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on data structures and their operations, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.