What is the difference between an array and a linked list?

An array stores elements in contiguous memory locations, allowing O(1) random access but O(n) insertion/deletion. A linked list stores elements in nodes with pointers, allowing O(1) insertion/deletion at the head but O(n) access. Arrays have fixed size; linked lists are dynamic. Choose arrays for frequent access, linked lists for frequent insertions/deletions.

How do I implement a stack using an array?

Use an array with a 'top' pointer (index). Push: increment top and assign value. Pop: return value at top and decrement top. Check for overflow (top == maxSize-1) and underflow (top == -1). This gives O(1) operations. Alternatively, use a dynamic array (like Python list) to avoid fixed size.

What is a binary search tree and how does it work?

A binary search tree (BST) is a tree where each node has at most two children. For any node, all values in the left subtree are less, and all in the right subtree are greater. Search, insert, and delete average O(log n) if balanced. In-order traversal yields sorted order. BSTs are used for efficient searching and sorting.

Why do we use Big O notation in data structures?

Big O notation describes the worst-case time or space complexity of an algorithm as input size grows. It helps compare data structures objectively, independent of hardware or implementation details. For example, O(1) means constant time, O(n) linear, O(log n) logarithmic. This allows you to choose the most efficient structure for your problem.

What is a hash table and how does it handle collisions?

A hash table maps keys to indices using a hash function. Collisions occur when two keys hash to the same index. Common resolution methods: chaining (store multiple items in a linked list at that index) and open addressing (find next empty slot via probing, e.g., linear or quadratic). Good hash functions minimise collisions for O(1) average performance.

How do I choose the right data structure for a problem?

Consider the operations you need: frequent access? Use array or hash table. Frequent insertions/deletions? Use linked list. Need order? Use stack (LIFO) or queue (FIFO). Need hierarchical data? Use tree. Need relationships? Use graph. Also consider memory constraints and whether the structure needs to be dynamic. Always analyse time/space complexity.

Data Structures

OCR

A-Level

This topic covers the representation and storage of data within various structures, including arrays, records, lists, tuples, linked-lists, graphs, stacks, queues, trees, and hash tables. It requires an understanding of how to create, traverse, add, and remove data from these structures using either procedural or object-oriented programming approaches.

Objectives

Exam Tips

Pitfalls

Key Terms

Mark Points

Topic Overview

Data structures are fundamental building blocks in computer science, defining how data is organised, stored, and manipulated in memory. In OCR A-Level Computer Science, you'll explore both linear structures (arrays, linked lists, stacks, queues) and non-linear structures (trees, graphs). Understanding these allows you to write efficient algorithms, as the choice of data structure directly impacts time and space complexity. For example, a stack is ideal for undo operations, while a hash table enables O(1) average lookup time.

This topic is crucial because it underpins almost every software system you'll encounter. From databases using B-trees to social networks using graphs, data structures are everywhere. In the OCR specification, you'll need to implement these structures in a programming language (often Python or Java) and analyse their performance using Big O notation. You'll also learn about abstract data types (ADTs) and how they encapsulate data and operations.

Mastering data structures prepares you for the 'Algorithms' topic, as many algorithms are designed to work with specific structures. For instance, Dijkstra's shortest path algorithm relies on a priority queue, and binary search trees enable efficient searching. By the end of this topic, you should be able to select the most appropriate structure for a given problem and justify your choice using complexity analysis.

Key Concepts

Core ideas you must understand for this topic

→Abstract Data Types (ADTs): A logical description of data and operations without implementation details. Examples include stack (push/pop) and queue (enqueue/dequeue).
→Dynamic vs Static Structures: Static structures (arrays) have fixed size; dynamic structures (linked lists) can grow/shrink at runtime, using pointers.
→Big O Notation: Used to describe worst-case time/space complexity. For example, accessing an array element is O(1), but searching an unsorted linked list is O(n).
→Tree Traversals: Pre-order, in-order, post-order for binary trees; breadth-first and depth-first for graphs. Each has specific use cases (e.g., in-order gives sorted order for BST).
→Hash Tables: Use a hash function to map keys to indices. Collision resolution techniques include chaining (linked list per bucket) and open addressing (probing).

