Studyledge

Advanced Algorithms and Recursion: Question 3

Syllabus 19.1

Structured A2 8 marks

A school stores a linked list of exam candidates' names, kept in alphabetical order, using two parallel arrays and a start pointer:

DECLARE CandidateName : ARRAY[1:5] OF STRING
DECLARE NextPointer : ARRAY[1:5] OF INTEGER
DECLARE StartPointer : INTEGER

NextPointer[i] holds the array index of the next node in the list, or -1 if there is no next node. Array positions not currently part of the list are unused. The list currently holds this data:

Index CandidateName NextPointer
1 Halima 4
2 (unused) -
3 Amir 1
4 Zayn -1
5 (unused) -

StartPointer = 3.

(a) State the sequence of names produced by traversing this list from StartPointer, following each NextPointer value in turn. [2]

(b) The name "Dinesh" is inserted into the list at the unused array position 2, so that the list remains in alphabetical order. State the new value of NextPointer[2] and the new value of NextPointer[3] after this insertion, explaining how each value is determined. [3]

(c) The node holding "Halima" (at index 1) is now deleted from the list. State which NextPointer value must change to remove "Halima" from the list, its new value, and state the resulting sequence of names produced when the list, as it now stands after both (b) and (c), is traversed from StartPointer. [3]

Show worked solution Hide worked solution

Worked solution

Part (a): Traversing the initial list

A linked list is read by following pointers, not array indices. Starting at StartPointer = 3:

  • Index 3 holds “Amir”; NextPointer[3] = 1, so go to index 1.
  • Index 1 holds “Halima”; NextPointer[1] = 4, so go to index 4.
  • Index 4 holds “Zayn”; NextPointer[4] = -1, so the list ends here.

Sequence: Amir, Halima, Zayn. [2 marks]: [1] for correctly following pointers rather than array order, [1] for the correct three names in the correct order.

Part (b): Inserting “Dinesh” at index 2

To keep the list in alphabetical order, “Dinesh” must be linked in between the correct neighbours. Comparing “Dinesh” against the list found in part (a):

  • “Dinesh” comes after “Amir” (D is after A), so the search continues past Amir.
  • “Dinesh” comes before “Halima” (D is before H), so “Dinesh” belongs between Amir and Halima.

Two pointers must be updated, in the correct order, so the chain is never broken:

  1. NextPointer[2] ← NextPointer[3]. The new Dinesh node is given the pointer Amir used to have (to Halima, index 1). So NextPointer[2] = 1.
  2. NextPointer[3] ← 2. Only now is Amir’s pointer changed, to point at the new Dinesh node.

After this: NextPointer[3] = 2 and NextPointer[2] = 1. Traversing now gives Amir → Dinesh → Halima → Zayn.

[3 marks]: [1] for correctly identifying the insertion point (between Amir and Halima), [1] for the correct value of NextPointer[2] (= 1), [1] for the correct value of NextPointer[3] (= 2).

Part (c): Deleting “Halima” (index 1)

To delete a node, the pointer belonging to its predecessor (the node currently pointing to it) must be changed to skip over it. After part (b), the node pointing to index 1 (Halima) is Dinesh, at index 2 (NextPointer[2] = 1).

NextPointer[2] ← NextPointer[1]. Dinesh’s pointer is changed to whatever Halima’s pointer was (NextPointer[1] = 4, pointing to Zayn). So NextPointer[2] changes from 1 to 4.

Index 1 is no longer reachable from StartPointer, so “Halima” has effectively been removed without moving or shifting any other array element. Traversing the list now:

  • Index 3: “Amir”; NextPointer[3] = 2 → index 2.
  • Index 2: “Dinesh”; NextPointer[2] = 4 → index 4.
  • Index 4: “Zayn”; NextPointer[4] = -1 → end.

Sequence: Amir, Dinesh, Zayn.

[3 marks]: [1] for identifying that NextPointer[2] is the value that must change, [1] for the correct new value (4), [1] for the correct resulting traversal sequence.

Final answers

  • (a) Amir, Halima, Zayn
  • (b) NextPointer[2] = 1, NextPointer[3] = 2
  • (c) NextPointer[2] changes from 1 to 4; the list now reads Amir, Dinesh, Zayn