Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Linked lists: nodes, traversal and search

A linked list stores each item in a node. The node contains the item’s data and a link to the next node. A playlist can therefore change its logical order without moving every later item in memory. The links, rather than the physical array positions, define the order.

By the end, you will be able to

identify the head, data, next pointer and null marker;
reconstruct logical order from an array of nodes;
traverse and search safely;
explain the benefit of resizing at run time and the cost of following links.

Follow links, not rows

Start at head 3. Read Maya, move to next 0; read Noor, move to 4; read Sol, move to −1/null and stop. Scanning array indexes 0,1,2... would not produce list order.

The traversal rule

The variable current identifies the node to visit next. The rule that must remain true is that current is either a valid node or the null marker. While current is not null, process the current node’s data and then replace current with the node’s next pointer.

A search adds one decision. If the current data equals the target, report success. Otherwise, follow the next pointer. In an empty list, head is null, so the loop runs zero times.

Multiple choice1 mark

For the diagram, what is the logical list order?

AMaya, Noor, Sol
BNoor, Maya, Sol
CSol, Noor, Maya
DArray indexes 0,3,4

Trace table5 marks

Trace traversal of an array-of-nodes linked list.

Enter a value only when it changes. Follow pointers and output in execution order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython

data = ["Noor", "", "", "Maya", "Sol"]
nextIndex = [4, -1, -1, 0, -1]
current = 3
while current != -1:
print(data[current])
current = nextIndex[current]

Trace table with 5 columns
Row	data	nextIndex	current	current != -1	Output
1
2
3
4
5
6
7

Guided search

Create columns current, data[current], match? and next. Search for Sol. Stop immediately when found. Then repeat for Ari and reach null. This distinguishes successful termination from exhausted-list termination.

Written answer4 marks

Using the diagram, trace searches for Noor and Ari. Give visited node indexes and final outcome for each.

Start from head=3 and follow each next pointer in logical order.

Students type their answer here.

Independent transfer: write search

Return the node index containing target or -1 if absent. Inputs are data, next_index and head.

Coding task5 marks

def linked_search(data, next_index, head, target):
    current = head
    while current != -1:
        if ...:
            return current
        # Follow the link stored in the current node.
        current = ...
    return -1

Written answer3 marks

Compare linked-list access with array direct indexing for retrieving the 100th logical item.

Explain mechanism and consequence.

Students type their answer here.

Written answer4 marks

A music service does not know in advance how many tracks a user will add. Explain one benefit and one cost of using a dynamic linked list rather than a fixed-size array.

Refer to what happens while the program is running. Do not write only that one structure uses more memory.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks

A linked-list node stores data and a completion 1 to the next node. Traversal begins at the completion 2 pointer and follows links until the target or completion 3. Physical array order can differ from completion 4 order.

Review your work

Check that traversal begins at head, follows next pointers and stops at the null marker.