Linked Lists (Cambridge (CIE) A Level Computer Science): Revision Note

Exam code: 9618

Written by: Robert Hampton

Reviewed by: James Woodhouse

Updated on 3 June 2025

Linked lists

How do you program a linked list?

To recap the main operations of linked lists and how they work, read our ADT Overview page
To program a Linked List you must be able to perform the following operations:
- Create a linked list
- Traverse a linked list
- Add data to a linked list
- Remove data from a linked list

Create a linked list

Define the class called ‘Node’ that represents a node in the linked list.
Each node has 2 fields ‘fruit’ (this stores the fruit value) and ‘next’ (this stores a reference to the next node in the list)
We create 3 nodes and assign fruit values to each node
To establish a connection between the nodes we set the ‘next’ field of each node to the appropriate next node

Pseudocode
`CLASS Node DECLARE fruit : STRING DECLARE next : Node ENDCLASS // Create nodes DECLARE node1 : Node DECLARE node2 : Node DECLARE node3 : Node SET node1 = NEW Node SET node2 = NEW Node SET node3 = NEW Node // Assign fruit values SET node1.fruit = "apple" SET node2.fruit = "banana" SET node3.fruit = "orange" // Connect nodes SET node1.next = node2 SET node2.next = node3 SET node3.next = NULL`

Pseudocode

CLASS Node
    DECLARE fruit : STRING
    DECLARE next : Node
ENDCLASS

// Create nodes
DECLARE node1 : Node
DECLARE node2 : Node
DECLARE node3 : Node

SET node1 = NEW Node
SET node2 = NEW Node
SET node3 = NEW Node

// Assign fruit values
SET node1.fruit = "apple"
SET node2.fruit = "banana"
SET node3.fruit = "orange"

// Connect nodes
SET node1.next = node2
SET node2.next = node3
SET node3.next = NULL

Python
`class Node: def __init__(self, fruit): self.fruit = fruit self.next = None # Create nodes node1 = Node("apple") node2 = Node("banana") node3 = Node("orange") # Connect nodes node1.next = node2 node2.next = node3`

Python

class Node:
  def __init__(self, fruit):
    self.fruit = fruit
    self.next = None

# Create nodes
node1 = Node("apple")
node2 = Node("banana")
node3 = Node("orange")

# Connect nodes
node1.next = node2
node2.next = node3

Java
`class Node { String fruit; Node next; Node(String fruit) { this.fruit = fruit; this.next = null; } } public class LinkedListExample { public static void main(String[] args) { // Create nodes Node node1 = new Node("apple"); Node node2 = new Node("banana"); Node node3 = new Node("orange"); // Connect nodes node1.next = node2; node2.next = node3 } }`

Java

class Node {
    String fruit;
    Node next;

    Node(String fruit) {
        this.fruit = fruit;
        this.next = null;
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        // Create nodes
        Node node1 = new Node("apple");
        Node node2 = new Node("banana");
        Node node3 = new Node("orange");

        // Connect nodes
        node1.next = node2;
        node2.next = node3
    }
}

Algorithm to traverse a linked list

We traverse the linked list starting from ‘node1’. We output the fruit value of each node and update the ‘current’ reference to the next node until we reach the end of the list

Pseudocode
`// Start at the head of the list DECLARE current : Node SET current = node1 WHILE current != NULL OUTPUT current.fruit SET current = current.next ENDWHILE`

Python
`# Traverse the linked list` `current = node1` `while current is not None:` `print(current.fruit)` `current = current.next`

Python

# Traverse the linked list

current = node1

while current is not None:

print(current.fruit)

current = current.next

Java
`// Traverse the linked list` `current = node1;` `while (current != null) {` `System.out.println(current.fruit);` `current = current.next;`

Java

// Traverse the linked list

current = node1;

