All subjects · Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Implementing a linked list with classes

Edexcel IAL Computer Science · WCP04 Advanced Practical Programming and Problem-solving

A linked list stores items in nodes. Each node holds its data and a reference (pointer) to the next node, so items can be inserted or removed by changing references rather than moving data.

Practise this in the app: instant marking and a fix for every mistake. Free, no email needed to start.

Practise this lesson

Nodes and references

A Node object has data and next. The last node's next is None.
The list object stores only head, a reference to the first node (None when the list is empty).
To traverse, start at head and follow next until you reach None.
Unlike a Python list, there is no direct indexing: reaching the 100th item means following 99 references.

The code

Every operation is a traversal plus some reference changes.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def traverse(self):
        items = []
        current = self.head
        while current is not None:
            items.append(current.data)
            current = current.next
        return items

    def insert_front(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    def insert_sorted(self, data):
        node = Node(data)
        if self.head is None or data < self.head.data:
            node.next = self.head
            self.head = node
            return
        current = self.head
        while current.next is not None and current.next.data < data:
            current = current.next
        node.next = current.next
        current.next = node

    def find(self, target):
        current = self.head
        while current is not None:
            if current.data == target:
                return current
            current = current.next
        return None

    def update(self, old, new):
        node = self.find(old)
        if node is not None:
            node.data = new
        return node is not None

    def remove(self, target):
        if self.head is None:
            return False
        if self.head.data == target:
            self.head = self.head.next
            return True
        current = self.head
        while current.next is not None:
            if current.next.data == target:
                current.next = current.next.next
                return True
            current = current.next
        return False

Inserting and removing

Insert at the front: the new node points at the old head; head points at the new node.
Insert in order: walk until the next node's data is bigger, then link the new node in between: node.next = current.next, then current.next = node. The order of these two lines matters: reversing them loses the rest of the list.
Remove: find the node before the target and set its next to skip over the target. The head is a special case.
Always handle the empty list and the head first.

# Node and LinkedList classes as above

names = LinkedList()
for n in ["Kim", "Ali", "Zed", "Mo"]:
    names.insert_sorted(n)
print(names.traverse())
names.remove("Mo")
names.update("Zed", "Ben")
names.insert_front("Ann")
print(names.traverse(), names.find("Ali") is not None)

Output:

['Ali', 'Kim', 'Mo', 'Zed']
['Ann', 'Ali', 'Kim', 'Ben'] True

Worked example

Draw the references when 15 is inserted into the sorted list 10 -> 20 -> 30.

Start with current at 10. current.next.data is 20, which is not less than 15, so stop.
node.next = current.next: the new node 15 points at 20.
current.next = node: 10 now points at 15.
List: 10 -> 15 -> 20 -> 30

Answer: 10 -> 15 -> 20 -> 30, with only two references changed and no data moved.

Key idea: Node(data, next); list holds head; traverse by following next until None; insert by linking new.next first, then the previous node's next; remove by making the previous node skip the target; handle empty and head cases.

Check yourself

The Node and LinkedList classes from the lesson are included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def traverse(self): items = [] current = self.head while current is not None: items.append(current.data) current = current.next return items def insert_front(self, data): node = Node(data) node.next = self.head self.head = node def insert_sorted(self, data): node = Node(data) if self.head is None or data < self.head.data: node.next = self.head self.head = node return current = self.head while current.next is not None and current.next.data < data: current = current.next node.next = current.next current.next = node def find(self, target): current = self.head while current is not None: if current.data == target: return current current = current.next return None def update(self, old, new): node = self.find(old) if node is not None: node.data = new return node is not None def remove(self, target): if self.head is None: return False if self.head.data == target: self.head = self.head.next return True current = self.head while current.next is not None: if current.next.data == target: current.next = current.next.next return True current = current.next return False l = LinkedList() for x in [3, 1, 4, 1]: l.insert_front(x) print(l.traverse()) ```
Show answer
[1, 4, 1, 3]. Each insert_front puts the new value first, so the list is reversed. Output: `[1, 4, 1, 3]`
The Node and LinkedList classes from the lesson are included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def traverse(self): items = [] current = self.head while current is not None: items.append(current.data) current = current.next return items def insert_front(self, data): node = Node(data) node.next = self.head self.head = node def insert_sorted(self, data): node = Node(data) if self.head is None or data < self.head.data: node.next = self.head self.head = node return current = self.head while current.next is not None and current.next.data < data: current = current.next node.next = current.next current.next = node def find(self, target): current = self.head while current is not None: if current.data == target: return current current = current.next return None def update(self, old, new): node = self.find(old) if node is not None: node.data = new return node is not None def remove(self, target): if self.head is None: return False if self.head.data == target: self.head = self.head.next return True current = self.head while current.next is not None: if current.next.data == target: current.next = current.next.next return True current = current.next return False l = LinkedList() for x in [40, 10, 30, 20]: l.insert_sorted(x) l.remove(30) print(l.traverse()) ```
Show answer
[10, 20, 40]. insert_sorted keeps ascending order: 10, 20, 30, 40. Removing 30 links 20 straight to 40. Output: `[10, 20, 40]`
The Node and LinkedList classes from the lesson are included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def traverse(self): items = [] current = self.head while current is not None: items.append(current.data) current = current.next return items def insert_front(self, data): node = Node(data) node.next = self.head self.head = node def insert_sorted(self, data): node = Node(data) if self.head is None or data < self.head.data: node.next = self.head self.head = node return current = self.head while current.next is not None and current.next.data < data: current = current.next node.next = current.next current.next = node def find(self, target): current = self.head while current is not None: if current.data == target: return current current = current.next return None def update(self, old, new): node = self.find(old) if node is not None: node.data = new return node is not None def remove(self, target): if self.head is None: return False if self.head.data == target: self.head = self.head.next return True current = self.head while current.next is not None: if current.next.data == target: current.next = current.next.next return True current = current.next return False l = LinkedList() for x in "cba": l.insert_front(x) print(l.remove("a"), l.remove("q"), l.head.data) ```
Show answer
True False b. a is at the head, so head moves to b and remove returns True; q is not found, so False. Output: `True False b`
The Node and LinkedList classes from the lesson are included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def traverse(self): items = [] current = self.head while current is not None: items.append(current.data) current = current.next return items def insert_front(self, data): node = Node(data) node.next = self.head self.head = node def insert_sorted(self, data): node = Node(data) if self.head is None or data < self.head.data: node.next = self.head self.head = node return current = self.head while current.next is not None and current.next.data < data: current = current.next node.next = current.next current.next = node def find(self, target): current = self.head while current is not None: if current.data == target: return current current = current.next return None def update(self, old, new): node = self.find(old) if node is not None: node.data = new return node is not None def remove(self, target): if self.head is None: return False if self.head.data == target: self.head = self.head.next return True current = self.head while current.next is not None: if current.next.data == target: current.next = current.next.next return True current = current.next return False l = LinkedList() for x in range(5, 0, -1): l.insert_front(x) steps = 0 current = l.head while current.data != 4: current = current.next steps = steps + 1 print(steps) ```
Show answer
3. The list is 1, 2, 3, 4, 5 from the head; reaching 4 takes `3` moves along next references.
In insert_sorted, why must `node.next = current.next` come before `current.next = node`?
- Python requires attributes to be set in alphabetical order
- It makes the list circular
- Otherwise the reference to the rest of the list is overwritten and lost
- It is faster but either order works
Show answer
Otherwise the reference to the rest of the list is overwritten and lost. If current.next is changed first, nothing points to the remainder of the list any more.
Compared with a Python list, what is a disadvantage of a linked list?
- Reaching the nth item needs n - 1 steps along references, so there is no fast indexing
- Inserting in the middle requires moving all later items
- It cannot store strings
- Its size must be fixed in advance
Show answer
Reaching the nth item needs n - 1 steps along references, so there is no fast indexing. Access is sequential. Insertion is cheap once the place is found, and the list grows freely.
What should `traverse()` return for an empty LinkedList, and why does the code manage it?
- None, because head is None
- It raises AttributeError
- An empty list, because current starts as None so the while loop never runs
- A list containing None
Show answer
An empty list, because current starts as None so the while loop never runs. The loop condition `current is not None` is false straight away.

Practise with instant feedback

Sources

Last updated 8 November 2026. Spotted a mistake? Tell us.