A-LevelComputer ScienceData types and structures9618/21 · Oct/Nov 2022 · Q412 Marks

The following diagram shows an Abstract Data Type (ADT) representation of an ordered linked list. The data item stored in each node is a single character. The data will be accessed in alphabetical order. The symbol Ø represents a null pointer. [Figure 4.a.i]

(a)(i)Nodes with data 'A' and 'K' are added to the linked list. Nodes with data 'J' and 'L' are deleted. After the changes, the data items still need to be accessed in alphabetical order. Complete the diagram to show the new state of the linked list. Start pointer 'C' 'J' 'L'[4]
(a)(ii)The original data could have been stored in a 1D array in which each element stores a character. For example: 'C' 'J' 'L' Explain the advantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array.[2]
(a)(iii)Explain the disadvantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array.[2]
(b)A program will store data using a linked list like the one shown in part (a). Explain how the linked list can be implemented.[4]

This question uses a diagram from the original paper, which isn't shown here. Open the full paper from the past papers archive to see it.

Mark scheme

Marking points from the official mark scheme (Oct/Nov 2022). The mark or mark type is shown in brackets.

[1] (a)(i) Data A and K stored in new / existing nodes
[1] (a)(i) Start pointer points to Node A
[1] (a)(i) Node A points to Node C and Node C points to Node K
[1] (a)(i) Node K contains Null Pointer
[1] (a)(ii) Pointers determine the ordering of data // only the pointers need to be changed when data changed
[1] (a)(ii) Easier to add / delete data (to maintain correct sequence) in a linked list // description of moving data to maintain correct sequence when array used
[1] (a)(iii) Need to store pointers as well as data
[1] (a)(iii) More complex (to setup / implement)
[1] (b) Declare two (1D) arrays
[1] (b) One for data, one for pointers
[1] (b) Elements from same index represent one node
[1] (b) Declare an integer / variable for StartPointer // explain its use
[1] (b) Define appropriate value for null pointer // explain its use
[1] (b) Declare an integer / variable for FreeList pointer // explain its use
[1] (b) Routines are needed to add / delete / search
[1] (b) Define a record type with fields for data and pointer
[1] (b) Declare one (1D) array
[1] (b) ...of the defined record type

On Oracle Prep you can write or photograph your own answer and have it marked by AI against this mark scheme, with feedback on what you missed.