Computational Thinking and Data Structures: Question 9

Worked solution

Part (a): Following StartPointer and NextPointer to find the logical order

The physical order of names stored in the array (StudentName[1], StudentName[2], StudentName[3] = “Chen”, “Zara”, “Amy”) is not the logical order of the linked list. The logical order is found by starting at StartPointer and repeatedly following NextPointer:

1. StartPointer = 3, so the first student is StudentName[3] = "Amy".
2. NextPointer[3] = 1, so the next student is StudentName[1] = "Chen".
3. NextPointer[1] = 2, so the next student is StudentName[2] = "Zara".
4. NextPointer[2] = 0, which signals end of list. There is no next student.

So the logical order is Amy, Chen, Zara. Correctly in alphabetical order, even though the data is not stored in that order in the array.

[3 marks]: [1] for the correct final order (Amy, Chen, Zara), [1] for correctly starting the traversal at StudentName[StartPointer], [1] for correctly following each NextPointer value in turn and correctly stopping at the NextPointer value 0.

Part (b): Inserting “Ben” without moving existing data

“Ben” belongs alphabetically between “Amy” and “Chen” (Amy < Ben < Chen < Zara). Since indices 1, 2 and 3 already hold data that must not be moved, “Ben” is stored in the next unused array position, index 4:

StudentName[4] ← "Ben"

To splice “Ben” into the list between Amy and Chen, only the pointers need to change. Amy must now point to Ben instead of directly to Chen, and Ben must point on to Chen:

• NextPointer[4] ← 1 (Ben’s next is Chen, at index 1)
• NextPointer[3] ← 4 (Amy’s next is updated from 1 to 4, i.e. Ben)
• StartPointer is unchanged, remaining 3, because “Amy” is still the first student alphabetically.

Verifying the new order: StartPointer = 3 → “Amy”; NextPointer[3] = 4 → “Ben”; NextPointer[4] = 1 → “Chen”; NextPointer[1] = 2 → “Zara”; NextPointer[2] = 0 → end. This gives Amy, Ben, Chen, Zara, which is correctly in alphabetical order.

[4 marks]: [1] for storing “Ben” at index 4, [1] for NextPointer[4] = 1 (Ben → Chen), [1] for updating NextPointer[3] = 4 (Amy → Ben), [1] for correctly stating StartPointer does not change and remains 3.

Part (c): Advantage over a plain sorted array

Inserting “Ben” into this array-based linked list required no existing data to be moved at all. Only one previously unused array slot was written to, and two NextPointer values were updated. If the names were instead stored in a single 1D array kept continuously in alphabetical order, inserting “Ben” between “Amy” and “Chen” would require shifting “Chen”, “Zara” (and any names after them) one position to the right first, to open up a gap at the correct index, which becomes increasingly costly as the list grows longer or as more insertions are made in the middle of it.

[2 marks]: [1] for identifying that no shifting of existing elements is required, [1] for contrasting this with a plain sorted array, where later elements would need to be shifted to make room for the new value.

Final answers

• (a) Amy, Chen, Zara. Found by starting at StudentName[StartPointer] and following NextPointer until a value of 0 is reached.
• (b) StudentName[4] = "Ben", NextPointer[4] = 1, NextPointer[3] = 4, StartPointer unchanged at 3. New logical order: Amy, Ben, Chen, Zara.
• (c) No existing array elements need to be shifted. Only one free slot and a couple of NextPointer values are updated, unlike a plain sorted array which would need later elements shifted along to make room.