Skip to main content
CBE Nexus · Undergraduate Computer Science

Chapter 5: Data Structures and Algorithms

Master algorithm analysis, arrays, linked lists, stacks, queues, hash tables, trees, heaps, graphs, sorting, searching, recursion and algorithm design strategies.

Back to Computer Science course guide

Chapter overview and learning outcomes

This chapter develops the conceptual and practical foundations of data structures and algorithms. It connects theory with implementation, evaluation and responsible computing practice.

1. Algorithms and abstract data types

An algorithm is a finite, well-defined procedure for solving a problem. An abstract data type describes the values and operations of a structure without prescribing its implementation. A list, stack, queue, set, map and priority queue are examples. Choosing an appropriate abstraction reduces complexity and allows implementations to change without altering the program's conceptual interface.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

2. Algorithm correctness and complexity

Correctness asks whether an algorithm produces the required result for every valid input under stated assumptions. A proof may use loop invariants, induction or reasoning about preconditions and postconditions. Complexity estimates resource use as input size grows. Time complexity counts an abstract measure of operations; space complexity considers additional memory. Best, average and worst cases describe different input behaviours.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

3. Asymptotic notation and Big O

Big O gives an asymptotic upper bound on growth, ignoring constant factors and lower-order terms. Big Omega gives a lower bound; Big Theta gives a tight bound when both apply. Common growth rates include constant, logarithmic, linear, linearithmic, quadratic and exponential. For example, nested loops over n elements often produce O(n²) work, while binary search on sorted data is O(log n).

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

4. Arrays and dynamic arrays

An array stores elements in indexed positions, often contiguously. Index access is typically O(1), while inserting into the middle may require shifting elements and take O(n). Dynamic arrays grow capacity when needed, giving amortised efficient append operations. Bounds checking is essential to avoid invalid access. Arrays are useful when predictable indexing and cache locality are important.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

5. Linked lists

A linked list stores elements in nodes connected by references. Singly linked nodes point to the next node; doubly linked nodes also point backward. Insertion or removal can be O(1) when the relevant node is already known, but searching by position is O(n). Linked lists use additional memory for references and often have poorer cache locality than arrays.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

6. Stacks, queues and deques

A stack follows last-in, first-out order, supporting push and pop. It is used in function calls, expression evaluation, undo operations and depth-first search. A queue follows first-in, first-out order, supporting enqueue and dequeue; it is used in scheduling and breadth-first search. A deque supports insertion and removal at both ends.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

7. Hash tables and maps

A hash table maps keys to array positions using a hash function. Collisions occur when distinct keys map to the same location and may be handled by chaining or open addressing. Expected lookup, insertion and deletion can be O(1) under suitable assumptions, but poor hashing or high load factors degrade performance. Keys should have stable equality and hash behaviour.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

8. Trees, binary search trees and heaps

Trees represent hierarchical data. In a binary search tree, keys in the left subtree are smaller and keys in the right subtree are larger under the chosen ordering. An unbalanced tree can degrade to O(n); balanced trees maintain logarithmic height. A binary heap supports efficient priority queue operations, with O(log n) insertion and removal of the root.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

9. Graphs and graph algorithms

Graphs model relationships among entities. Breadth-first search explores by distance in unweighted graphs; depth-first search explores paths deeply before backtracking. Dijkstra's algorithm finds shortest paths from a source when edge weights are non-negative. Minimum spanning tree algorithms such as Kruskal's and Prim's connect all vertices with minimum total edge weight in a connected weighted undirected graph.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

10. Searching and sorting

Linear search examines elements sequentially and works without ordering. Binary search repeatedly halves a sorted search interval. Sorting algorithms include insertion sort, selection sort, merge sort, quicksort and heap sort. Their time, space, stability and worst-case properties differ. Merge sort guarantees O(n log n) time but uses extra space for arrays; quicksort is often fast in practice but can have quadratic worst-case behaviour without suitable pivot strategy.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

11. Recursion and algorithm design paradigms

Recursion solves a problem by reducing it to smaller instances, with a base case that stops further calls. Divide and conquer splits a problem, solves subproblems and combines results. Greedy algorithms make locally optimal choices; dynamic programming stores overlapping subproblem results; backtracking explores candidates and abandons paths that cannot lead to a solution. Each strategy requires proof that it is appropriate.

