A-Level Computer Science / Unit 10: Organising Data in Programs

10.4.1 Abstract Data Types and Choosing a Structure

🔒 Lesson slides are available to signed-in users. Sign in

10.4.1 Abstract Data Types and Choosing a Structure

Programs often need more than a collection of values. They also need clear rules for how those values may be added, accessed, changed or removed. An Abstract Data Type describes this combination of stored data and permitted operations without first exposing every implementation detail.

This page introduces the general idea of an ADT and develops a method for choosing between a stack, queue and linked list. The following pages examine each structure in more detail.

By the end of this section, you should be able to:

  • Explain an ADT as stored data together with a defined set of operations.
  • Distinguish the behaviour of an ADT from the way it is implemented.
  • Recognise stacks, queues and linked lists as examples of ADTs.
  • Describe the high-level access rules of each structure.
  • Choose a suitable ADT from the requirements of a problem.
  • Justify a choice using the order of insertion, access and removal.
  • Explain that these ADTs can be implemented using arrays.
Scope: the syllabus does not require students to write pseudocode that implements these ADTs. Students should understand their behaviour, manipulate stored data according to the structure's rules, justify their use and describe array-based implementations.

What Is an Abstract Data Type?

An ADT is a logical description of a collection of data and the operations through which a program may use that data. The word abstract means that the description concentrates on observable behaviour rather than the internal storage details.

Abstract Data Type: a collection of data together with a defined set of operations that can be performed on those data.

For example, a structure may allow a new item to be added, an item to be removed and the next available item to be inspected. The rules governing those operations form part of the ADT.

Common misconception: an ADT is not simply “some stored data”. A complete explanation must also include the operations and rules that control the data.

Interface and Implementation

A useful way to understand abstraction is to separate what the structure offers from how the structure is built.

Idea Main question Example
ADT behaviour What operations are available, and what rules do they follow? A queue removes the item that has waited longest.
Interface How does another part of the program request those operations? Add an item, inspect the next item or remove the next item.
Implementation How are the data and control information stored internally? An array and one or more pointer variables.
Exam tip: a strong comparison says that an ADT defines the permitted behaviour, while an implementation supplies the internal storage and algorithms that make that behaviour possible.
Two implementations can provide the same ADT behaviour. Do not define an ADT only by saying that it “uses an array”.

General Operations on Data Structures

The exact operation names vary between structures, but several broad actions occur repeatedly. Their meaning is constrained by the rules of the chosen ADT.

General action Purpose Important qualification
Create Prepare a new empty instance. The structure starts with no stored items.
Add / insert Place a new item into the structure. The ADT determines where the item may enter.
Access / inspect View an item without necessarily removing it. Some ADTs expose only one end or one next item.
Find Locate an item or determine whether it is present. The method depends on the structure and implementation.
Edit Change stored information. Direct access to an arbitrary item may not be permitted.
Delete / remove Take an item out of the structure. The ADT determines which item may leave next.
Traverse Visit the stored items systematically. The visiting order follows the structure's organisation.
Common mistake: do not assume that every ADT allows arbitrary indexed access. A stack and queue deliberately restrict which item can be accessed or removed next.

Three ADTs in This Unit

The three required structures can be distinguished by the rule that determines where new items are added and which item is available next.

Stack

Items are added and removed at the same end, called the top. The most recently added item is the next one removed.

Key order: last in, first out.

Queue

Items join at the rear and leave from the front. The item that has been waiting longest is removed first.

Key order: first in, first out.

Linked list

Items are stored as nodes connected by links. Nodes can be inserted or removed by changing links rather than shifting every later item.

Key idea: linked sequence of nodes.

Use the access rule in your justification. Naming the structure without explaining how its rule matches the requirement is not enough.

Comparing Stack, Queue and Linked List

Question Stack Queue Linked list
Where is a new item added? At the top At the rear At a chosen linked position
Which item is normally removed next? The most recently added item The earliest waiting item The selected node
Natural order LIFO FIFO Determined by links
Typical strength Reversing or returning through recent states Fair processing in arrival order Insertion and deletion within a changing sequence
Typical limitation Older items are hidden below newer ones Later items must wait behind earlier ones Items are normally followed sequentially rather than by direct index
Detailed page 10.4.2 10.4.3 10.4.4
LIFO: last in, first out.   FIFO: first in, first out.

A Method for Choosing a Structure

