Data Structures — OCR A-Level Computer Science
Data Structures explained
Data Structures covers 3 specification points, including (a) Arrays (of up to 3 dimensions), records,… and Linked-list, graph (directed and undirected),….
Read the full explanation
Open a point below for its explanation and revision guidance.
(a) Arrays (of up to 3 dimensions), records, lists, tuples.
This statement asks you to recognise arrays of up to three dimensions, records, lists and tuples. An array stores elements of one data type under one identifier, reached by index: a one-dimensional array is a row, a two-dimensional array is a grid of rows and columns, and a three-dimensional array adds a further index. A record groups fields of different data types under one name, such as a student record with a text name, an integer age and a Boolean enrolment flag. A list is an ordered collection whose length can change as items are added or removed. A tuple is an ordered collection, often of mixed types, whose values are fixed once created. Keep any array example within three dimensions.
(b) The following structures to store data: linked-list, graph (directed and undirected), stack, queue, tree, binary search tree, hash table.
Statement (b) requires you to know seven structures: linked list, directed and undirected graph, stack, queue, tree, binary search tree and hash table. Learn each by its defining rule. A linked list is a chain of nodes, each holding data and a pointer to the next node. A graph has vertices joined by edges; directed edges have a direction, undirected edges do not. A stack is last-in, first-out; a queue is first-in, first-out. A tree is a hierarchy with a root and child nodes. In a binary search tree, left descendants hold smaller values and right descendants hold larger values. A hash table uses a hash function to turn each key into a storage position. Practise naming each from a description.
(c) How to create, traverse, add data to and remove data from the data structures mentioned above. (NB this can be either using arrays and procedural programming or an object-oriented approach).
Statement (c) asks you to know how to create, traverse, add data to and remove data from each structure in (b). Take a linked list: to create one, set head to null; to traverse, start at head and follow each next pointer until null; to add, relink the pointers around the new node; to remove, point the previous node past the deleted one. For a stack in an array with a top index, pushing increases top then stores the item, and popping reads the item at top then decreases it. The NB allows either arrays with procedural programming or an object-oriented approach, so an operation may be a procedure acting on arrays or a method of a class. Trace each operation on paper.
Your focus
- Describe the structure of arrays of up to three dimensions and the indices needed to access an element.
- Explain how a record groups fields of different data types under one identifier.
- Distinguish lists from tuples by their ability to change length and contents.
Show all 9 objectives
- Name each of the seven structures listed in the statement.
- Describe the defining rule of each structure.
- Identify the correct structure from a short description.
- Write the steps to create and traverse a linked list.
- Trace push, pop, enqueue and dequeue on a worked example.
- Implement one structure using either arrays with procedures or a class.
Data Structures exam tips
Marking Points
- Identifies an array as a collection of elements of the same data type, accessed by index.
- Describes a two-dimensional array as having rows and columns, with each element addressed by two indices.
- Explains that a three-dimensional array needs three indices and keeps examples within the three-dimension limit.
- Explains that a record holds fields of different data types under one identifier, with a correct example.
- Distinguishes a list, whose length can change, from a tuple, whose values are fixed once created.
- Gives a relevant use for at least one structure, such as storing a set of student details or a grid of game squares.
- Defines a linked list as a sequence of nodes, each holding data and a pointer to the next node.
- Distinguishes a directed graph from an undirected graph by whether edges have a direction.
- Identifies a stack as last-in, first-out and a queue as first-in, first-out.
- Describes a binary search tree by smaller values in the left subtree and larger values in the right subtree.
- Explains that a hash table uses a hash function to map each key to a storage position.
- Explains create, traverse, add and remove for a linked list using head and next pointers.
- Describes stack push as increasing the top index before storing the item.
- Traverses a linked list from head, following next pointers until null.
- Removes a linked list node by relinking the previous node's pointer past it.
- Recognises that an operation may be written as a procedure on arrays or as a class method.
Examiner Tips
- 💡Give one concrete example for each structure, such as a student record with a name, an age and an enrolment flag.
- 💡State the key difference between a list and a tuple, namely whether the length and contents can change after creation.
- 💡When describing an array, state how many indices each element needs to be addressed.
- 💡Learn one defining sentence for each structure and check you can state it without notes.
- 💡When a question gives a description, match it to the structure's rule, such as last-in-first-out, first-in-first-out or parent-child hierarchy.
- 💡Sketch a small labelled diagram for graphs and trees so you can check the difference between vertices, edges, nodes and children.
- 💡Write out the pointer or index changes in order and check each step against a labelled diagram.
- 💡Consider edge cases for each operation, such as an empty structure, a single node or removing the head.
- 💡Implement the same operation both procedurally and as a class method to see how the logic stays the same.
Common Mistakes
- Claims that arrays can hold elements of mixed data types; correct this by stating that array elements share one data type, whereas records and tuples can mix types.
- Confuses records with arrays by describing a record's fields as accessed by numeric index; correct this by stating that record fields are accessed by name.
- Treats a tuple as changeable like a list; correct this by noting that a tuple's values are fixed once created.
- Uses a four-dimensional array as an example for this statement; correct this by keeping array examples to no more than three dimensions.
- Confuses stack and queue ordering; a stack removes the most recently added item, whereas a queue removes the oldest.
- Treats an undirected graph as having arrows on its edges; undirected edges have no direction.
- Describes a binary search tree as any binary tree; it also requires ordered values in its left and right subtrees.
- Describes a hash table as storing items in sorted order; it stores each item at a position computed by a hash function.
- Shifts every element when removing from a linked list; removal only requires pointer changes.
- Pops from a stack by removing the bottom item; pop removes the top item, the most recently pushed.
- Dequeues from the back of a queue; dequeue removes the front item, the oldest added.
- Assumes an object-oriented approach is required; the statement allows arrays with procedural programming.