Linked lists

Structure

A linked list is a dynamic data structure made of nodes. Each node holds data and a pointer (reference) to the next node. A head pointer refers to the first node; the last node's pointer is null (None).

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

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

Head -> [Ash | ->] -> [Fig | ->] -> [Oak | ->] -> [Yew | None]

Operations

• Traverse: start at head; visit each node and follow next until it is None.
• Search: traverse, comparing each node's data with the target; stop when found or at the end. This is linear: O(n).
• Insert (in order): create a node; traverse to find the node before the insertion point; set new.next = previous.next; then previous.next = new. Inserting at the head: new.next = head; head = new.
• Delete: find the node before the one to delete; set previous.next = target.next, so the target is bypassed (if it is the head, head = head.next). No data is moved.

def traverse(self):
    current = self.head
    while current is not None:
        print(current.data)
        current = current.next

Benefits and drawbacks

Benefits: size grows and shrinks at run time; insertion and deletion only change pointers (no shifting of items), which is fast once the position is found.

Drawbacks: no direct access by index, so finding the 50th item means following 49 pointers; binary search is not possible; each node uses extra memory for its pointer; more complex code and pointer errors can lose the rest of the list.

Worked example

Insert 'Elm' into the ordered list Ash, Fig, Oak, Yew.

1. Create a node for Elm.
2. Traverse: Elm comes after Ash and before Fig, so the previous node is Ash.
3. Set Elm.next = Ash.next (the Fig node).
4. Set Ash.next = Elm.

Answer: Ash, Elm, Fig, Oak, Yew: two pointers changed, nothing moved.

Check yourself

1. What does the pointer in the last node of a linked list hold?
   • The address of the head
   • Null (None)
   • The data of the first node
   • The number of nodes
   Show answer

   Null (None). Null marks the end of the list.

2. To insert a new node N after node P, which order of pointer changes is correct?
   • P.next = N, then N.next = P.next
   • head = N, then N.next = None
   • P.next = None, then N.next = P
   • N.next = P.next, then P.next = N
   Show answer

   N.next = P.next, then P.next = N. If P.next were changed first, the rest of the list would be lost.

3. How is a node deleted from the middle of a linked list?
   • Every later node is moved back one place
   • The previous node's pointer is changed to point to the node after the one being deleted
   • The deleted node's data is set to 0
   • The head pointer is set to None
   Show answer

   The previous node's pointer is changed to point to the node after the one being deleted. The node is bypassed; nothing is shifted.

4. A search for 'Oak' in the list Ash, Fig, Oak, Yew starts at the head. How many nodes are examined, including the one that matches?
   Show answer

   3. Ash, Fig, Oak: 3 nodes.

5. A linear search for 'Pine' in the list Ash, Fig, Oak, Yew checks every node in turn until it reaches the end (it does not stop early). How many nodes are examined before it reports not found?
   Show answer

   4. It must reach the end of the list: 4 nodes.

6. Which is an advantage of a linked list over a static array?
   • Any item can be accessed directly by its index
   • Binary search can be used
   • Items can be inserted or deleted without shifting other items
   • It uses less memory per item
   Show answer

   Items can be inserted or deleted without shifting other items. Only pointers change.

7. Why can binary search not be used efficiently on a linked list?
   • There is no direct access to the middle node; reaching it means following pointers from the head
   • Linked lists cannot be sorted
   • Linked lists cannot store numbers
   • Binary search needs a hash function
   Show answer

   There is no direct access to the middle node; reaching it means following pointers from the head. Finding the middle is itself O(n).

8. A recursive count(node) function returns the number of nodes. What is a correct base case?
   • If node.next is None, return None
   • If node is None, return 0
   • If node.data is 0, return 1
   • Always return count(node.next)
   Show answer

   If node is None, return 0. count(None) = 0; otherwise 1 + count(node.next).

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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