Begin with the problem requirements rather than choosing a familiar structure first. Ask the following questions in order.

  1. Which item must be available next? The newest item suggests a stack; the oldest waiting item suggests a queue.
  2. Where may insertion and deletion occur? One restricted end suggests a stack; opposite ends suggest a queue; positions within a sequence suggest a linked list.
  3. Must arrival order be preserved? When earlier requests should be handled first, a queue is usually appropriate.
  4. Will the sequence change frequently in the middle? A linked list can avoid shifting a long run of later items when links are updated.
  5. Is direct indexed access required? If the main requirement is immediate access by position, a conventional array may be more suitable than these restricted ADTs.
A justification should connect a requirement to a structural rule: “A queue is suitable because requests must be removed in the same order in which they arrive.”

Worked Structure Decisions

Situation Best choice Reason
A drawing program must undo the latest action first. Stack The most recently added action must be removed before earlier actions.
Print jobs must be processed in submission order. Queue The earliest waiting job must leave the structure first.
A route planner often inserts and removes checkpoints between existing checkpoints. Linked list Links can be updated to change the sequence without shifting every later item.
A compiler checks nested brackets and closes the newest unmatched bracket first. Stack The most recently opened bracket must be matched first.
Customer-support requests should be allocated in arrival order. Queue FIFO behaviour preserves the order in which requests entered.
An ordered maintenance sequence is frequently edited between existing steps. Linked list Nodes can be inserted or removed by altering links within the sequence.
Avoid vague reasoning: “use a stack because it stores actions” is weak. Many structures store actions. The decisive point is that the newest action must be removed first.

Interactive: Structure Decision Lab

Read each requirement, choose a structure and then inspect the explanation. The visual model shows the access rule that makes the recommended ADT suitable.

Scenario 1 of 6
Problem requirement

Undo recent drawing actions

The newest action must be reversed before any earlier action.

    Your decision

    Choose a structure

    Select the ADT whose access rule matches the requirement.

    Behaviour model No structure selected

    The model will appear after you make a choice.

    Common Mistakes and Misconceptions

    • Defining an ADT without mentioning its operations.
    • Confusing the logical behaviour with one array-based implementation.
    • Claiming that all structures allow direct access to any stored item.
    • Selecting a stack whenever values need to be stored, without checking the removal order.
    • Selecting a queue because it is “fair” without explaining FIFO behaviour.
    • Claiming that linked lists always make every operation faster.
    • Giving implementation pseudocode even though the question asks only for a suitable ADT and justification.
    • Using the words LIFO or FIFO without connecting them to the situation.

    Practice

    Task 1: Complete the definition

    Improve this incomplete statement: “An Abstract Data Type is a collection of data.”

    Task 2: Behaviour or implementation?

    Classify each statement.

    1. The earliest waiting item is removed first.
    2. Two integer variables store the front and rear positions.
    3. A new item is added at the top.
    4. A one-dimensional array stores the items.

    Task 3: Choose and justify

    Select a stack, queue or linked list for each situation.

    1. A web browser stores pages for a Back operation.
    2. A help desk processes unresolved tickets in arrival order.
    3. A playlist is frequently edited by inserting tracks between existing tracks.
    4. A depth-first search must return to the most recently stored branch point.

    Task 4: Improve weak justifications

    Rewrite each answer so that it refers to the required access or removal rule.

    1. “Use a queue because queues are good for printers.”
    2. “Use a stack because it stores the actions.”
    3. “Use a linked list because it is flexible.”

    Task 5: Recognise when an array may be better

    A program must repeatedly read the value stored at a known numbered position, with few insertions or deletions. Explain why direct array indexing may be more suitable than a stack, queue or linked list.

    Review

    Question Strong answer should include
    What is an ADT? Stored data together with the operations and rules that apply to those data.
    Why is it abstract? It describes behaviour without requiring the internal implementation details.
    When is a stack suitable? When the newest item must be accessed or removed first.
    When is a queue suitable? When items must be processed in arrival order.
    When is a linked list suitable? When a linked sequence changes through insertions or deletions at selected positions.
    How should a choice be justified? By linking a problem requirement to the ADT's insertion, access or removal rule.
    How can these ADTs be implemented later in the unit? Using arrays and suitable pointer or index variables.
    Final exam tip: identify which item must be available next, select the structure whose rule produces that behaviour, and explain the connection explicitly.