CS · Chapter 13

Cambridge AS & A Level · Part 2 · Chapter 13

Data Types and Structures

Choosing the right data type, grouping data into records, arrays and text files, and building stacks, queues and linked lists from plain arrays. Every worked example, task, figure and exam-style question from the chapter is here, with labs that run the book's algorithms one step at a time.

Guru Jazzy

🎯 Learning objectives

By the end of this chapter you should be able to:

select and use suitable data types: INTEGER, REAL, CHAR, STRING, BOOLEAN, DATE, ARRAY, FILE
explain why a record structure holds data of different types under one identifier
write pseudocode to define a record type, and to read from and save to a record
use array terms: index, upper bound, lower bound
Choose a 1D or 2D array for a task
write pseudocode to process arrays, including a bubble sort and a linear search

Explain why files are needed
write pseudocode to handle text files of one or more lines
explain that an Abstract Data Type (ADT) is a collection of data plus a set of operations on it
recognise a stack, queue and linked list as ADTs, describe their key features and justify using one
use a stack, queue and linked list to store, add, edit and delete data
describe how each can be implemented using arrays

🔢 13.01 Data types

Primitive data types

In Chapter 12 every variable went into an identifier table. That table should also say what kind of data each variable holds. In Worked Example 12.01, Miles is always a whole number, but Km is worked out as Miles * 1.61, which usually is not.

Primitive (or atomic) data types are the ones a programming language provides with built-in commands:

a whole number is an INTEGER, for example the counter of a loop
A number with a decimal point is a REAL
TRUE or FALSE is a BOOLEAN
A single character is a CHAR

Tip Chapter 1 (Sections 1.02 and 1.03) shows how integers and characters are stored inside the computer. Chapter 16 (Section 16.03) covers how real numbers (single, double, float) are stored.

Further data types

Several characters together make a STRING. The number 12 and the string "12" are different things: you can do arithmetic with one but not the other.
A string is a structured type, because it is really a sequence of characters. The empty string "" is still a string; it just holds no characters.
A date such as 3 February 2018 can be written as three numbers, 3/2/2018. Because we often want to calculate with dates (how many days between two of them?), DATE is its own data type. Chapter 14, Section 14.03 shows how different languages handle it.

Type	Meaning	Example value
INTEGER	A signed whole number	-7, 0, 2019
REAL	A signed number with a decimal point	44.95, -0.5
CHAR	A single character	'X'
STRING	A sequence of zero or more characters	"Fred", ""
BOOLEAN	The logical values TRUE and FALSE	TRUE
DATE	Day, month and year, sometimes with a time in hours, minutes and seconds	03/02/2018

Table 13.01 Summary of pseudocode data types

🎮 Pick the data type

What is the best data type for each value? Watch out for values that look like numbers but are not used as numbers.

Task 13.01 Look at the identifier tables in Chapter 12 (Tables 12.06 and 12.09 to 12.12). Give the data type that suits each variable listed.

For each variable ask three questions:

Is it only ever TRUE or FALSE? → BOOLEAN (flags such as Found, NoMoreSwaps).
Is it a number you will count or calculate with? Whole numbers (counters, indexes, totals of items) → INTEGER. Anything that can have a fractional part (kilometres, prices, averages) → REAL.
Otherwise it is text: one character → CHAR, more → STRING. Phone numbers, ISBNs and codes such as "034AB45" are STRINGs even if they look numeric, because you never do arithmetic on them and a leading 0 must be kept.

🗂️ 13.02 The record type

Sometimes variables of different types belong together, like the data about one person: name (STRING), date of birth (DATE), height (REAL), number of siblings (INTEGER) and whether they study full time (BOOLEAN).

A record type groups them. It is a user-defined type: the programmer decides which variables (fields) a record holds.

Tip A record type is also known as a composite type.

Declaring the type

TYPE <TypeIdentifier>
   DECLARE <field identifier> : <data type>
   .
   .
ENDTYPE

Declaring a variable of that type

DECLARE <variable identifier> : <record type>

Reaching one field: dot notation

<variable identifier>.<field identifier>

The Person example

TYPE PersonType
   DECLARE Name : STRING
   DECLARE DateOfBirth : DATE
   DECLARE Height : REAL
   DECLARE NumberOfSiblings : INTEGER
   DECLARE IsFullTimeStudent : BOOLEAN
ENDTYPE

DECLARE Person : PersonType

Person.Name ← "Fred"
Person.NumberOfSiblings ← 3
Person.IsFullTimeStudent ← TRUE

OUTPUT Person.Name

The book's own listing leaves out DECLARE inside this TYPE block; the Cambridge 9618 pseudocode guide puts it in, as shown here.

🔬 Lab: fill in a PersonType record

Type a value for each field and press Assign. The lab checks each value against the field's data type and writes the pseudocode assignments for you.

Fields are empty.

Task 13.02 Write the declaration of a record type to store the details of a book: Title, Year of publication, Price, ISBN. Then write the statements that assign "Computer Science", 2019, £44.95 and "9781108733755" to the fields.

TYPE BookType
   DECLARE Title : STRING
   DECLARE YearOfPublication : INTEGER
   DECLARE Price : REAL
   DECLARE ISBN : STRING      // digits, but never used in arithmetic
ENDTYPE

