Community resourceWorksheet

OCR H446 1.4.2 Linked lists: traversal and search

Part 5 of 14 · H446 1.4.2 · Data structures

Logical order in a linked list follows the links, not the row order of the array that stores the nodes, and that distinction is where students most often go wrong in H446 1.4.2. Using a playlist held as an array of nodes, this worksheet establishes the traversal invariant and applies it to searching.

Students will:

  • identify head, data, next and the null value that ends a list
  • reconstruct the logical order of a list from an array of nodes
  • trace a search, separating a successful stop from reaching the end of the list
  • write a search that returns the index holding a target or reports its absence
  • compare following links with direct array indexing when retrieving a distant item

Inside: 7 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers, 1 Python task and 1 trace table. 17 marks, about 40 to 50 minutes.

Series: H446 1.4.2 · Data structures, part 5 of 14.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

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

Linked lists: nodes, traversal and search

A dynamically changing playlist stores each item with a pointer to the next. Logical order follows links, not physical memory order.

By the end, you will be able to

  • identify head, data, next and null;
  • reconstruct logical order from an array of nodes;
  • traverse and search safely;
  • explain dynamic benefits and access costs.

Reactivate: an index can identify an array slot.

Follow links, not rows

Array-of-nodes linked listhead = 3index 3Maya | next 0index 0Noor | next 4index 4Sol | next −1Traversal follows next pointers: physical array order is irrelevant. −1 represents null/end.

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.

Worked traversal invariant

current identifies the node to visit next. While current is not null: process nodes[current].data; then set current to nodes[current].next.

Search adds one decision: if data equals target, report success; otherwise advance. Empty list means head is null and the loop executes zero times.

Multiple choice1 mark

For the diagram, what is the logical list order?

  • ANoor, Maya, Sol
  • BSol, Noor, Maya
  • CArray indexes 0,3,4
  • DMaya, Noor, Sol
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
  1. data = ["Noor", "", "", "Maya", "Sol"]
  2. nextIndex = [4, -1, -1, 0, -1]
  3. current = 3
  4. while current != -1:
  5. print(data[current])
  6. current = nextIndex[current]
Trace table with 5 columns
RowdatanextIndexcurrentcurrent != -1Output
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):
    pass
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.

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 responses

Check every response against its command word and the supplied constraints. Strengthen unsupported answers with accurate method, mechanism, state or contextual consequence before submitting.