Preview

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

Linked-list algorithms

A linked-list algorithm follows links, not physical array order. Safe updates preserve reachability.

By the end, you will be able to

traverse/search by next pointers;
add/remove at head, middle and end;
order pointer updates safely;
handle empty and missing-target cases.

Reactivate: -1 represents null in this array-of-nodes model.

Worked insertion and removal

Given previous.next = successor, insert new by first setting new.next = successor, then previous.next = new. If you overwrite previous.next first without saving successor, the remainder can become unreachable.

Remove current after previous by setting previous.next = current.next. Removing head instead sets head = head.next. Empty and not-found cases change nothing.

Multiple choice1 mark

Which insertion order preserves the old successor?

Aprevious.next = new; then read previous.next
Bnew.next = previous.next; then previous.next = new
CDelete successor; then link new
DMove every node in memory

Trace table5 marks

Trace logical traversal; indexes are deliberately out of physical order.

Enter a value only when it changes. Record output in 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

value = ["N","","S","M"]
next_index = [2,-1,-1,0]
current = 3
while current != -1:
print(value[current])
current = next_index[current]

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

Written answer6 marks

head=3; node 3 is M→0, node 0 is N→2, node 2 is S→-1. Insert X between N and S, then remove M. Give safe pointer assignments and final logical order.

State changes before final order.

Students type their answer here.

Independent transfer: search a linked list

values and next_index are parallel arrays. Return the node index containing target or -1.

Coding task6 marks

def linked_search(values, next_index, head, target):
    pass

Written answer4 marks

Explain why access to the kth logical item is generally O(k) in a singly linked list, while insertion after a known node can be O(1).

Distinguish locating from updating.

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

Traversal begins from the completion 1 pointer and follows each node's completion 2 link. Before redirecting a predecessor, a new node must preserve the old completion 3. Safe update order preserves completion 4 of the remaining list.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.