Define and use composite data types

13.1 User‑Defined Data Types

Learning objectives

• Define and use **non‑composite** user‑defined types: enumerated, pointer, set.
• Define and use **composite** user‑defined types: record (structure), array, tuple, class/object.
• Explain why each type is required in a program.
• Design an appropriate user‑defined type for a given problem and justify the choice.
• Show how composite types are used to implement abstract data types (stacks, queues, linked lists, trees, …).

1. Non‑Composite User‑Defined Types

These types are built from a single primitive type but give the programmer a new name or a restricted set of values.

1.1 Enumerated type

ENUM Colour { Red, Green, Blue };
Colour favourite := Blue;

1.2 Pointer type

TYPE PtrToNode IS POINTER TO Node;

RECORD Node {
    data : INTEGER;
    next : PtrToNode;          // pointer to another Node
}

Why a pointer is needed: the size of a Node record is fixed, but the number of nodes required by a linked list is not known at compile‑time. By storing only the address of the next node, we can create an arbitrarily long chain of nodes without allocating a huge contiguous block of memory.

Memory‑layout illustration (simplified):

+-------------------+      +-------------------+
| Node p            | ---> | Node q            |
|-------------------|      |-------------------|
| data = 12         |      | data = 27         |
| next = address(q) |      | next = NIL        |
+-------------------+      +-------------------+

1.3 Set type

SET OF CHAR VOWELS = { 'a', 'e', 'i', 'o', 'u' };
IF ch IN VOWELS THEN
    OUTPUT "vowel"
ENDIF

2. Composite User‑Defined Types

Real‑world entities usually consist of several related pieces of data. Grouping those pieces into a single logical unit improves readability, maintainability and data integrity, and provides the building blocks for abstract data types.

2.1 Record (Structure)

A record is a collection of named fields, each of which may have a different primitive type.

RECORD Point {
    x : INTEGER;
    y : INTEGER;
}

Access fields with the dot operator (.) or the arrow operator (->) when a pointer to a record is used.

2.2 Array

An array stores a fixed number of elements of the **same** type, indexed from 1 (Cambridge convention).

DECLARE scores : ARRAY [1..10] OF INTEGER;
DECLARE marks  : ARRAY [1..5] OF INTEGER := {90, 85, 78, 92, 88};

2.3 Tuple

A tuple is a fixed‑size, ordered collection that may contain elements of different types. In many languages tuples are immutable; in Cambridge pseudocode they are treated as a record without field names.

DECLARE person : TUPLE (STRING, INTEGER, BOOLEAN) := ("Alice", 23, TRUE);

2.4 Class / Object

A class combines data (attributes) and behaviour (methods). Objects are instances of a class. The Cambridge syllabus expects the term “class” but also recognises that a simple record can be used when no methods are required.

CLASS Circle {
    PRIVATE radius : REAL;

    PUBLIC CONSTRUCTOR(r : REAL) {
        radius := r;
    }

    PUBLIC FUNCTION area() : REAL {
        RETURN 3.14159 * radius * radius;
    }
}

2.5 Type alias (optional)

Creating a new name for an existing type can make code clearer.

TYPE Point2D IS RECORD
    x : INTEGER;
    y : INTEGER;
END RECORD;

3. Operations on Composite Types

1. Creation / instantiation – allocate memory and initialise fields (e.g. DECLARE p : Point := (0,0);).
2. Access – use . (or -> for a pointer) to read or modify a field.
3. Assignment – whole‑type assignment copies all fields (a shallow copy unless the type contains pointers).
4. Comparison – usually requires a user‑defined routine that tests each corresponding field for equality.
5. Pass‑by‑value vs. pass‑by‑reference – large composites are normally passed by reference to avoid costly copies and to allow the routine to modify the original data.

4. Design example – Student record

4.1 Definition (Cambridge pseudocode)

RECORD Student {
    id   : STRING;
    name : STRING;
    age  : INTEGER;
    GPA  : REAL;
}

4.2 Using the record

DECLARE class : ARRAY [1..5] OF Student;

/* Initialise the first element */
class[1] := ("S001", "Emma", 19, 3.7);

/* Function to compute the average GPA of an array of students */
FUNCTION averageGPA(studs : ARRAY [1..n] OF Student; n : INTEGER) : REAL
    DECLARE total : REAL := 0.0;
    FOR i FROM 1 TO n DO
        total := total + studs[i].GPA;
    ENDFOR
    RETURN total / n;
ENDFUNCTION

4.3 Design justification (syllabus requirement 13.1.3)

• Readability – all information about a student is grouped together; class[i].GPA is self‑explanatory.
• Maintainability – adding a new attribute (e.g. major : STRING) requires only one change to the record definition, not to every parallel array.
• Data cohesion – the four fields always belong to the same logical entity; parallel arrays could become out‑of‑sync.
• Alternative designs considered
  • Parallel arrays – separate arrays for each attribute; harder to keep data aligned and more error‑prone.
  • Class – would be appropriate if behaviour (methods such as calculateHonours()) were required; a record is sufficient for pure data storage.

5. Composite types in algorithms & abstract data types (ADTs)

Composite types are the building blocks of ADTs. Choose the type that matches the required operations.

• Stack – often an ARRAY with a top index, or a linked list of Node records.
• Queue – circular ARRAY or linked list of records with front and rear pointers.
• Linked list – record Node { data : INTEGER; next : PtrToNode; } demonstrates the combined use of a record and a pointer.
• Tree – node record with left and right pointers; recursive algorithms traverse the composite structure.

When designing an algorithm, consider:

• Random access → ARRAY
• Frequent insertion/deletion → linked structure (record + pointer)
• Fixed‑size, heterogeneous data → TUPLE or RECORD
• Behaviour required → CLASS

6. Key points to remember

• Non‑composite types (enumerated, pointer, set) give new names or constraints to primitive types.
• Composite types model complex entities and are essential for creating ADTs.
• Use the exact term **record** (or **structure**) as required by the Cambridge syllabus.
• Justify the choice of a particular composite type in terms of readability, maintainability and algorithmic suitability.
• Pass large composites by reference to avoid unnecessary copying.
• Encapsulation via CLASS protects data integrity by restricting direct field access.

+---------------------------+        +---------------------------+
| Student record            |        | averageGPA(students)      |
|---------------------------|        |---------------------------|
| id   : STRING             |        | total := 0                |
| name : STRING             |        | FOR each s in students    |
| age  : INTEGER            |  --->  |   total := total + s.GPA  |
| GPA  : REAL               |        | ENDFOR                    |
+---------------------------+        | RETURN total / n          |
                                     +---------------------------+