The following diagram represents an Abstract Data Type (ADT) for a linked list. [Diagram: A --> C --> D --> E --> Ø]. The free list is as follows: [Diagram: (empty box) --> (empty box) --> (empty box) --> Ø]

Mark scheme

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

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