Community resourceWorksheet

OCR H446 1.4.2 Linked lists: add and remove

Part 6 of 14 · H446 1.4.2 · Data structures

Changing a linked list means rewiring pointers in a safe order, and the wrong order silently orphans the rest of the data. This H446 1.4.2 worksheet takes students from insertion at the head and after a node through to removal of head, middle and final nodes, checking reachability after every change.

Students will:

  • insert a node at the head and after a given node in an order that preserves the remainder
  • remove head, middle and final nodes without leaving data unreachable
  • state what actually changes on insertion, and what does not need to move
  • implement head removal and insertion after a node using nodes held as objects
  • compare an array-of-nodes implementation with an object-node one and name a shared invariant

Inside: 9 explanation cells, 2 multiple-choice questions, 2 fill-in-the-blanks cells, 2 written answers and 2 Python tasks. 28 marks, about 50 to 60 minutes.

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

Shared by Coding PathwayVerified teacher

  • 17 cells
  • About 60 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 1 Oct 2026

Preview

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

Linked lists: add and remove

Adding or removing a node changes links. It does not shift a block of neighbouring array values. The order of the updates matters because one incorrect assignment can make the rest of the list unreachable.

By the end, you will be able to

  • insert at the head and after an existing node;
  • remove the head, a middle node and the final node;
  • order pointer updates without orphaning data;
  • work with both array-based and object-based linked lists.

Safe insertion order

Safe linked-list insertion orderAnew BC1. B.next = C2. A.next = BConnect the new node onward before redirecting the previous node; otherwise C may be orphaned.

To insert B between A and C, first save/connect B.next to C, then redirect A.next to B. Reversing the first update without saving C can make the remaining list unreachable.

Worked removal

List A → B → C. To remove B: keep previous=A and current=B; set previous.next = current.next, so A now points to C. For head removal, set head = head.next. For final removal, previous.next becomes null.

After every operation, check: head reaches every logical node exactly once and traversal ends at null.

Multiple choice1 mark

When inserting newNode after current, which update should preserve the old remainder first?

  • Acurrent.next = newNode
  • BnewNode.next = current.next
  • Chead = null
  • Ddelete current.next
Multiple choice1 mark

What normally changes when a node is inserted into an array-of-nodes linked list?

  • AEvery later value shifts one array position
  • BThe physical array must be sorted
  • CLink fields and possibly the head pointer, not every later stored value
  • DAll next fields become null

Guided pointer table

Draw before/after next fields for insert X at head, insert Y after the second node, remove head and remove the final node. Circle the link that preserves the remaining list.

Written answer6 marks

For A → C → D, insert B after A and then remove C. State each pointer update in a safe order and give the final list.

Use names such as B.next and A.next.

Students type their answer here.

Array implementation and the free list

An array-based linked list needs to know which unused node can be allocated next. A free pointer identifies the first available array node. The unused nodes can themselves form a linked free list. To insert at the front, take the node at free, advance free to the next unused node, store the new data, point the new node to the old head, and then update head.

Fill in the blanks5 marks
The current list is head = 0 with node 0 = (M, next 1) and node 1 = (N, next −1). The free list begins at free = 2, where node 2 points to unused node 3. Insert X at the front.
State itemValue after insertion
index allocated to Xentry 1
updated free pointerentry 2
X.nextentry 3
updated headentry 4
logical listentry 5

Supported implementation: object nodes

Implement remove_head(head). A Node has data and next attributes. Return (removed_value, new_head); return (None, None) for empty.

Coding task3 marks
def remove_head(head):
    if head is None:
        return None, None

    removed_value = ...
    new_head = ...
    return removed_value, new_head

Independent transfer: insert after a node

Implement insert_after(current, new_node). Both are Node objects with a next attribute. Preserve the old successor, link new_node to it, then link current to new_node. Return new_node.

Coding task4 marks
def insert_after(current, new_node):
    old_successor = current.next
    # Connect the new node onwards before redirecting current.
    new_node.next = ...
    current.next = ...
    return new_node
Written answer4 marks

Compare an array-of-nodes implementation with an object-node implementation. State one representation difference and one invariant shared by both.

Focus on indexes/references and logical links.

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
For safe middle insertion, point the new node to the old completion 1 before redirecting the previous node. Otherwise the remainder may become completion 2. Removing the head changes the completion 3 pointer; removing a middle node makes its predecessor bypass it to its completion 4.

Review your work

Redraw each pointer update and confirm that every intended node remains reachable from head.