DECLARE Book : BookType
Book.Title ← "Computer Science"
Book.YearOfPublication ← 2019
Book.Price ← 44.95
Book.ISBN ← "9781108733755"

📦 13.03 Arrays

When we want a list or a table (matrix) of values, most languages give us arrays. An array is an ordered set of data items, usually of the same type, grouped under one identifier. Each element is reached with an array index for each dimension.

A list is a one-dimensional (1D) array; a table or matrix is a two-dimensional (2D) array.

Tip In pseudocode an array must be declared before it is used: choose an identifier, the data type of its values, and the upper bound and lower bound of each dimension.

Array index: the row or column number of an individual array element
Upper bound: the highest index number of an array dimension
Lower bound: the smallest index number of an array dimension

📏 13.04 One-dimensional arrays

On paper we usually number a list from 1. Many languages (VB.NET, Python, Java) number array elements from 0, the lower bound. Depending on the problem, it can make sense to ignore element 0. The upper bound is the largest index used.

Declaring

DECLARE <arrayIdentifier> : ARRAY[<lowerBound>:<upperBound>] OF <dataType>

DECLARE List1 : ARRAY[1:3] OF STRING    // 3 elements
DECLARE List2 : ARRAY[0:5] OF INTEGER   // 6 elements
DECLARE List3 : ARRAY[1:100] OF INTEGER // 100 elements
DECLARE List4 : ARRAY[0:25] OF CHAR     // 26 elements

Accessing

<arrayIdentifier>[x]

NList[25] ← 0    // set 25th element to zero
AList[3] ← 'D'   // set 3rd element to letter D