while (current != null) {

System.out.println(current.fruit);

current = current.next;

Algorithm to add data to a linked list

We create a new node with the new data and check if the list is empty
If it isn’t, we find the last node and add the new node to the end

Pseudocode
`// Create a new node DECLARE newNode : Node SET newNode = NEW Node SET newNode.fruit = "orange" SET newNode.next = NULL // If the list is empty IF node1 = NULL THEN SET node1 = newNode ELSE // Traverse to the end of the list DECLARE current : Node SET current = node1 WHILE current.next != NULL SET current = current.next ENDWHILE // Append the new node SET current.next = newNode ENDIF`

Pseudocode

// Create a new node
DECLARE newNode : Node
SET newNode = NEW Node
SET newNode.fruit = "orange"
SET newNode.next = NULL

// If the list is empty
IF node1 = NULL THEN
    SET node1 = newNode
ELSE
    // Traverse to the end of the list
    DECLARE current : Node
    SET current = node1

    WHILE current.next != NULL
        SET current = current.next
    ENDWHILE

    // Append the new node
    SET current.next = newNode
ENDIF

Python
`# Add "orange" to the end of the linked list` `new_node = Node("orange")` `if node1 is None:` `# If the list was empty, make "orange" the head` `node1 = new_node` `else:` `# Find the last node and append "orange" to it` `current = node1` `while current.next is not None:` `current = current.next` `current.next = new_node`

Python

# Add "orange" to the end of the linked list
new_node = Node("orange")

if node1 is None:
# If the list was empty, make "orange" the head
node1 = new_node
else:
# Find the last node and append "orange" to it
current = node1
while current.next is not None:
current = current.next
current.next = new_node

Java
`// Add "orange" to the end of the linked list` `Node new_node = new Node("orange");` `if (node1 == null) {` `// If the list was empty, make "orange" the head` `node1 = new_node;` `} else {` `// Find the last node and append "orange" to it` `current = node1;` `while (current.next != null) {` `current = current.next;` `}` `current.next = new_node;` `}`

Java

// Add "orange" to the end of the linked list
Node new_node = new Node("orange");

if (node1 == null) {
// If the list was empty, make "orange" the head
node1 = new_node;
} else {
// Find the last node and append "orange" to it
current = node1;
while (current.next != null) {
current = current.next;
}
current.next = new_node;

}

Algorithm to remove data from a linked list

We traverse the list until we find the data to be removed
If the data to be removed is the first node, we update the head, else we update the node before to bypass the data to be removed

Pseudocode
`// Start traversal from the head DECLARE current : Node DECLARE previous : Node SET current = node1 SET previous = NULL WHILE current != NULL IF current.fruit = "apple" THEN IF previous = NULL THEN // "apple" is at the head of the list SET node1 = current.next ELSE // Bypass the current node SET previous.next = current.next ENDIF BREAK ENDIF SET previous = current SET current = current.next ENDWHILE`

Pseudocode

// Start traversal from the head
DECLARE current : Node
DECLARE previous : Node

SET current = node1
SET previous = NULL

WHILE current != NULL
    IF current.fruit = "apple" THEN
        IF previous = NULL THEN
            // "apple" is at the head of the list
            SET node1 = current.next
        ELSE
            // Bypass the current node
            SET previous.next = current.next
        ENDIF
        BREAK
    ENDIF

    SET previous = current
    SET current = current.next
ENDWHILE

Python
`# Find and remove "apple"` `while current is not None:` `if current.fruit == "apple":` `if previous is None:` `# If "apple" is the first node, update the head` `node1 = current.next` `else:` `# Remove the node by updating the previous node's next pointer` `previous.next = current.next` `break` `previous = current` `current = current.next`

Python

# Find and remove "apple"

while current is not None:

if current.fruit == "apple":

if previous is None:

# If "apple" is the first node, update the head

node1 = current.next

else:

# Remove the node by updating the previous node's next pointer

previous.next = current.next

break

previous = current

current = current.next

Java
`// Find and remove "apple"` `while (current != null) {` `if (current.fruit.equals("apple")) {` `if (previous == null) {` `// If "apple" is the first node, update the head` `node1 = current.next;` `} else {` `// Remove the node by updating the previous node's next pointer` `previous.next = current.next;` `}` `break;` `}` `previous = current;` `current = current.next;` `}`

Java

// Find and remove "apple"

while (current != null) {

if (current.fruit.equals("apple")) {

if (previous == null) {

// If "apple" is the first node, update the head

node1 = current.next;

} else {

// Remove the node by updating the previous node's next pointer

previous.next = current.next;

}

break;

}

previous = current;

current = current.next;

}

Worked Example

The following diagram represents an Abstract Data Type (ADT) for a linked list.

The free list is as follows:

Explain how a node containing data value B is added to the list in alphabetic sequence.[4]

Answer

One mark per point

Check for a free node [1 mark]
Search for correct insertion point [1 mark]
Assign data value B to first node in free list / node pointed to by start pointer of free list [1 mark]
Pointer from A will be changed to point to node containing B (instead of C) [1 mark]
Pointer from B will be changed to point to node containing C [1 mark]
Start pointer in free list moved to point to next free node [1 mark]

You've read 0 of your 5 free revision notes this week

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

Previous:QueuesNext:Binary Trees

Linked Lists (Cambridge (CIE) A Level Computer Science): Revision Note

Linked lists

How do you program a linked list?

Create a linked list

Algorithm to traverse a linked list

Algorithm to add data to a linked list

Algorithm to remove data from a linked list

You've read 0 of your 5 free revision notes this week

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

1. Information representation

Data Representation

Binary Prefixes

Number Systems

Binary Arithmetic

Uses of Number Systems

Character Encoding

Multimedia

Bitmap Images

Vector Graphics

Sound Representation

Compression

Compression

Compression Techniques

2. Communication

Networks & the Internet

Network Types

Network Models

Network Topologies

Cloud Computing

Transmission Media

Network Hardware

Ethernet

Bit Streaming

The Internet

IP Addressing

Locating Resources on the World Wide Web

3. Hardware

Computers & Components

System Components

Embedded Systems

Hardware Devices

Memory Types

Monitoring & Control

Logic Gates & Logic Circuits

Logic Gates

Logic Construction

4. Processor Fundamentals

Central Processing Unit (CPU) Architecture

System Architecture

Components of the CPU

System Performance

Ports & Interfaces

Fetch-Execute Cycle

Interrupts

Assembly Language

Assembly Language Basics

Assembly Process

Instruction Groups

Addressing Modes

Bit Manipulation

Bitwise Operations

5. System Software

Operating Systems

Operating System Fundamentals

Utility Software

Program Libraries

Language Translators

Translator Types

Development Tools

6. Security, privacy & data integrity

Data Security

Security Measures

Threats

Data Protection

Data Integrity

Integrity Methods

7. Ethics & Ownership

Ethics & Ownership

Professional Ethics