B4.1.1 · Abstract data types (ADTs)
Concept of ADTs
By the end you can
Describe abstract data types as mathematical operational specifications and separate logical interface from memory implementation.
In computer science, abstraction is the art of hiding unnecessary internal mechanics so that engineers can focus on problem-solving. An applies this principle directly to data organization: it specifies what operations can be performed on a collection of data, without specifying how those operations are physically stored or executed in computer memory.
Specification versus implementation#
Consider the Stack ADT:
- The ADT Specification: Defines operations
push(x),pop(),peek(), andisEmpty(), and guarantees Last-In, First-Out (LIFO) behavior. - The Physical Implementation: Could be an internal fixed-size array with an integer pointer, or a dynamic singly linked list of heap nodes.
To any program using the stack, the internal implementation makes zero difference: calling stack.push(5) behaves identically either way.
Why ADTs are foundational in software engineering#
- Encapsulation: Internal arrays, pointers, and memory blocks remain strictly private. Client programs cannot bypass validation rules.
- Interchangeability: If an array-based list causes out-of-memory errors during scaling, engineers can replace it with a linked list backend. Because public method signatures do not change, not a single line of caller code needs editing!
- Reusability: Standardized ADT contracts allow software libraries to be shared universally across different projects and frameworks.
Check yourself
Concept of ADTs
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 9 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Define the term abstract data type (ADT) and distinguish it from a concrete data structure.
[2]Define: Give the precise meaning of the term.
2.Explain the software engineering benefits of separating the abstract interface of an ADT from its physical implementation.
[4]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.State three standard abstract data types and identify one core operation defined for each.
[3]State: Give a short answer, no explanation needed.
In a nutshell
- An abstract data type (ADT) defines data values and allowable operations from the user’s perspective, completely independent of memory implementation.
- An ADT represents the “what” (specification/contract), while a data structure represents the “how” (physical memory realization).
- Classic examples of ADTs include Stacks, Queues, Lists, Trees, and Graphs.
- Separating interface from implementation enables developers to swap internal data structures without breaking external client code.