Worked application: Consider a realistic computing task, identify its assumptions and constraints, then trace the relevant process using a small example. Record intermediate states, expected results and possible failure cases. Compare at least one alternative approach and explain the trade-offs in correctness, performance, maintainability and security.

Study focus: Define the key terms, reproduce the concept diagram, explain the mechanism in sequence and solve a short problem without relying on memorised wording.

Figure 1. Algorithm analysis
Define input size n→Count key operations→Estimate time and space→Express asymptotic growth

Conceptual learning diagram; use alongside the explanations and practical work.

Figure 2. Data structure selection
Identify required operations→Compare access and update cost→Consider memory and ordering→Choose suitable abstraction

Conceptual learning diagram; use alongside the explanations and practical work.

Figure 3. Divide and conquer
Divide into subproblems→Solve subproblems→Combine their results→Prove correctness and analyse

Conceptual learning diagram; use alongside the explanations and practical work.

Practical laboratory activity

  1. Write a short problem specification, listing inputs, outputs and constraints.
  2. Draw a diagram or write pseudocode before implementation.
  3. Implement a small example in an appropriate language or tool.
  4. Test normal, boundary and invalid cases; record actual and expected results.
  5. Explain the design trade-offs and suggest one improvement.

Use authorised software and test environments. Do not run experiments on systems or data without permission.

Worked reasoning and self-check

For every problem, state the assumptions first. Work through a small input manually, record each important state transition and compare the final result with the specification. If the result differs, isolate the smallest failing example and revise the reasoning before changing code. For performance questions, identify the input-size variable and count the dominant operation rather than guessing from execution time alone.

Examination and revision questions

Answer with definitions, explanations, diagrams, calculations or code traces as appropriate. Show working for numerical and algorithmic questions.

  1. Define a data structure.

    Show answer guidance

    A way of organising data to support particular operations efficiently.

  2. What is Big O notation?

    Show answer guidance

    An asymptotic upper bound describing how resource use grows with input size.

  3. What is the time complexity of binary search on sorted data?

    Show answer guidance

    O(log n).

  4. Differentiate stack and queue.

    Show answer guidance

    A stack is last-in first-out; a queue is first-in first-out.

  5. What is a linked list?

    Show answer guidance

    A collection of nodes connected by references or pointers.

  6. What is a hash collision?

    Show answer guidance

    When two distinct keys map to the same hash-table location.

  7. Why can an unbalanced binary search tree be slow?

    Show answer guidance

    Its height can approach n, making operations O(n) in the worst case.

  8. What is a heap used for?

    Show answer guidance

    Efficient priority queue operations, especially access to the minimum or maximum element.

  9. Differentiate BFS and DFS.

    Show answer guidance

    BFS explores breadth-wise by layers; DFS explores paths deeply before backtracking.

  10. What is the worst-case time complexity of merge sort?

    Show answer guidance

    O(n log n).

  11. What is recursion?

    Show answer guidance

    A technique in which a function solves a problem by calling itself on smaller instances.

  12. What is dynamic programming?

    Show answer guidance

    A method that stores solutions to overlapping subproblems to avoid repeated computation.

  13. What is a greedy algorithm?

    Show answer guidance

    An algorithm that repeatedly makes a locally optimal choice according to a rule.

  14. What is a stable sorting algorithm?

    Show answer guidance

    A sort that preserves the relative order of equal-key elements.

  15. Why analyse space complexity?

    Show answer guidance

    To understand memory requirements and whether an algorithm fits resource constraints.

Revision checklist

Further study and references

Consult current university textbooks, peer-reviewed computing research, official language and standards documentation, processor or operating-system manuals, and reputable open educational resources. Check edition, publication date and technical version. Programming language behaviour, security recommendations and software tools evolve; verify details against current official documentation.

Academic and responsible-use note: These notes support undergraduate learning. Verify course requirements with your university, cite sources in assessed work, respect software licences and data privacy, and test only systems for which you have authorisation.

Return to the full Computer Science course guide

Official Education References

Use these official organisations for curriculum guidance, examinations and further learning information.