The nth element of MyList is MyList[n]. (If the lower bound is 0, NList[25] is really the 26th element; the book's comments assume counting from 1.)

🎯 Bounds practice

How many elements does each declaration create? New numbers every time.

🧮 Worked Example 13.01 Working with a 1D array

Problem: take seven numbers as input and store them for later use.

Seven separate variables would work, but not for 70 numbers. Instead we use a linear list, a 1D array called MyList. MyList[4] is the element at position 4; counting position 0 as the first, that is the fifth element. A loop visits each element in turn:

FOR Index ← 0 TO 6
   INPUT MyList[Index]
NEXT Index

**Figure 13.01**MyList array filled by a loop

With inputs 25, 34, 98, 7, 41, 19 and 5 the array is filled as in Figure 13.01.

Task 13.03 Define two arrays, one for your friends' names and one for their ages, as shown in Figure 13.02.

**Figure 13.02**Arrays for names and ages

DECLARE Name : ARRAY[0:19] OF STRING
DECLARE Age  : ARRAY[0:19] OF INTEGER

Indexes 0 to 19 give 20 friends. The two arrays are parallel: Name[i] and Age[i] describe the same person.

🔍 Worked Example 13.02 Linear search

Problem: input a number and search for it in the seven-number array from Worked Example 13.01. Start at the first element and check each one in turn until the value is found or the end of the array is reached. This is a linear search.

Identifier	Data type	Explanation
MyList	ARRAY[0:6] OF INTEGER	1D array that stores seven numbers
MaxIndex	INTEGER	The index of the last element (the book says "number of elements"; with indexes 0–6 it is really the upper bound, 6)
SearchValue	INTEGER	The value to search for
Found	BOOLEAN	TRUE if the value has been found; FALSE if not
Index	INTEGER	Index of the element being checked

Table 13.02 Identifier table for the linear search algorithm

MaxIndex ← 6
INPUT SearchValue
Found ← FALSE
Index ← -1
REPEAT
   Index ← Index + 1
   IF MyList[Index] = SearchValue
      THEN
         Found ← TRUE
   ENDIF
UNTIL Found = TRUE OR Index >= MaxIndex
IF Found = TRUE
   THEN
      OUTPUT "Value found at location: ", Index
   ELSE
      OUTPUT "Value not found"
ENDIF

The compound condition on REPEAT…UNTIL exits as soon as the value is found. The flag Found makes the algorithm easier to read: it is initialised to FALSE before the loop and set to TRUE on a match.

If the value is missing, the loop stops when Index >= MaxIndex, the end of the array. Because the loop tests MaxIndex rather than the number 6, the algorithm works for any array size by changing only the first line.

Linear search: checking each element of an array in turn for a required value

🔬 Lab: trace the linear search

SearchValue

Task 13.04 Use the algorithm in Worked Example 13.02 as a design pattern. Write an algorithm that uses the arrays from Task 13.03 to search for a friend's name and output their age.

MaxIndex ← 19
INPUT SearchName
Found ← FALSE
Index ← -1
REPEAT
   Index ← Index + 1
   IF Name[Index] = SearchName
      THEN
         Found ← TRUE
   ENDIF
UNTIL Found = TRUE OR Index >= MaxIndex
IF Found = TRUE
   THEN
      OUTPUT SearchName, " is ", Age[Index], " years old"
   ELSE
      OUTPUT "Friend not found"
ENDIF

Only three things change from the design pattern: MaxIndex, the array that is searched, and the output, which uses the same index in the parallel Age array.

🫧 Worked Example 13.03 Bubble sort

The simplest way to sort an unordered list:

Compare the first and second values. If the first is larger, swap them.
Compare the second and third values. If the second is larger, swap them.
Compare the third and fourth values, and so on…
Keep comparing adjacent values, swapping if necessary, until the last two values have been processed.

**Figure 13.03**Swapping values working down the array (first pass)

After the first pass the largest value is in its correct place at the end. The others may still be out of order, so we pass through again and again. After each pass the next largest value is in place (Figure 13.04). That is a loop inside a loop: a nested loop. The method is called a bubble sort, because small values slowly rise to the top like bubbles in a liquid.

**Figure 13.04**States of the array after each pass

Identifier	Data type	Explanation
MyList	ARRAY[0:6] OF INTEGER	Seven numbers
MaxIndex	INTEGER	Upper bound of the array
n	INTEGER	Number of pairs to compare in each pass
i	INTEGER	Outer loop counter
j	INTEGER	Inner loop counter
Temp	INTEGER	Temporary store while swapping

Table 13.03 Identifier table for bubble sort

n ← MaxIndex - 1
FOR i ← 0 TO MaxIndex - 1
   FOR j ← 0 TO n
      IF MyList[j] > MyList[j + 1]
         THEN
            Temp ← MyList[j]
            MyList[j] ← MyList[j + 1]
            MyList[j + 1] ← Temp
      ENDIF
   NEXT j
   n ← n - 1  // next time round the inner loop we don't
              // look at values already in the right place
NEXT i

Improving it: stop when no swaps happen

The values may be in order before the outer loop has finished. The list in Figure 13.05 differs only slightly from the first one, and it is sorted after pass 3, yet the algorithm carries on for three more passes of pointless comparisons.

**Figure 13.05**States of a nearly sorted list after each pass

If a whole pass makes no swaps, the array must be in order. So the outer FOR loop becomes a conditional loop, controlled by a flag NoMoreSwaps: set to TRUE at the start of each pass, and to FALSE whenever a swap happens.

Identifier	Data type	Explanation
MyList	ARRAY[0:6] OF INTEGER	Seven numbers
MaxIndex	INTEGER	Upper bound of the array
n	INTEGER	Pairs to compare in each pass
NoMoreSwaps	BOOLEAN	TRUE when no swaps have happened in the current pass; FALSE when a swap has
j	INTEGER	Inner loop counter
Temp	INTEGER	Temporary store while swapping

Table 13.04 Identifier table for the improved bubble sort

n ← MaxIndex - 1
REPEAT
   NoMoreSwaps ← TRUE
   FOR j ← 0 TO n
      IF MyList[j] > MyList[j + 1]
         THEN
            Temp ← MyList[j]
            MyList[j] ← MyList[j + 1]
            MyList[j + 1] ← Temp
            NoMoreSwaps ← FALSE
      ENDIF
   NEXT j
   n ← n - 1
UNTIL NoMoreSwaps = TRUE

Bubble sort: a sort method where adjacent pairs of values are compared and swapped

🔬 Lab: bubble sort, one comparison at a time

Basic (FOR loop) Improved (NoMoreSwaps)

Discussion point: What happens if the array elements are already in the correct order?

The basic version still makes every pass: for 7 items that is 6 + 5 + 4 + 3 + 2 + 1 = 21 comparisons and no swaps at all. The improved version makes one pass of 6 comparisons, finds no swaps, and stops. Try "Already sorted" in the lab with each mode. This is the best case for the improved bubble sort.

Task 13.05 Rewrite the algorithm in Worked Example 13.03 to sort the array into descending order.

Only the comparison changes, from > to <, so the smaller value of each pair is moved towards the end:

n ← MaxIndex - 1
REPEAT
   NoMoreSwaps ← TRUE
   FOR j ← 0 TO n
      IF MyList[j] < MyList[j + 1]
         THEN
            Temp ← MyList[j]
            MyList[j] ← MyList[j + 1]
            MyList[j + 1] ← Temp
            NoMoreSwaps ← FALSE
      ENDIF
   NEXT j
   n ← n - 1
UNTIL NoMoreSwaps = TRUE

🔲 13.05 Two-dimensional arrays

When we refer to one cell of a table on paper, we give the row first and then the column. A 2D array is declared the same way: number of rows first, then columns, each with its own lower and upper bound.

DECLARE <identifier> : ARRAY[<lBound1>:<uBound1>,
                             <lBound2>:<uBound2>] OF <dataType>

// a game board of 6 rows and 7 columns
Board : ARRAY[1:6,1:7] OF INTEGER

<arrayIdentifier>[x,y]

Board[3,4] ← 0  // row 3, column 4 set to zero

Elements can be numbered from 0, but sometimes it is more natural to count rows and columns from 1, as with the board game in Worked Example 13.05.

To visit every element of a 1D array we use one loop. A 2D array needs a loop for each row and, inside it, a loop for each column: nested loops.

For each row
   For each column
      Assign the initial value to the element
      at the current position

🧮 Worked Example 13.04 2D arrays and nested loops

Set every element of ThisTable to zero:

FOR Row ← 0 TO MaxRowIndex
   FOR Column ← 0 TO MaxColumnIndex
      ThisTable[Row, Column] ← 0
   NEXT Column
NEXT Row

Output the table, one row per line:

FOR Row ← 0 TO MaxRowIndex
   FOR Column ← 0 TO MaxColumnIndex
      OUTPUT ThisTable[Row, Column] // stay on same line
   NEXT Column
   OUTPUT Newline  // move to next line for next row
NEXT Row

Identifier	Data type	Explanation
ThisTable	ARRAY[0:3, 0:5] OF INTEGER	2D array that stores the values
MaxRowIndex	INTEGER	Upper bound of the row index
MaxColumnIndex	INTEGER	Upper bound of the column index
Row	INTEGER	Row counter
Column	INTEGER	Column counter

Table 13.05 Identifier table for working with a table

🔬 Lab: watch the nested loops

The inner loop (columns) finishes completely before the outer loop (rows) moves on. Press Step to fill ThisTable : ARRAY[0:3, 0:5].

Task 13.06

Declare a 2D array to store the board for Noughts and Crosses. Empty squares are a space; player A's counters are "O" and player B's are "X".
Initialise the array so every square is empty.
Write a statement for player A placing a counter in the top-left square.
Write a statement for player B placing a counter in the middle square.

DECLARE Board : ARRAY[1:3, 1:3] OF CHAR       // 1

FOR Row ← 1 TO 3                              // 2
   FOR Column ← 1 TO 3
      Board[Row, Column] ← ' '
   NEXT Column
NEXT Row

Board[1, 1] ← 'O'                             // 3  top left
Board[2, 2] ← 'X'                             // 4  middle

🔴 Worked Example 13.05 A program to play Connect 4

Connect 4 is a game for two players. In the commercial version (Figure 13.06) one player has red tokens and the other black, 21 each. The board is a vertical grid of six rows and seven columns.

Players take turns to choose a column that is not full and drop a token into it. It lands in the lowest empty position. The first player to connect four of their tokens in a horizontal, vertical or diagonal line wins. If all tokens are used and nobody has four in a line, it is a draw.

On the computer the players are 'O' and 'X' and the board is a 2D array. To keep the problem simple, a player wins with four in a row horizontally or vertically only.

First attempt in structured English

Initialise board
Set up game
Display board
While game not finished
   Player makes a move
   Display board
   Check if game finished
   If game not finished, swap player

Top-level pseudocode using modules

01 CALL InitialiseBoard
02 CALL SetUpGame
03 CALL OutputBoard
04 WHILE GameFinished = FALSE DO
05    CALL PlayerMakesMove
06    CALL OutputBoard
07    CALL CheckGameFinished
08    IF GameFinished = FALSE
09       THEN
10          CALL SwapThisPlayer
11    ENDIF
12 ENDWHILE

Steps 03 and 06 are the same: the OutputBoard module is written once and called from two places. That is one of the advantages of modules.

Identifier	Data type	Explanation
Board	ARRAY[1:6,1:7] OF CHAR	2D array that represents the board
InitialiseBoard		Procedure to set the whole board to blanks
SetUpGame		Procedure to set initial values for `GameFinished` and `ThisPlayer`
GameFinished	BOOLEAN	FALSE if the game is not finished; TRUE if the board is full or a player has won
ThisPlayer	CHAR	'O' when it is player O's turn; 'X' when it is player X's turn
OutputBoard		Procedure to output the current board
PlayerMakesMove		Procedure to place the current player's token in the chosen location
CheckGameFinished		Procedure to check whether the token just placed wins, or the board is full
SwapThisPlayer		Procedure to change the player's turn

Table 13.06 Initial identifier table for the Connect 4 game

Now each module is refined. Each refinement adds identifiers, which are listed after it.

PROCEDURE InitialiseBoard
   FOR Row ← 1 TO 6
      FOR Column ← 1 TO 7
         Board[Row, Column] ← BLANK // use a suitable value for blank
      NEXT Column
   NEXT Row
ENDPROCEDURE

PROCEDURE SetUpGame
   ThisPlayer ← 'O'   // Player O always starts
   GameFinished ← FALSE
ENDPROCEDURE

PROCEDURE OutputBoard
   FOR Row ← 6 DOWNTO 1
      FOR Column ← 1 TO 7
         OUTPUT Board[Row, Column] // don't move to next line
      NEXT Column
      OUTPUT Newline // move to next line
   NEXT Row
ENDPROCEDURE

Additional identifiers (Table 13.07): Row INTEGER (loop counter for rows), Column INTEGER (loop counter for columns), BLANK CHAR (the value for an empty location). OutputBoard counts rows down from 6, because row 1 is the bottom of the board and must be printed last.

PROCEDURE PlayerMakesMove
   ValidColumn ← PlayerChoosesColumn // a module returns column number
   ValidRow ← FindFreeRow            // a module returns row number
   Board[ValidRow, ValidColumn] ← ThisPlayer
ENDPROCEDURE

FUNCTION PlayerChoosesColumn RETURNS INTEGER // returns a valid column number
   OUTPUT "Player ", ThisPlayer, "'s turn."
   REPEAT
      OUTPUT "Enter a valid column number: "
      INPUT ColumnNumber
   UNTIL ColumnNumberValid = TRUE // check whether the column number is valid
   RETURN ColumnNumber
ENDFUNCTION

FUNCTION ColumnNumberValid RETURNS BOOLEAN
// returns whether or not the column number is valid
   Valid ← FALSE
   IF ColumnNumber >= 1 AND ColumnNumber <= 7
      THEN
         IF Board[6, ColumnNumber] = BLANK // at least 1 empty space in column
            THEN
               Valid ← TRUE
         ENDIF
   ENDIF
   RETURN Valid
ENDFUNCTION

FUNCTION FindFreeRow RETURNS INTEGER
// returns the next free position
   ThisRow ← 1
   WHILE Board[ThisRow, ValidColumn] <> BLANK DO // find first empty cell
      ThisRow ← ThisRow + 1
   ENDWHILE
   RETURN ThisRow
ENDFUNCTION

Identifier	Data type	Explanation
ValidColumn	INTEGER	The column number the player has chosen
PlayerChoosesColumn	INTEGER	Function to get the current player's valid choice of column
ValidRow	INTEGER	The first free row in the chosen column
FindFreeRow	INTEGER	Function to find the next free location in the chosen column
ColumnNumber	INTEGER	The column number chosen by the current player
ColumnNumberValid	BOOLEAN	Function to check whether the chosen column is valid: in the range 1 to 7 with at least one empty location
Valid	BOOLEAN	FALSE if the column number is not valid; TRUE if it is
ThisRow	INTEGER	Points to the next row to be checked

PROCEDURE CheckGameFinished
   WinnerFound ← FALSE
   CALL CheckIfPlayerHasWon
   IF WinnerFound = TRUE
      THEN
         GameFinished ← TRUE
         OUTPUT ThisPlayer, " is the winner"
      ELSE
         CALL CheckForFullBoard
   ENDIF
ENDPROCEDURE

PROCEDURE CheckIfPlayerHasWon
   WinnerFound ← FALSE
   CALL CheckHorizontalLine
   IF WinnerFound = FALSE
      THEN
         CALL CheckVerticalLine
   ENDIF
ENDPROCEDURE

PROCEDURE CheckHorizontalLine
   FOR i ← 1 TO 4
      IF Board[ValidRow, i] = ThisPlayer AND
         Board[ValidRow, i + 1] = ThisPlayer AND
         Board[ValidRow, i + 2] = ThisPlayer AND
         Board[ValidRow, i + 3] = ThisPlayer
         THEN
            WinnerFound ← TRUE
      ENDIF
   NEXT i
ENDPROCEDURE

PROCEDURE CheckVerticalLine
   IF ValidRow = 4 OR ValidRow = 5 OR ValidRow = 6
      THEN
         IF Board[ValidRow, ValidColumn] = ThisPlayer AND
            Board[ValidRow - 1, ValidColumn] = ThisPlayer AND
            Board[ValidRow - 2, ValidColumn] = ThisPlayer AND
            Board[ValidRow - 3, ValidColumn] = ThisPlayer
            THEN
               WinnerFound ← TRUE
         ENDIF
   ENDIF
ENDPROCEDURE

PROCEDURE CheckForFullBoard
   BlankFound ← FALSE
   ThisRow ← 0
   REPEAT
      ThisColumn ← 0
      ThisRow ← ThisRow + 1
      REPEAT
         ThisColumn ← ThisColumn + 1
         IF Board[ThisRow, ThisColumn] = BLANK
            THEN
               BlankFound ← TRUE
         ENDIF
      UNTIL ThisColumn = 7 OR BlankFound = TRUE
   UNTIL ThisRow = 6 OR BlankFound = TRUE
   IF BlankFound = FALSE
      THEN
         OUTPUT "It is a draw"
         GameFinished ← TRUE
   ENDIF
ENDPROCEDURE

PROCEDURE SwapThisPlayer
   IF ThisPlayer = 'O'
      THEN
         ThisPlayer ← 'X'
      ELSE
         ThisPlayer ← 'O'
   ENDIF
ENDPROCEDURE

Additional identifiers: WinnerFound BOOLEAN (TRUE if a winning line is found), CheckIfPlayerHasWon, CheckHorizontalLine, CheckVerticalLine and CheckForFullBoard (procedures), BlankFound BOOLEAN, ThisRow and ThisColumn INTEGER loop counters.

Book slip Table 13.12 lists a procedure called CheckVerticalLineInValidColumn, but the code calls it CheckVerticalLine, and CheckHorizontalLine is missing from the table. The names above match the code. Also, a vertical line can only end on the token just placed, which is why only ValidRow 4, 5 or 6 can complete one.

Teacher's note Tokens fill each column from row 1 upwards, so the board is full exactly when row 6 is full. CheckForFullBoard could just check Board[6, 1] to Board[6, 7].

🎮 Play the book's Connect 4

Two players share the screen. Choose a column (tap a ▼ button, or use keys 1–7). The log shows which module runs and which array element changes. Like the book, only horizontal and vertical lines win.

👥 Arrays of records

Using PersonType from Section 13.02, we can declare an array of 100 person records and reach each person's fields:

DECLARE Person : ARRAY[1:100] OF PersonType

Person[1].Name ← "Fred"
OUTPUT Person[1].Name

This is very useful when we have several people's data and do not want a separate 1D array for every field.

Task 13.07

Declare an array of BookType (see Task 13.02) for 200 books.
Set the first book's details to the values given in Task 13.02.

DECLARE Book : ARRAY[1:200] OF BookType

Book[1].Title ← "Computer Science"
Book[1].YearOfPublication ← 2019
Book[1].Price ← 44.95
Book[1].ISBN ← "9781108733755"

📄 13.06 Text files

Data in an array disappears when the program stops. To keep data permanently, save it to a file and read it back the next time the program runs.

A text file is a sequence of characters arranged in lines. Each line ends with an end-of-line marker, and the file ends with an end-of-file marker.

Tip You can check what a text file contains, or create one that a program needs, with a text editor such as Notepad.

Writing to a text file

Writing usually means creating the file (any old contents are replaced).

OPENFILE <filename> FOR WRITE   // open the file for writing
WRITEFILE <filename>, <stringValue> // write a line of text
CLOSEFILE <filename>            // close file

Reading from a text file

OPENFILE <filename> FOR READ    // open file for reading
READFILE <filename>, <stringVariable> // read a line of text
CLOSEFILE <filename>            // close file

Appending to a text file

Append mode adds new data to the end of an existing file instead of creating a new one.

OPENFILE <filename> FOR APPEND  // open file for append
WRITEFILE <filename>, <stringValue> // write a line of text
CLOSEFILE <filename>            // close file

The end-of-file (EOF) marker

To read a whole file we use a conditional loop and test for the end-of-file marker. The function EOF() returns FALSE while there is more to read and TRUE once the marker is reached. REPEAT…UNTIL EOF() works, but if the file might be empty, WHILE NOT EOF() is better, because it tests before the first read.

OPENFILE "Test.txt" FOR READ
WHILE NOT EOF("Test.txt") DO
   READFILE "Test.txt", TextString
   OUTPUT TextString
ENDWHILE
CLOSEFILE "Test.txt"

🔬 Lab: a text file you can open, write, append and read

Run the file statements yourself on "Test.txt". Try writing after opening FOR READ, or reading past the end, to see the errors a real program would hit.

Mode

Test.txt

Task 13.08

Write pseudocode to save the array data from Task 13.06 to a text file.
Write pseudocode to read the values stored in the text file back into the board array.

Write each square on its own line, row by row, so the file always has exactly 9 lines. Then read them back in the same order.

// 1 save the board
OPENFILE "Board.txt" FOR WRITE
FOR Row ← 1 TO 3
   FOR Column ← 1 TO 3
      WRITEFILE "Board.txt", Board[Row, Column]
   NEXT Column
NEXT Row
CLOSEFILE "Board.txt"

// 2 load the board
OPENFILE "Board.txt" FOR READ
FOR Row ← 1 TO 3
   FOR Column ← 1 TO 3
      READFILE "Board.txt", LineOfText   // LineOfText : STRING
      Board[Row, Column] ← LineOfText    // one character: ' ', 'O' or 'X'
   NEXT Column
NEXT Row
CLOSEFILE "Board.txt"

A FOR loop is fine here because we know the file holds 9 lines. For a file of unknown length use WHILE NOT EOF(). An alternative is one line per row, joining the three characters with &.

🧩 13.07 Abstract Data Types (ADTs)

An Abstract Data Type is a collection of data together with a set of operations that:

create a new instance of the data structure
Find an element in it
Insert a new element into it
Delete an element from it
access all its elements in a systematic way

Abstract Data Type: a collection of data with associated operations

The rest of the chapter describes three ADTs (the stack, the queue and the linked list) and shows how to build each one from arrays. Each data item here is a single character, but in a real program it would usually be a set of data, perhaps the fields of a record.

🥞 13.08 Stacks

Think of a real stack: items are piled on top of each other, and only the top item can be reached. Try to pull one out of the middle and the pile collapses. The last item added is the first one removed: LIFO (last in, first out).

**Figure 13.07**An empty stack and a stack with four items pushed

Slots are numbered from the bottom, which feels more natural for a stack.
BaseOfStackPointer always points to the first slot.
TopOfStackPointer points to the last item pushed (added). When an item is popped (removed), it goes down by one to the new top item.
When the stack is empty, TopOfStackPointer is −1.

DECLARE Stack : ARRAY[0:7] OF CHAR

🔬 Lab: stack in an array

Task 13.09

Draw the stack in Figure 13.07 after "E" has been pushed.
Draw the stack in Figure 13.07 after one item has been popped.

1 E goes into slot 4. TopOfStackPointer = 4, BaseOfStackPointer = 0.

4  E  ← TopOfStackPointer
3  D
2  C
1  B
0  A  ← BaseOfStackPointer

2 D is popped. TopOfStackPointer = 2. (D may still be in slot 3 of the array, but it is no longer part of the stack and will be overwritten by the next push.)

3
2  C  ← TopOfStackPointer
1  B
0  A  ← BaseOfStackPointer

Use the lab to check: load Figure 13.07, then Push E, or Pop.

🚶 13.09 Queues

In a real, orderly queue people join at the end and leave from the front. Nobody pushes in and nobody leaves from the middle. The first item in is the first out: FIFO.

**Figure 13.08**An empty queue and a queue after five items have joined

A simple array version keeps the front at position 0. An empty queue has EndOfQueuePointer = −1. To join, increment EndOfQueuePointer and then store the item there. When the front item leaves, every other item moves forward one slot and EndOfQueuePointer goes down by one.

Task 13.10

Draw the queue after "F" has joined the non-empty queue in Figure 13.08.
Draw the queue after one item has left the non-empty queue in Figure 13.08.

0  A  ← FrontOfQueuePointer
1  B
2  C
3  D
4  E
5  F  ← EndOfQueuePointer
6
7

0  B  ← FrontOfQueuePointer
1  C
2  D
3  E  ← EndOfQueuePointer
4
5
6
7

(1) F joins at slot 5. (2) A leaves: B, C, D and E each move up one slot, and EndOfQueuePointer falls from 4 to 3.

The circular queue

All that moving of data is slow. A better idea is a circular queue: the data stays where it is and two pointers mark the front and the end. When the end reaches the last slot it wraps around to slot 0. Figure 13.09 shows a circular queue after 11 items have joined and 5 have left.

**Figure 13.09**A circular queue after 11 items have joined and 5 have left

🔬 Lab: linear queue vs circular queue

Linear (items shuffle forward) Circular (pointers wrap)

🔗 13.10 Linked lists

In Section 13.03 an array was a linear list: items in consecutive locations. That is not always suitable. Another way is to store each item wherever there is space and link the items into order with pointers.

Node: an element of a list
Pointer: a variable that stores the address of the node it points to
Null pointer: a pointer that does not point at anything (shown as Ø)
Start pointer: a variable that stores the address of the first element of a linked list

In the diagrams the value in each node box is its key field; a real node would hold many data items. The arrows are pointers. They show where a node conceptually links to, not the actual address.

**Figure 13.10**Conceptual diagram of a linked list

Changing the list: only pointers move

Add at the start (Figure 13.11): copy StartPointer into the new node's pointer, then point StartPointer at the new node A.

**Figure 13.11**Adding a new node to the beginning of a linked list

Add at the end (Figure 13.12): node L's pointer now points to the new node P, and P's pointer is the null pointer.

**Figure 13.12**Adding a new node to the end of a linked list

Delete the first node (Figure 13.13): copy the deleted node's pointer into StartPointer.

**Figure 13.13**Deleting the first node in a linked list

Delete the last node (Figure 13.14): set the previous node's pointer to null.

**Figure 13.14**Deleting the last node of a linked list

An ordered linked list keeps its nodes in key order, so a node may have to go between two others.

Insert C between B and D (Figure 13.15): copy B's pointer into C's pointer, then point B at C.

**Figure 13.15**Adding a new node into a linked list

Delete D from the middle (Figure 13.16): copy D's pointer into B's pointer.

**Figure 13.16**Deleting a node within a linked list

Why bother? Real data is much more than one key field. To reorder a linked list only the pointers change; in a linear list every data item would have to move. A linked list saves time but needs more storage for the pointer fields.

🧱 Implementing a linked list with arrays

Use one 1D array for the data and another for the pointers. Reading across both arrays at the same index gives one node. A new value goes into the next free element of Data, and pointers are adjusted to link it into the right place.

**Figure 13.17**Using arrays to implement the linked list in Figure 13.10

The linked list from Figure 13.10 in two arrays: StartPointer = 1 → B(1) → D(2) → L(0) → −1

**Figure 13.18**Adding a new node to the beginning of a linked list (arrays)

Add A at the start: A stored at index 3 with pointer 1; StartPointer becomes 3

**Figure 13.19**Adding a new node to the end of a linked list (arrays)

Add P at the end: P stored at index 3 with pointer −1; L's pointer (index 0) becomes 3

**Figure 13.20**Deleting the first node in a linked list (arrays)

Delete the first node: StartPointer takes B's pointer value, 2. The old data stays but nothing points to it.

**Figure 13.21**Deleting the last node of a linked list (arrays)

Delete the last node: the penultimate node D (index 2) gets the null pointer −1

**Figure 13.22**Adding a new node into a linked list (arrays)

Insert C: stored in any free element (index 3). Its pointer takes B's old pointer (2), and B now points to 3

**Figure 13.23**Deleting a node within a linked list (arrays)

Delete D: D's pointer (0) is copied into the preceding node B

The free list

Unused nodes must be easy to find, so they are linked into a second linked list: the free list, with its own pointer FreeListPtr.

**Figure 13.24**A linked list and a free list

When the arrays are first set up the linked list is empty, so StartPointer is null (−1) and every node is linked into the free list (Figure 13.25). After adding "L", "B" and "D" in alphabetical order the arrays look like Figure 13.26. Deleting "B" links its element back into the front of the free list (Figure 13.27).

**Figure 13.25**An empty linked list and its free list implemented using arrays

**Figure 13.26**Linked list and free list after adding L, B and D

**Figure 13.27**Linked list and free list after a deletion

Book slip The text says Figure 13.27 deletes "B", but the figure keeps StartPointer at 1, changes B's pointer from 2 to 0 and puts index 2 at the front of the free list: that deletes D. Deleting B correctly gives StartPointer = 2, Pointer[1] = 3 and FreeListPtr = 1. Try both in the lab below.

A linked list can also be stored as an array of records (Section 13.02): each record is one node with a data field and a pointer field (Figure 13.28).

**Figure 13.28**A linked list stored as an array of records, before any nodes are used

🔬 Lab: ordered linked list with a free list

Insert and delete values. New nodes are taken from the front of the free list, the list stays in alphabetical order, and deleted nodes go back to the front of the free list, exactly as in Figures 13.25–13.27.

Index	Data	Pointer

Task 13.11 A linked list is set up using the values in the UserID array below. Without moving any of the contents of UserID, insert the pointer values so that the linked list is in alphabetical order.

**Task 13.11**UserID array for Task 13.11

✍️ Fill in the pointers

Index	UserID	Pointer

StartPointer

Alphabetical order: AS23 (3) → BR01 (0) → CK25 (2) → DT71 (4) → EB95 (5) → FL39 (1).

Index	UserID	Pointer
[0]	BR01	2
[1]	FL39	−1
[2]	CK25	4
[3]	AS23	0
[4]	DT71	5
[5]	EB95	1
[6]	(empty)	−1 or free list

StartPointer = 3. Index 6 is unused; if a free list is kept, FreeListPtr = 6.

Tip A stack can be built from a linked list: the start pointer acts as the top-of-stack pointer, and items are only ever added to and removed from the start of the list.

Tip A queue can be built from a linked list: the start pointer is the front of the queue. Items are always added at the end of the list and removed from the start.

Reflection point: What is the difference between standard data types, ADTs and user-defined data types?

Standard (built-in) data types such as INTEGER, REAL, CHAR, STRING, BOOLEAN and DATE are provided by the language; you just use them.
User-defined data types such as a record type are built by the programmer from existing types, to describe the shape of the data (which fields it has).
An ADT such as a stack, queue or linked list is defined by its behaviour: the data plus the operations allowed on it (push and pop, join and leave, insert and delete). How it is stored, whether in arrays, records or something else, is hidden from whoever uses it.

📌 Summary

The standard data types are INTEGER, REAL, CHAR, STRING, BOOLEAN and DATE.
A record structure holds data of different types under one identifier.
Dot notation addresses the fields of a record.
Arrays have dimensions with upper and lower bounds.
An array element is reached with one index (1D) or two (2D).
A bubble sort compares pairs of values in a linear list and swaps them if needed.
A linear search checks each value in turn for the one required.
Text files can be written and read, so data is kept between program runs.
Stacks, queues and linked lists are Abstract Data Types and can be implemented using arrays.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

Try it here first: choose a type for each, then check.

Variable	Example value	Data type

Model answer: ColourCode STRING (it contains letters); ProductionDate DATE; Weight REAL; NumberInStock INTEGER; SizeCode CHAR; Completed BOOLEAN. (Half a mark each, rounded down: 6 correct = 3 marks.)

**Question 2**Using a stack and a queue to reverse values

Each item leaves the first queue from the front and is pushed onto the stack; then each item is popped off the stack and joins the second queue.

Stack (top first)
E   ← top
D
C
B
A   ← Base of Stack

Second queue
E   ← Front of Queue
D
C
B
A

1 mark for the stack, 1 mark for the reversed queue.

**Question 3**Alicia’s UserList and PasswordList arrays

Identifier	Data type	Explanation
UserList	ARRAY[0:20] OF STRING	1D array to store user IDs
PasswordList	ARRAY[0:20] OF STRING	1D array to store passwords
MaxIndex	INTEGER	Upper bound of the array
MyUserID	STRING	User ID entered to log in
MyPassword	STRING	Password entered to log in
UserIdFound	BOOLEAN	FALSE if user ID not found in UserList; TRUE if user ID found in UserList
LoginOK	BOOLEAN	FALSE if user ID not found or password does not match; TRUE if user ID found and password matches
Index	INTEGER	Pointer to current array element

Book slip The question says "twenty users", but the arrays run from [0] to [20], which is 21 elements, and MaxIndex is 20. Either the lower bound should be 1, or there are 21 users. The answers here follow the diagram.

The completed blanks are marked with ◀.

MaxIndex ← 20
INPUT MyUserID
INPUT MyPassword
UserIdFound ← FALSE
LoginOK ← FALSE                                ◀
Index ← -1
REPEAT
   Index ← Index + 1                           ◀
   IF UserList[Index] = MyUserID               ◀ ◀
      THEN
         UserIdFound ← TRUE
   ENDIF
UNTIL UserIdFound = TRUE OR Index >= MaxIndex  ◀ ◀
IF UserIdFound = TRUE
   THEN
      IF PasswordList[Index] = MyPassword      ◀ ◀
         THEN
            LoginOK ← TRUE
      ENDIF                                    ◀
ENDIF
IF LoginOK = TRUE                              ◀
   THEN
      OUTPUT "Login successful"
   ELSE
      OUTPUT "User ID and/or password incorrect"
ENDIF

That is 10 blanks, 1 mark each. The book prints INDEX ← … in capitals; the identifier is Index.

// (i)
TYPE UserRecord
   DECLARE UserID : STRING
   DECLARE Password : STRING
ENDTYPE

// (ii)
DECLARE User : ARRAY[0:20] OF UserRecord

(i) 1 mark for TYPE … ENDTYPE, 1 mark for both fields with types. (ii) 1 mark for the bounds, 1 mark for OF UserRecord. The search would then compare User[Index].UserID and User[Index].Password.

Guru Jazzy · Cambridge AS & A Level Computer Science · Chapter 13 Data Types and Structures · Figures from the Cambridge coursebook (Langfield & Duddell)