Chapter overview and learning outcomes
This chapter develops foundational undergraduate knowledge in data structures and algorithm design, connecting theory with practical software engineering decisions. It is designed for active study: read each section, work through the examples, draw the diagrams from memory and complete the revision questions.
- Define and explain the central concepts using accurate technical terminology.
- Apply the methods to a realistic software engineering scenario.
- Compare alternatives and justify design or process decisions.
- Identify assumptions, risks, limitations and quality implications.
- Communicate technical reasoning with clear diagrams and evidence.
1. Data structures and algorithmic thinking
A data structure organises information to support operations such as access, insertion, deletion, search and traversal. An algorithm specifies steps for transforming inputs into outputs. Data structure selection affects performance, memory use and implementation complexity. There is rarely one best structure for every workload. Engineers should identify dominant operations, data size, ordering requirements, concurrency and persistence needs. Abstract data types describe behaviour independently of implementation, allowing an implementation to change while the interface remains stable.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
2. Complexity analysis and asymptotic notation
Time complexity estimates how operation count grows with input size; space complexity estimates memory requirements. Big-O describes an asymptotic upper bound, Big-Omega a lower bound and Big-Theta a tight bound. Common growth rates include constant, logarithmic, linear, linearithmic, quadratic and exponential. Worst-case analysis gives a guarantee for the most demanding input under a model; average-case analysis depends on an input distribution. Complexity complements benchmarking: real performance also depends on constants, hardware, cache behaviour and data characteristics.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
3. Arrays, dynamic arrays and strings
An array stores elements in indexed positions, commonly in contiguous memory. Indexed access is typically constant time, while insertion or deletion in the middle may require shifting elements. Dynamic arrays resize when capacity is exhausted, often giving amortised constant-time append. Strings represent sequences of characters or code units, and Unicode encoding means one visible character may occupy multiple units. Bounds checking, immutability and encoding assumptions matter. Arrays are useful for tables, buffers, matrices and cache-friendly processing.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
4. Linked lists and pointer-based structures
A linked list stores elements in nodes connected by references. Singly linked lists point to the next node; doubly linked lists also point backward. Insertion or removal can be efficient when the relevant node is already known, but locating an arbitrary position requires traversal. Linked structures allocate nodes separately and may have poorer cache locality than arrays. Pointer errors, dangling references and memory leaks are implementation risks in languages without automatic memory management.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
5. Stacks, queues and deques
A stack follows last-in, first-out order. Push adds an item and pop removes the most recent item. Stacks support function calls, expression evaluation, undo operations and depth-first search. A queue follows first-in, first-out order and supports scheduling, buffering and breadth-first search. A deque permits insertion and removal at both ends. Implementations may use arrays or linked nodes. Capacity, overflow, underflow and thread-safety should be considered in production systems.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
6. Hash tables, maps and sets
A hash table maps keys to storage locations using a hash function. Collisions occur when distinct keys map to the same location; common strategies include chaining and open addressing. Expected lookup and insertion can be close to constant time under suitable assumptions, but poor hashing or adversarial inputs can degrade performance. Resizing maintains load factor. Maps associate keys with values; sets store unique elements. Hash-based structures are useful for indexes, caches, symbol tables and deduplication.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
7. Trees, binary search trees and balanced trees
Trees represent hierarchical relationships. A binary search tree orders keys so that smaller values appear in one subtree and larger values in another, supporting search and ordered traversal. Performance depends on height; an unbalanced tree may degrade to linear operations. Balanced structures such as AVL trees and red-black trees maintain height constraints through rotations and recolouring or balancing rules. B-trees and variants are used in storage systems and databases because they reduce costly disk accesses.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
8. Heaps and priority queues
A binary heap is a complete binary tree that satisfies a heap-order property. In a min-heap, each parent is no greater than its children; in a max-heap, each parent is no smaller. A priority queue exposes removal of the highest- or lowest-priority item. Heaps support scheduling, event simulation, graph algorithms and top-k queries. Insertion and removal typically require logarithmic time, while reading the root is constant time. Heap arrays use index arithmetic to locate parents and children.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
9. Graphs, traversal and pathfinding
Graphs model relationships between entities. Breadth-first search explores by distance in edges and finds shortest paths in unweighted graphs. Depth-first search explores deeply before backtracking and supports cycle detection and component analysis. Dijkstra's algorithm handles non-negative edge weights; Bellman-Ford supports negative weights and detects reachable negative cycles. Minimum spanning tree algorithms connect vertices at minimum total cost. Choose representations and algorithms according to graph density, weights and required results.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
10. Sorting, searching and selection
Linear search checks elements sequentially and takes O(n) time. Binary search takes O(log n) time on data that is sorted and supports efficient indexed access. Sorting methods include insertion sort, selection sort, merge sort, quicksort and heapsort. Their trade-offs include time complexity, memory, stability and worst-case behaviour. Stable sorting preserves relative order of equal keys. Selection algorithms find order statistics such as a median without necessarily sorting the entire collection.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
11. Recursion, divide-and-conquer and dynamic programming
Recursion defines a solution in terms of smaller instances and requires base cases that guarantee termination. Divide-and-conquer splits a problem, solves subproblems and combines results. Dynamic programming stores solutions to overlapping subproblems using memoisation or tabulation. Greedy algorithms make locally optimal choices and require a correctness proof to establish global optimality. Backtracking explores candidate solutions and abandons partial candidates that cannot lead to a valid result. Paradigm selection should follow problem structure, not fashion.
Engineering application and analysis
Apply this concept to a realistic software project. Identify the actors, inputs, outputs, constraints, dependencies and failure conditions. Explain why the selected method is appropriate, what assumptions it makes, and how its success could be evaluated. Compare at least one alternative and discuss the consequences for maintainability, reliability, security, accessibility, performance and cost. Distinguish evidence from opinion, and state what additional information would be needed before making a production decision.
Worked study activity
Construct a small example, annotate each step, and test both an ordinary case and a boundary case. Record the expected result before running the test, compare the observed result, investigate any difference, and explain the lesson. Where a design choice is involved, write down the trade-off and identify who is affected by it.
Conceptual learning diagram; adapt it to the system or example being studied.
Conceptual learning diagram; adapt it to the system or example being studied.
Conceptual learning diagram; adapt it to the system or example being studied.
Practical laboratory / project activity
- Choose a bounded problem relevant to this chapter and describe the intended users and context.
- Write down assumptions, constraints, inputs, outputs and measurable success criteria.
- Develop a small prototype, model, algorithm, specification or test artefact.
- Use version control and document tools, versions and important decisions.
- Test normal, boundary and failure conditions; retain reproducible evidence.
- Review the result for usability, accessibility, security, reliability and maintainability.
- Submit a concise report explaining the method, findings, limitations and next steps.
Only test systems and datasets for which you have permission. Protect personal information and follow institutional academic-integrity and laboratory rules.
Worked reasoning and self-assessment
Begin with a precise problem statement. Separate known facts from assumptions. Identify the relevant concepts and choose a method that fits the problem constraints. Work through a small example manually, then verify the result using a suitable tool or test. Explain why the approach works, where it may fail, and what evidence would be needed to trust it in a larger system. For a design decision, state the alternatives and the trade-offs rather than presenting one choice as universally best.
Examination and revision questions
Attempt each question before opening the answer guidance. Use examples, diagrams and precise definitions in longer responses.
What is a data structure?
Show answer guidance
A way of organising data to support specified operations.
What does Big-O notation describe?
Show answer guidance
An asymptotic upper bound on growth of resource use.
When is an array useful?
Show answer guidance
When indexed access and compact sequential storage are important.
Differentiate a stack and a queue.
Show answer guidance
A stack is last-in first-out; a queue is first-in first-out.
What is a hash collision?
Show answer guidance
Two distinct keys map to the same hash-table location.
Why balance a search tree?
Show answer guidance
To prevent height from becoming linear and preserve efficient operations.
What is a priority queue?
Show answer guidance
An abstract data type that removes items according to priority.
What does BFS find in an unweighted graph?
Show answer guidance
A shortest path in number of edges from a source to reachable vertices.
What is the precondition for binary search?
Show answer guidance
The searched data must be ordered and support suitable indexed access.
What is a stable sorting algorithm?
Show answer guidance
One that preserves the relative order of equal-key records.
What is recursion?
Show answer guidance
A technique where a function solves a problem using smaller instances of itself.
Differentiate memoisation and tabulation.
Show answer guidance
Memoisation stores results on demand; tabulation builds results iteratively in a planned order.
What is a greedy algorithm?
Show answer guidance
An algorithm that repeatedly makes a locally preferred choice.
What is backtracking?
Show answer guidance
A search method that explores candidates and abandons partial solutions that cannot succeed.
Why benchmark algorithms?
Show answer guidance
To measure actual behaviour on representative workloads and complement theoretical analysis.
Revision checklist
- Can I define the chapter's key terms accurately?
- Can I explain the diagrams without reading the captions?
- Can I apply the ideas to a new project scenario?
- Can I justify a method and compare it with alternatives?
- Can I identify risks, assumptions and quality implications?
- Can I explain what evidence would validate my conclusion?
Further reading and academic practice
Use current university textbooks, peer-reviewed software engineering research, recognised standards and official technical documentation. Verify edition, version, publication date and applicability before citing a source. Cite quotations, data, diagrams, software and ideas according to your institution's required referencing style. Do not invent references, results or test evidence. Compare sources critically and note where professional guidance differs by context or jurisdiction.