A-Level Computer Science / Unit 10: Organising Data in Programs

10.4.4 Linked Lists: Nodes, Pointers and Updates

🔒 Lesson slides are available to signed-in users. Sign in

10.4.4 Linked Lists: Nodes, Pointers and Updates

A linked list stores a sequence of nodes. Each node contains data and a link to the next node. The nodes do not need to occupy neighbouring storage locations because the links, rather than physical position, determine the list order.

This page focuses on the behaviour of a singly linked list: following links, inserting nodes, editing stored values and removing nodes. Detailed parallel-array layouts, free-list management and comparisons with stack and queue implementations are reserved for 10.4.5 Implementing ADTs with Arrays.

By the end of this section, you should be able to:

  • Describe a linked list as a sequence of connected nodes.
  • Use the terms node, pointer, start pointer and null pointer accurately.
  • Trace the logical order of a list by following pointers.
  • Explain pointer changes for insertion at the start, middle and end.
  • Explain pointer changes for deletion at the start, middle and end.
  • Distinguish editing node data from changing the links between nodes.
  • Justify the use of a linked list for a given situation.
  • State the main benefits and limitations of linked lists.
Syllabus scope: students should be able to add, edit and delete data in a linked list and describe an array-based implementation. Complete implementation pseudocode is not required.

The Linked List Model

A fixed array normally gives each item a position such as index 0, 1, 2 and 3. In a linked list, the next item is found by reading a pointer stored in the current node. This allows the logical sequence to differ from the physical storage order.

Start
→
Amber next
→
Cedar next
→
Echo next
→
NULL
The example is a singly linked list: each node stores one pointer to the next node.
Common misconception: the arrows are a diagrammatic way to show links. A program stores pointer values such as addresses, references or array indexes.

Key Terms

Term Meaning Role in a list
Node One linked-list element containing data and a pointer field. Stores one item and identifies what comes next.
Pointer A stored value that identifies another node's location. Connects the current node to its successor.
Start pointer A variable identifying the first node. Provides the entry point for traversal.
Null pointer A special value meaning “no next node”. Marks the end of the list; array examples often use -1.
Traversal Visiting nodes by repeatedly following their pointers. Used to find, display or update an item.
An empty data field and a null pointer are different. An empty field concerns the data; a null pointer concerns the absence of another node.

Inserting Nodes

Insert at the start

The new node must point to the old first node. The start pointer is then changed to identify the new node.

Before: Start → Amber → Cedar → Echo
After: Start → Aster → Amber → Cedar → Echo

Insert between two nodes

Suppose Dune must be inserted between Cedar and Echo. Dune first receives Cedar's old pointer, then Cedar is changed to point to Dune.

Before: Cedar → Echo
Update 1: Dune → Echo
Update 2: Cedar → Dune

Insert at the end

The old final node is changed to point to the new node. The new node receives a null pointer because it is now last.

Before: Kite → Quartz → NULL
After: Kite → Quartz → Willow → NULL
Common mistake: when inserting in the middle, store the old link in the new node before replacing the predecessor's pointer. Otherwise, the remainder of the list may become unreachable.

Deleting Nodes

Deletion removes a node from the active chain. The old data may still remain physically stored until the location is reused.

Position removed Pointer update Example
First node Copy the first node's next pointer into the start pointer. Start moves from Amber to Cedar.
Middle node Make the predecessor point to the deleted node's successor. Cedar changes from pointing to Echo to pointing to Kite.
Final node Set the predecessor's pointer to null. Kite becomes the final node after Quartz is removed.
Deleting a node does not mean that the previous node should point to null in every case. For a middle deletion, it must point to the node that follows the deleted node.
In a written explanation, name the three roles clearly: predecessor, target and successor.

Editing Data Without Changing the Links

To edit a stored value, traverse from the start pointer until the required node is found, then change its data field. The pointer can remain unchanged when the node's position in the sequence is still correct.

Before: Echo → Kite → Quartz
Edit: change Kite to Lantern
After: Echo → Lantern → Quartz
In an ordered linked list, changing a key value may make the node incorrectly positioned. The node may need to be removed and reinserted in the correct location.

Maintaining an Ordered Linked List

A linked list may be kept in key order, such as alphabetical order or ascending priority. The physical storage locations still do not need to be ordered.

To insert a new key, traverse the list until the correct predecessor and successor are found. Then change the two links needed to place the new node between them.

Physical storage might be: [Echo, Willow, Amber, Dune, Quartz, Kite, Cedar]
while the linked order is: Amber → Cedar → Dune → Echo → Kite → Quartz → Willow.
“Ordered linked list” describes the order produced by following pointers, not the order of memory addresses or array indexes.

When Is a Linked List Suitable?

Requirement How a linked list responds
Items are inserted or deleted frequently. Links can be changed without shifting every later item.
The number of items changes over time. Nodes can be added or released as needed, depending on implementation.
Items are normally processed sequentially. Traversal naturally follows one node to the next.
Direct access to item number 500 is required. A linked list is less suitable because earlier nodes must be traversed first.
Memory use must be minimal. Pointer fields add storage overhead.
Strong justification: “A linked list is suitable because items are inserted and removed frequently; changing links avoids shifting all later records.”
Do not claim that linked-list insertion is always instant. The program may first need to traverse the list to find the insertion position.

Implementation Preview

A linked list can be represented using parallel arrays or an array of node records. One field stores data and another stores the index of the next node. A separate start pointer identifies the first active node.

Implementation component Purpose
Data field or data array Stores the node's value or record.
Next field or pointer array Stores the index of the successor.
Start pointer Stores the index of the first active node.
Unused-node management Tracks storage positions available for later insertion.
Detailed free-list tracing, parallel arrays and arrays of records are developed in 10.4.5 Implementing ADTs with Arrays.

Interactive: Linked List Update Lab

Select a scenario and step through the pointer changes. The left-hand table shows physical storage; the right-hand chain shows the logical list produced by following the start pointer.

Physical representation

Node storage

Original list
Index Data Next Status
Logical representation

Follow the links

StartPointer: 2 Unused slots: 1, 3

Begin at the start pointer

StartPointer contains 2, so index 2 is the first active node.

Step 1 of 6: StartPointer identifies index 2.

Common Mistakes and Misconceptions

  • Reading nodes in array-index order instead of following the start pointer.
  • Confusing the node's data with its pointer.
  • Treating null as an empty string or zero data value.
  • Forgetting to preserve the old next pointer during a middle insertion.
  • Setting the predecessor to null when deleting a middle node.
  • Assuming deleted data must be erased immediately.
  • Claiming linked lists provide fast direct access by position.
  • Ignoring the extra storage required for pointer fields.
  • Including detailed free-list mechanics when the question only asks about conceptual updates.

Practice

Task 1: Trace a list

StartPointer = 4. Node 4 points to 1, node 1 points to 6, node 6 points to 2 and node 2 points to -1.

  1. Write the index traversal.
  2. State which node is first and which is last.

Task 2: Insert at the start

The current start pointer is 5. A new node is stored at index 3. State the two pointer updates required to make index 3 the new first node.

Task 3: Insert in the middle

Node P currently points to node R. Explain how node Q can be inserted between them without losing the link to R.

Task 4: Delete a node

The chain is M → N → P → S → NULL.

  1. Describe the pointer change needed to remove P.
  2. Describe the pointer change needed to remove M.
  3. Describe the pointer change needed to remove S.

Task 5: Choose and justify

Decide whether a linked list is suitable for each situation.

  1. A playlist where tracks are frequently inserted and removed.
  2. A fixed table requiring immediate access to row 900.
  3. A changing sequence of large records processed from start to end.
  4. A tiny fixed set of values that never changes order.

Review

Question Strong answer should include
What is a node? An element containing data and a pointer to the next node.
What does the start pointer do? Identifies the first node and provides the entry point for traversal.
What marks the end of the list? A null pointer in the final node.
How is a middle node inserted? The new node receives the predecessor's old pointer, then the predecessor points to the new node.
How is a middle node deleted? The predecessor is changed to point to the target's successor.
What is a main benefit? Insertion and deletion can avoid shifting many stored values.
What are two limitations? Sequential traversal is needed and pointer fields consume extra storage.
Final exam tip: draw or write the chain before and after an update. Name exactly which pointer changes and what it points to afterwards.