Chapter 13
Data types
& structures
Data types
& Records
Primitive Data Types
What Are Data Types?
A data type is a way of classifying data based on what kind of value it stores.
Computers cannot treat all data the same way.
For example:
Numbers are processed differently from text.
True/False values are processed differently from numbers.
So, we use data types to tell the computer what kind of data we are storing.
Primitive Data Types
Why Are Data Types Important?
Choosing the correct data type:
✔ Ensures correct calculations
✔ Saves memory
✔ Improves program efficiency
✔ Prevents errors
Primitive Data Types
Integer
Used to store whole numbers (no decimal part).
Examples:
10, -5, 0, 250
Pseudocode:
DECLARE Age : INTEGER
Age ← 10
Python: age = 10
Primitive Data Types
Real
Used to store numbers with decimals.
Examples:
3.14, -2.5, 0.0
Pseudocode:
DECLARE Temp : REALTemp ← 3.14
Python: temp = 3.14
Primitive Data Types
Char
Stores a single character only.
Examples:
'A', 'B', '5', '$'
⚠ Important:
Char stores only ONE character
Pseudocode:
DECLARE Grade : CHAR
Grade ← 'A'
⟶ Used for: gender (M/F), grade (A/B/C), menu choice
Primitive Data Types
String
Stores a sequence of characters (text).
Examples:
"Hello"
"1234"
"@#$%"
Pseudocode:
DECLARE Name : STRING
Name ← "Alice"
⟶ Used for: names, addresses, messages
Primitive Data Types
Boolean
Stores only two possible values:
TRUE
FALSE
Pseudocode:
DECLARE LoggedIn : BOOLEAN
LoggedIn ← TRUE
Used for:
Conditions
Flags
Login status
Validation checks
Primitive Data Types
Date
Stores a calendar date.
Example format:
24/04/2025
Pseudocode:
DECLARE DOB : DATE
DOB ← "24/04/2025"
Used for:
Date of birth
Exam date
Registration date
Primitive Data Types
In pseudocode:
You must declare variables before using them.
Every variable must have:
A unique name (identifier)
A data type
General format:
DECLARE <identifier> : <data type>
Example:
DECLARE Score : INTEGER
DECLARE Name : STRING
DECLARE IsPassed : BOOLEAN
Record Structures
What Is a Record?
A record is a composite data structure.
This means:
It stores multiple related data items
Each item (called a field) can have a different data type
All fields are grouped under one name
⟶ A record groups related information together in an organised way.
Record Structures
Why Do We Use Records?
Without records, we would need many separate variables.
Example without a record:
DECLARE Make : STRING
DECLARE Model : STRING
DECLARE Colour : STRING
DECLARE Price : REAL
DECLARE DateOfRegistration : DATE
This becomes difficult to manage.
⟶Records make programs:
More organised
Easier to read
Easier to maintain
Less error-prone
Record Structures
Key Features of a Record :
Contains a fixed number of fields
Each field has:
A name
A data type
All fields are related to the same entity
Declaring a Record in Pseudocode :
General structure:
TYPE <TypeName>
DECLARE <FieldName> : <DataType>
DECLARE <FieldName> : <DataType>
ENDTYPE
After defining the type, we create a variable of that type.
Record Structures
Example: Car Record
Suppose we want to store information about a car.
Step 1: Define the record type
TYPE Car
DECLARE Make : STRING
DECLARE Model : STRING
DECLARE Colour : STRING
DECLARE Price : REAL
DECLARE DateOfRegistration : DATE
ENDTYPE
Here:
Car is the record type
Make, Model, Colour, Price, DateOfRegistration are fields
Record Structures
Step 2: Create a variable of that type
DECLARE MyCar : Car
Now MyCar contains all five fields.
Step 3: Assign values to the fields
[Link] ← "Toyota"
[Link] ← "Yaris"
[Link] ← "Red"
[Link] ← 14995.99
[Link] ← "12/03/2022"
Notice the use of:
[Link]
This is called dot notation.
Record Structures
Step 4: Access (Read) Data from the Record
OUTPUT "Make: ", [Link]
OUTPUT "Model: ", [Link]
OUTPUT "Colour: ", [Link]
OUTPUT "Price: £", [Link]
OUTPUT "Date of Registration: ", [Link]
Record Structures
A record:
Groups related data items
Can store different data types
Improves structure and readability
Uses dot notation to access fields
Key features of records
Feature Explanation
Can store different data types Unlike arrays, records are not limited to a single type
Fields are named Each item in the record has a meaningful identifier
Easier to manage complex data about real-world
Offers structured storage
entities
Arrays
Array Basics
What is an array?
An array is a data structure used to store multiple values of the same data type under one
name.
All elements must be the same data type
Elements are stored in a fixed order
Each element is accessed using an index (position number)
Array Indexing
The first element is at the lower bound (LB)
The last element is at the upper bound (UB)
The lower bound is usually 0 or 1, depending on the programming language
Dimensions of Arrays
One-dimensional array → stores a simple list of values
Multi-dimensional array → stores data in tables or grids (e.g. rows and columns)
One-dimensional (1D) arrays
A 1D array is a linear array
To declare a 1D array in pseudocode you must include the lower bound, upper bound and data
types:
DECLARE <identifier> : ARRAY[LB:UB] OF <data type>
One-dimensional (1D) arrays
In this example a 1D array of five elements each containing single character :
// Declare the array
DECLARE Letters : ARRAY[0:4] OF CHAR
// Assign values to each index
Letters[0] ← 'B'
Letters[1] ← 'E'
Letters[2] ← 'A'
Letters[3] ← 'D'
Letters[4] ← 'S' The array is declared with indices from 0 to 4
Each element stores a single character using
// Output the full array the CHAR data type
FOR Index ← 0 TO 4 The loop outputs each letter in order
OUTPUT Letters[Index]
NEXT Index
Two-dimensional (2D) arrays
A 2D array can be visualised as a table
When navigating through a 2D array you first have to go down the rows and then across the
columns to find a position within the array
In 2D arrays the following must be declared:
Lower bound for rows (LBR) & upper bound for rows (UBR)
Lower bound for columns (LBC) & upper bound for columns (UBC)
DECLARE <identifier> : ARRAY[LBR:UBR, LBC:UBC] OF <data type>
Two-dimensional (2D) arrays
In this example a 2D array can be declared as: An example complete program could be:
// Row 0
DECLARE Letters : ARRAY[0:2, 0:4] OF CHAR
Grid[0,0] ← 'B'
Grid[0,1] ← 'E'
Grid[0,2] ← 'A'
Grid[0,3] ← 'D'
Grid[0,4] ← 'S'
// Row 1
Grid[1,0] ← 'S'
Grid[1,1] ← 'E'
Grid[1,2] ← 'V'
Grid[1,3] ← 'E'
Grid[1,4] ← 'N'
ARRAY[0:2, 0:4] creates 3 rows and 5 columns
// Row 2
First index is the row, second is the column: Grid[2,0] ← 'W'
Letters[row, column] Grid[2,1] ← 'H'
All elements are of type CHAR Grid[2,2] ← 'I'
Grid[2,3] ← 'T'
Grid[2,4] ← 'E'
Searching arrays
What is a linear search?
How do you perform a linear
search?
A linear search starts with the first value in a dataset and
checks every value one at a time until all values have [Link] the first value
been checked 2. IF it is the value you are
A linear search can be performed even if the values are
looking for STOP!
not in order
[Link] move to the next value
A linear search can be used to find elements in an array
Each element in the array is checked in order, from the and check
lower bound to the upper bound, until the item is found [Link] UNTIL you have
or the upper bound is reached checked all values and not
found the value you are looking
for
An example pseudocode algorithm to perform // Input the value to search for
a linear search on a 1D array could be: OUTPUT "Enter the value to search for:"
INPUT Target
DECLARE List : ARRAY[0:4] OF INTEGER
DECLARE Target : INTEGER Found ← FALSE
DECLARE Found : BOOLEAN Index ← 0
DECLARE Index : INTEGER
WHILE Index <= 4 AND Found = FALSE DO
// Initialise array values IF List[Index] = Target THEN
List[0] ← 12 Found ← TRUE
List[1] ← 25 ELSE
List[2] ← 37 Index ← Index + 1
List[3] ← 42 ENDIF
List[4] ← 56 ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at index ", Index
ELSE
OUTPUT "Item not found"
ENDIF
Identifier table
Sorting arrays
How do you perform a bubble
What is a bubble sort?
sort?
A bubble sort is a simple sorting algorithm that starts at
the beginning of a dataset and checks values in 'pairs'
1. Compare the first two values in the
and swaps them if they are not in the correct order
dataset
One full run of comparisons from beginning to end is
2. IF they are in the wrong order : Swap
called a 'pass', a bubble sort may require multiple 'passes'
them
to sort the dataset
3. Compare the next two values
The algorithm is finished when there are no more swaps
4. REPEAT step 2 & 3 until you reach the
to make
end of the dataset (pass 1)
A bubble sort can be used to put elements in an array in
5. IF you have made any swaps :
order
REPEAT from the start (pass 2,3,4...)
6. ELSE you have not made any swaps :
STOP! the list is in the correct order
// Bubble sort algorithm
A pseudocode algorithm for a bubble sort on a FOR Pass ← 1 TO 5
1D array could be: Swapped ← FALSE
FOR Index ← 0 TO 4
DECLARE Numbers : ARRAY[0:5] OF INTEGER IF Numbers[Index] > Numbers[Index + 1] THEN
DECLARE Temp : INTEGER Temp ← Numbers[Index]
DECLARE Pass : INTEGER Numbers[Index] ← Numbers[Index + 1]
DECLARE Index : INTEGER Numbers[Index + 1] ← Temp
DECLARE Swapped : BOOLEAN Swapped ← TRUE
ENDIF
// Initialise the array NEXT Index
Numbers[0] ← 5 IF Swapped = FALSE THEN
Numbers[1] ← 2 // List is already sorted
Numbers[2] ← 4 EXIT
Numbers[3] ← 1 ENDIF
Numbers[4] ← 6 NEXT Pass
Numbers[5] ← 3
// Output the sorted array
FOR Index ← 0 TO 5
OUTPUT Numbers[Index]
NEXT Index
Identifier table
Files
Purpose of files
What is file handling?
File handling is the use of programming techniques to work with information
stored in text files
Examples of file handing techniques are:
opening text files
reading text files
writing text files
closing text files
An example program written in pseudocode to: DECLARE FruitName : STRING
Opens a text file for reading DECLARE FruitCount : INTEGER
Reads each line (a fruit name)
Counts how many fruits are in the file FruitCount ← 0
Outputs the total
Closes the file OPENFILE FruitFile FOR READ
WHILE NOT EOF(FruitFile) DO
Identifier table
READFILE FruitFile, FruitName
FruitCount ← FruitCount + 1
ENDWHILE
CLOSEFILE FruitFile
OUTPUT "Total number of fruits: ", FruitCount
Write program code to read the contents of [Link] into DataArray
Python
try:
DataFile = open("[Link]",'r')
for Line in DataFile:
[Link](int(Line))
[Link]()
except IOError:
print("Could not find file")
Introduction to
Abstract Data
Types (ADT)
What is an abstract data type (ADT)?
An abstract data type (ADT) is a collection of data and a set of operations on that data
A type of data together with the operations (actions) that can be performed on it.
It focuses on what it does, not how it is implemented.
Abstract means:
We do not care how it works inside
We only care about:
What data it stores
What operations we can perform
Three common ADT's are:
Stacks
Queues
Linked lists
Stack A stack is an Abstract Data Type (ADT) that stores data
using the Last In, First Out (LIFO) principle.
operations LIFO means the last item added is the first item
removed.
A stack is like a pile of plates: you add and remove
What is a stack? plates from the top only.
PUSH: adds an item to the top of the stack.
POP: removes the item from the top of the stack.
The first item pushed onto the stack will be the last
item popped off.
A stack uses two pointers:
Base pointer – points to the first item in the stack
(usually does not change).
Top pointer – points to the last item (top of the stack)
and changes after every PUSH or POP operation.
Stack
operations
Main operations
Stacks use a pointer which points to the top of
the stack, where the next piece of data will be
added (pushed) or the current piece of data can
be removed (popped)
Pushing data to a stack
When pushing (adding) data to a stack, the data is pushed to the position of the pointer
Once pushed, the pointer will increment by 1, signifying the top of the stack
Since the stack is a static data structure, an attempt to push an item on to a full stack is called a
stack overflow
Popping data from a stack
When popping (removing) data from a stack, the data is popped from
the position of the pointer
Once popped, the pointer will decrement by 1, to point at the new top
of the stack
Since the stack is a static data structure, an attempt to pop an item
from an empty stack is called a stack underflow
This would pop 'Ant' from the top of the stack
The new top of the stack would become 'Dog'
Popping data from a stack
Note that the data that is ‘popped’ isn’t necessarily erased
The pointer 'top' moves to show that 'Ant' is no longer in the stack and depending on the
implementation, 'Ant' can be deleted or replaced with a null value, or left to be overwritten
Queue operations
What is a queue?
A queue is an Abstract Data Type (ADT) that stores data using the First In, First
Out (FIFO) principle.
FIFO means the first item added is the first item removed.
A queue works like a line of people waiting in a shop: the first person in the line is
the first person served.
ENQUEUE: adds an item to the back (rear) of the queue.
DEQUEUE: removes an item from the front of the queue.
The first item added to the queue will be the first item removed.
A queue uses two pointers:
Front pointer – points to the first item in the queue (the next item to be
removed).
Rear pointer – points to the last item in the queue (where new items are
added).
Queue
operations
Main operations
Linear queues
A linear queue is a type of queue implemented using an array.
It follows the First In, First Out (FIFO) principle.
Items are added (ENQUEUE) to the next available space at the rear
of the queue.
Items are removed (DEQUEUE) from the front of the queue.
The front pointer moves forward when items are removed.
The rear pointer moves forward when items are added.
Once the rear pointer reaches the end of the array, no more items
can be added (even if there is empty space at the front). This is a
limitation of a linear queue.
Linear queues
Before adding an item (ENQUEUE), you must check that
the queue is not full (to avoid overflow).
If the end of the array has not been reached, the rear
pointer is incremented by 1, and the new item is added
at that position.
Example: if Adam, Brian, and Linda are enqueued, they
are added in that order at the rear of the queue.
Before removing an item (DEQUEUE), you must check
that the queue is not empty (to avoid underflow).
If the queue is not empty, the item at the front of the
queue is returned (removed), and the front pointer is
incremented by 1.
Example: if Adam, Brian, and Linda are in the queue,
when you dequeue, Adam (the first item added) is
removed first.
Queue operations
Circular queues
A circular queue is a queue implemented using a static array with fixed size (fixed capacity).
When items are added, the rear pointer moves forward through the array.
Eventually, the rear pointer reaches the end of the array.
When items are removed (DEQUEUE), empty spaces appear at the beginning of the array.
In a linear queue, these spaces are wasted. Moving all items to the front would take extra time.
To solve this problem, a circular queue (circular buffer) is used.
It reuses empty spaces at the front of the array.
When the rear pointer reaches the last position of the array, it wraps around to the start (index 0), as
long as the queue is not full.
When items are dequeued, the front pointer also moves forward, and it can also wrap around to the
start.
The queue is full when adding another item would make the rear pointer equal to the front pointer.
The queue is empty when the front pointer passes the rear pointer (or when both pointers are equal,
depending on implementation).
Circular queues
Before adding an item (ENQUEUE) to a circular queue,
you must check that the queue is not full.
The queue is full if the next position of the rear pointer is
already occupied by the item at the front of the queue
(meaning the rear would catch up to the front).
If the queue is not full, the rear pointer is moved to the
next position (wrapping around to index 0 if needed).
The new item is then added in that free position.
Example: if the next free position is available, Lauren is
enqueued at the new rear position.
Circular queues
Before removing an item (DEQUEUE) from a circular
queue, you must check that the queue is not empty.
If the queue is not empty, the item at the front of the
queue is returned (removed).
If this was the only item in the queue, both front and
rear pointers are reset to indicate the queue is empty.
Otherwise, the front pointer moves to the next position
(wrapping around to the start of the array if needed).
Example: if Adam is at the front, he is dequeued and the
front pointer moves to the next item in the queue.
Linked list operations
A linked list is an Abstract Data Type (ADT) where each item, called a node, contains data
and a pointer to the next node in the sequence.
It is like a chain of items, where each node stores:
The actual data
A pointer to the next node in the list
New items are usually added at the start of the list, and each node links to the next.
Think of it like a scavenger hunt, where each clue tells you where to go next.
Each node contains a data field (the information) and a pointer (the address of the next
node).
For example:
Start = 1 NextFree = 3
The data field contains the value of the actual data which is part of the list
The pointer field contains the address of the next item in the list
Traverse a linked list
Check if the linked list is empty
Start at the node the pointer is pointing to (Start = 1)
Output the item at the current node ('Pineapple')
Follow the pointer to the next node repeating through each node until the end of the
linked list.
When the pointer field is empty/null it signals that the end of the linked list has been
reached
Traversing the example above would produce: ‘Pineapple’, ‘Apple’, ‘Melon’
Adding a node
An advantage of using linked lists is that values can easily be added or removed by
editing the points
The following example will add the word ‘Orange’ after the word ‘Pineapple’
1. Check there is free memory to insert data into the node
2. Add the new value to the end of the linked list and update the ‘NextFree’ pointer
Start = 1 NextFree = 4
3. The pointer field of the word ‘Pineapple’ is updated to point to ‘Orange’, at position 3
4. The pointer field of the word ‘Orange’ is updated to point to ‘Apple’ at position 0
5. When traversed this linked list will now output: ‘Pineapple’, ‘Orange’, ‘Apple’, ‘Melon’
Removing a node
Removing a node also involves updating nodes, this time to bypass the deleted node
The following example will remove the word ‘Apple’ from the original linked list
1. Update the pointer field of ‘Pineapple’ to point to ‘Melon’ at index 2
2. When traversed this linked list will now output: ‘Pineapple’, ‘Melon’
The node is not truly removed from the list; it is only ignored
Although this is easier it does waste memory
Storing pointers themselves also means that more memory is required compared to an array
Items in a linked list are also stored in a sequence, they can only be traversed within that order so an
item cannot be directly accessed as is possible in an array