CAIE 9618 · Paper 4 · Topic 4.3.2

Linked
Lists

Nodes · Data & Pointer Fields · Head Pointer · Insert · Delete · Traverse · vs Array

CSZone Cambridge International AS & A Level Computer Science 9618

Structure of a Linked List

Nodes Connected by Pointers

A linked list is a dynamic data structure where each element (node) contains a data field and a pointer to the next node. Nodes can be scattered in memory — no contiguous allocation required.

Head →

Alice

→ 2

→

Bob

→ 3

→

Carol

→ 4

→

David

NIL

→

NIL

Each node: Data field | Pointer field (address of next node). Last node points to NIL.

CAIE PSEUDOCODE NODE TYPE

TYPE Node
DECLARE Data : STRING
DECLARE NextNode : ^Node
ENDTYPE

TYPE NodePtr = ^Node
DECLARE Head : NodePtr
Head ← NIL // empty list

KEY TERMS

Head — pointer to the first node; NIL if list is empty

NIL — null/null pointer; end-of-list marker

Pointer — stores the memory address of the next node

Operations — Insert & Delete

Changing the Pointer Chain

INSERT AT HEAD — O(1)

Create new node with NEW()

Set NewNode^.NextNode ← Head (new node points to current first)

Set Head ← NewNode (update head to new node)

No shifting required — just pointer updates

DELETE A NODE

Find the node BEFORE the target (traverse from Head)

Set Previous^.NextNode ← Target^.NextNode (bypass the target)

Call DISPOSE(Target) to free memory

Special case: deleting head → Head ← Head^.NextNode

LINKED LIST vs ARRAY

	Linked List	Array
Size	Dynamic	Fixed
Insert/Delete	O(1) at head	O(n) — shift
Random access	O(n) — traverse	O(1) — index
Memory	Extra pointer field	Compact
Cache	Poor (scattered)	Good (contiguous)

Exam Practice

Cambridge-style questions

Question 1

Describe the steps required to insert a new node containing the value 42 at the beginning of a linked list. State what happens to the Head pointer. [3]

1

Create a new node (using NEW()) and set its data field to 42.

1

Set the NextNode pointer of the new node to point to the node that Head currently points to (so the new node links to the old first node).

1

Update Head to point to the new node. Head now points to the node containing 42, which becomes the new first node in the list.

Common Mistakes

Don't lose easy marks

1

Updating Head BEFORE setting the new node's pointer — if you do Head ← NewNode first, you lose the reference to the old list. Always set NewNode^.NextNode ← Head FIRST, then Head ← NewNode.

2

Saying linked lists allow O(1) access to any element — they DON'T. To access the nth element you must traverse from Head through n nodes, which is O(n). Only the head node is O(1) access. Random access is an advantage of arrays, not linked lists.

3

Forgetting to handle the special case of an empty list — if Head = NIL, inserting or traversing requires a null check first. In delete operations, also check for deleting the head node (which requires updating Head directly, not a previous node's pointer).

Topic Summary — 4.3.2

What You Need to Know

STRUCTURE

Nodes (data + pointer to next). Head pointer. NIL marks end. TYPE Node with DECLARE Data and DECLARE NextNode:^Node in CAIE pseudocode.

INSERT AT HEAD — O(1)

NEW(node) → node^.NextNode ← Head → Head ← node. Order matters — set next pointer FIRST.

vs ARRAY

Linked list: dynamic size, O(1) insert/delete at head, O(n) random access. Array: fixed size, O(1) random access, O(n) insert/delete. Choose based on operation frequency.

CSZone

Next Video

4.3.3

Trees & Hash Tables

Binary Trees · BST · Hash Functions · Collisions

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools