Computer Science (AS & A Level) · Oct / Nov 2024 · Paper 41 · Question 3

A linked list stores positive integer data in a 2D array. The first dimension of the array stores the integer data. The second dimension of the array stores the pointer to the next node in the linked list. A linked list node with no data is initialised with the integer –1. These nodes are linked together as an empty list. A pointer of –1 identifies that node as the last node. The linked list can store 20 nodes. The global 2D array LinkedList stores the linked list. LinkedList is initialised as an empty list. The data in each node is initialised to –1. Each node’s pointer stores the index of the next node. The last node stores the pointer value –1, which indicates it is the last node. The global variable FirstEmpty stores the index of the first element in the empty list. This is the first node in the empty linked list when it is initialised, which is index 0. The global variable FirstNode stores the index of the first element in the linked list. There is no data in the linked list when it is initialised, so FirstNode is initialised to –1. This diagram shows the content of the initialised array. FirstEmpty = 0 FirstNode = –1 Index Data Pointer 0 -1 1 1 -1 2 2 -1 3 3 -1 4 4 -1 5 19 -1 -1

Read automatically from the paper; the printed page above is exact.