EnglandComputer ScienceSyllabus dot point

What data structures store collections of data, and how do stacks, queues, linked lists, trees and hash tables differ?

Data structures: arrays, records, tuples and lists, the stack and queue abstract data types and their operations, linked lists, trees and graphs, and hash tables, including how each is used and its advantages.

An OCR H446 answer on data structures: arrays, records, tuples and lists, the stack and queue abstract data types with their operations, linked lists, trees, graphs and hash tables, including how each is used and its advantages and disadvantages.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Quick answer

A data structure organises a collection of data. An array is a fixed-size, ordered collection of items of the same type accessed by index. A record (struct) groups related fields of possibly different types. A tuple is an ordered, immutable collection. A list is an ordered collection that can usually grow and hold mixed types. A stack is last in, first out (LIFO), with push, pop and peek operations, used for the call stack and undo. A queue is first in, first out (FIFO), with enqueue and dequeue, used for scheduling and buffers. A linked list stores each item in a node with a pointer to the next, so insertion and deletion are easy but access is sequential. A tree is a hierarchical structure of nodes (a binary tree has up to two children per node). A graph is a set of nodes connected by edges, modelling networks. A hash table uses a hash function to map a key to an array index for near-constant-time lookup.

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

OCR wants the common data structures, arrays, records, tuples, lists, stacks, queues, linked lists, trees, graphs and hash tables, with how each works, its operations and its uses. Expect a "stack versus queue" question and a "how does a hash table work" question.

The answer

Arrays, records, tuples and lists

Stacks and queues

Linked lists, trees, graphs and hash tables

Key fact

A linked list stores each item in a node containing the data and a pointer to the next node, so the list can grow and shrink dynamically and insertion or deletion just re-links pointers (no shifting), but elements must be reached by following the chain from the start (no direct indexing). A tree is a hierarchical structure of nodes connected by edges, with a root and no cycles; a binary tree allows each node up to two children and underlies binary search trees. A graph is a set of nodes (vertices) connected by edges, which may be directed or weighted, modelling networks such as roads, social links or the web. A hash table stores key-value pairs by applying a hash function to the key to compute an array index, giving near- $O(1)$ insertion, deletion and lookup; a collision (two keys hashing to the same index) is handled by chaining (a list at each slot) or open addressing (probing for the next free slot).

Trace stack and queue operations

Starting empty, apply to a stack: push 5, push 8, pop, push 3. Then to a queue: enqueue 5, enqueue 8, dequeue, enqueue 3. Show the contents and what is removed.

step 1: Stack operations

push 5 -> [5]; push 8 -> [5, 8] (8 on top); pop removes the top, 8, leaving [5]; push 3 -> [5, 3]. The stack now holds [5, 3] with 3 on top, and 8 was removed (last in, first out).

step 2: Queue operations

enqueue 5 -> [5]; enqueue 8 -> [5, 8] (5 at front); dequeue removes the front, 5, leaving [8]; enqueue 3 -> [8, 3]. The queue now holds [8, 3] with 8 at the front, and 5 was removed (first in, first out).

step 3: Compare what was removed

The stack removed 8 (the most recently added); the queue removed 5 (the earliest added). Same operations, opposite removal order, because of LIFO versus FIFO.

step 4: Match to a use

The stack behaviour suits undo (reverse the most recent action first); the queue behaviour suits a print spooler (print jobs in the order they arrived).

Examples in context

The call stack manages every subroutine call and is why recursion uses memory. Operating-system schedulers and print spoolers use queues. Hash tables back dictionaries and database indexes for fast lookup. Trees structure file systems and binary search trees; graphs model maps and social networks (traversed by BFS and DFS). OCR links this to the searching and traversal algorithms that operate on these structures, and to choosing the right structure when designing the Programming Project.

Try this

Q1. State the order in which items leave a stack and a queue. [2 marks]

Cue. Stack: last in, first out (LIFO). Queue: first in, first out (FIFO).

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

Cue. It can grow and shrink dynamically, and insertion/deletion just re-links pointers without shifting elements.

Q3. Explain what a collision is in a hash table and one way to handle it. [2 marks]

Cue. A collision is when two different keys hash to the same index; it can be handled by chaining (a list at that index) or open addressing (probing for the next free slot).

Exam-style practice questions

Practice questions written in the style of OCR exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

OCR 20206 marksExplain the difference between a stack and a queue, naming the operations on each, and give one use of each in a computer system.

Show worked answer →

Stack (up to 3): a stack is a last in, first out (LIFO) structure; items are added (push) and removed (pop) at the same end (the top), and peek reads the top without removing it. Use: storing return addresses and local variables during subroutine calls (the call stack), or implementing undo.

Queue (up to 3): a queue is a first in, first out (FIFO) structure; items are added (enqueue) at the rear and removed (dequeue) from the front. Use: holding processes ready to run (scheduling), a print spooler, or buffering data such as keyboard input. Markers reward LIFO with push/pop for the stack, FIFO with enqueue/dequeue for the queue, and a valid use of each.

OCR 20216 marksExplain how a hash table stores and retrieves data quickly, what a collision is, and one way collisions can be handled.

Show worked answer →

How it works (up to 3): a hash table applies a hash function to a key to compute an index (the hash) into an array, and stores the item at that index. To retrieve an item, the same hash function is applied to the key to go straight to its index, giving very fast (close to $O(1)$ ) lookup, insertion and deletion on average, without searching.

Collisions and handling (up to 3): a collision occurs when two different keys hash to the same index. It can be handled by chaining (storing a list of items at that index) or by open addressing / probing (placing the item in the next free slot). Markers reward hashing the key to an index for near-constant-time access, the definition of a collision (two keys, same index), and one valid resolution method.

Related dot points

Sources & how we know this

OCR AS and A Level Computer Science (H046, H446) specification — OCR (2015)