6 The following diagram represents an Abstract Data Type (ADT) for a linked list. [Figure showing linked list: Box -> A -> Box -> C -> Box -> D -> Box -> E -> Box -> Ø] The free list is as follows: [Figure showing free list: Box -> Box -> Box -> Ø] (a) Explain how a node containing data value B is added to the list in alphabetic sequence. (b) Describe how the linked list in part (a) may be implemented using variables and arrays.

Mark scheme

Marking points from the official mark scheme (May/June 2021). The mark or mark type is shown in brackets.

1. [1] (a) Check for a free node
2. [1] (a) Search for correct insertion point
3. [1] (a) Assign data value B to first node in free list / node pointed to by start pointer of free list
4. [1] (a) Pointer from A will be changed to point to node containing B (instead of C)
5. [1] (a) Pointer from B will be changed to point to node containing C
6. [1] (a) Start pointer in free list moved to point to next free node
7. [1] (b) An array (1D) to store the data and a second array (1D) to store the pointers
8. [1] (b) An (integer) variable to hold the start pointer and an (integer) variable to store the next free pointer
9. [2] (b) ALTERNATIVE: Define a record type comprising a data element and a pointer and declare an array (1D) of this type; An integer variable to hold the start pointer and an integer variable to store the next free pointer