Linked Lists (OCR A Level Computer Science)

Revision Note

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")

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: 2 October 2024

You've read 0 of your 10 free revision notes

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:Trees

Linked Lists (OCR A Level Computer Science)

Revision Note

Implementing a Linked List

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 10 free revision notes

Unlock more, it's free!

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

Author: Robert Hampton

Author: James Woodhouse