Revision NotesExam QuestionsPast Papers
A LevelComputer ScienceOCRRevision Notes8. Algorithms8.2 Algorithms for the Main Data StructuresLinked Lists

Linked Lists (OCR A Level Computer Science)

Revision Note

Robert Hampton

Written by: Robert Hampton

Reviewed by: James Woodhouse

Implementing a Linked List

How do you Program a Linked List?

  • To recap the main operations of Linked Lists and how they work, follow this link

  • 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:
    field fruit
    field next

# Create nodes
node1 = Node()
node2 = Node()
node3 = Node()

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

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

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
    }
}

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

# 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;

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

# Add "orange" to the end of the linked list
new_node = Node()
new_node.fruit = "orange"
new_node.next = None

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;

}

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

# 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;

    }

Last updated:

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

Sign up now. It’s free!

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

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:QueuesNext:Trees
    Author
    Reviewer
    Robert Hampton

    Author: Robert Hampton

    Expertise: Computer Science Content Creator

    Rob has over 16 years' experience teaching Computer Science and ICT at KS3 & GCSE levels. Rob has demonstrated strong leadership as Head of Department since 2012 and previously supported teacher development as a Specialist Leader of Education, empowering departments to excel in Computer Science. Beyond his tech expertise, Robert embraces the virtual world as an avid gamer, conquering digital battlefields when he's not coding.

    James Woodhouse

    Author: James Woodhouse

    Expertise: Computer Science

    James graduated from the University of Sunderland with a degree in ICT and Computing education. He has over 14 years of experience both teaching and leading in Computer Science, specialising in teaching GCSE and A-level. James has held various leadership roles, including Head of Computer Science and coordinator positions for Key Stage 3 and Key Stage 4. James has a keen interest in networking security and technologies aimed at preventing security breaches.