What You Need to Demonstrate

Key skills and knowledge for this topic

Correct identification and implementation of data structures (linked-list, graph, stack, queue, tree, binary search tree, hash table).
Ability to perform operations: create, traverse, add, and remove data.
Correct use of array indexing (0-based) and multi-dimensional arrays.
Understanding of the relationship between data structures and algorithms.
Correct implementation of data structures using either procedural or object-oriented approaches.

Marking Points

Key points examiners look for in your answers

Correct identification and implementation of data structures (linked-list, graph, stack, queue, tree, binary search tree, hash table).
Ability to perform operations: create, traverse, add, and remove data.
Correct use of array indexing (0-based) and multi-dimensional arrays.
Understanding of the relationship between data structures and algorithms.
Correct implementation of data structures using either procedural or object-oriented approaches.

Examiner Tips

Expert advice for maximising your marks

💡Be prepared to write pseudocode for operations on any of the listed data structures.
💡Practice tracing algorithms on paper to ensure you understand how data moves through a structure.
💡Ensure you can distinguish between the suitability of different structures for specific problems.
💡Remember that arrays are 0-based in the OCR pseudocode standard.
💡Be ready to explain the difference between procedural and object-oriented implementations of these structures.
💡When describing algorithms, always state the data structure used and justify why it's appropriate. For example, 'I used a queue for the breadth-first search because it processes nodes in FIFO order, ensuring level-by-level traversal.'
💡In coding questions, pay attention to edge cases: empty structures, single elements, and duplicate values. For linked lists, remember to update pointers correctly to avoid memory leaks or infinite loops.
💡For complexity analysis, be precise: state whether you're measuring time or space, and specify the operation (e.g., 'insertion at the head of a linked list is O(1)'). Avoid vague terms like 'fast' or 'slow'.

Common Mistakes

Pitfalls to avoid in your exam answers

Confusing the traversal methods for different structures (e.g., depth-first vs breadth-first).
Incorrectly handling array bounds, especially in multi-dimensional arrays.
Failing to correctly implement the logic for adding/removing nodes in linked lists or trees.
Misunderstanding the difference between a stack (LIFO) and a queue (FIFO).
Inconsistent use of 0-based indexing.
Misconception: 'A stack and a queue are the same thing.' Correction: Stacks are LIFO (Last In, First Out) – like a pile of plates; queues are FIFO (First In, First Out) – like a line at a till.
Misconception: 'Linked lists are always better than arrays because they are dynamic.' Correction: Arrays offer O(1) random access, while linked lists require O(n) to access an element. Linked lists also use more memory due to pointers.
Misconception: 'A binary search tree always has O(log n) search time.' Correction: This only holds if the tree is balanced. In the worst case (e.g., inserting sorted data), a BST degenerates into a linked list with O(n) search time.

Frequently Asked Questions

Common questions students ask about this topic

Before You Start

Prior knowledge that will help with this topic

•Basic programming concepts: variables, loops, conditionals, functions, and arrays.
•Understanding of pointers/references (if using languages like C++ or Java) or object references in Python.
•Fundamentals of algorithm analysis: Big O notation and simple complexity calculations.

Likely Command Words

How questions on this topic are typically asked

Describe

Explain

Implement

Trace

Compare

Construct

Ready to test yourself?

Practice questions tailored to this topic

Data Structures

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra

Topic Synopsis

Key Concepts & Core Principles

Exam Tips & Revision Strategies

Common Misconceptions & Mistakes to Avoid

Examiner Marking Points

Data Structures

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

What is the difference between an array and a linked list?

How do I implement a stack using an array?

What is a binary search tree and how does it work?

Why do we use Big O notation in data structures?

What is a hash table and how does it handle collisions?

How do I choose the right data structure for a problem?

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra