Linked List Insert and Delete Operations — GCSE Computer Science

What is the structure of a linked list node?

Each node in a singly linked list contains exactly two parts:

• data — the value being stored (an integer, a name, etc.),
• next — a pointer to the next node in the chain (or None if it is the last node).

In Python this is typically modelled with a class:

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

The linked list itself keeps track of the head — a pointer to the first node. If the list is empty, head is None.

head
  ↓
[10 | →] → [25 | →] → [37 | →] → [42 | None]

How do you insert a node at the head?

Inserting at the head is the fastest operation — O(1) — because no traversal is needed:

• Create the new node.
• Set the new node's next to point to the current head.
• Update head to point to the new node.

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

    def insert_at_head(self, data):
        new_node = Node(data)     # step 1: create
        new_node.next = self.head # step 2: point to old head
        self.head = new_node      # step 3: update head

Before: head → [25] → [37] → None Insert 10: head → [10] → [25] → [37] → None

How do you insert a node at the tail?

Inserting at the tail requires traversing the whole list to find the last node — O(n):

def insert_at_tail(self, data):
    new_node = Node(data)
    if self.head is None:         # empty list
        self.head = new_node
        return
    current = self.head
    while current.next is not None:  # walk to last node
        current = current.next
    current.next = new_node          # attach new node

Before: head → [10] → [25] → None Insert 37 at tail: head → [10] → [25] → [37] → None

How do you delete a node by value?

Deletion requires finding the node whose data matches the target and re-linking the chain to bypass it. There are two cases:

• Deleting the head: update head to head.next.
• Deleting any other node: find the node before the target and update its next pointer to skip the target node.

def delete(self, target):
    if self.head is None:
        return                          # empty list, nothing to do

    if self.head.data == target:        # target is the head
        self.head = self.head.next
        return

    current = self.head
    while current.next is not None:     # walk until node before target
        if current.next.data == target:
            current.next = current.next.next   # skip the target
            return
        current = current.next
    # target not found — do nothing

Before: head → [10] → [25] → [37] → None Delete 25: head → [10] → [37] → None

The node [25] still exists in memory but nothing points to it, so the garbage collector reclaims it.

How do you traverse a linked list to display it?

Traversal visits every node once in order — O(n):

def display(self):
    current = self.head
    while current is not None:
        print(current.data, end=" → ")
        current = current.next
    print("None")

This pattern — start at head, follow .next until None — is the foundation of every linked list operation that touches more than the first element.

How does a linked list compare with an array for these operations?

The key advantage of linked lists over arrays is insertion and deletion near the head without shifting elements. The key disadvantage is the absence of O(1) random access.

Frequently asked questions

Why do linked lists not support index-based access?

An array stores elements in consecutive memory locations, so the address of element at index i can be calculated instantly as base_address + i × element_size. Linked list nodes are scattered in memory with no fixed relationship between their addresses; the only way to reach node i is to start at head and follow next pointers i times — an O(n) operation.

What is a doubly linked list?

A doubly linked list adds a second pointer to each node: prev, pointing to the preceding node. This makes traversal in both directions possible and reduces deletion from O(n) to O(1) when you already have a reference to the node being deleted (you no longer need to find the node before it). The cost is doubled pointer storage per node. Doubly linked lists are the underlying structure for Python's collections.deque.

How do I draw a linked list trace for a GCSE exam?

Draw each node as a box split into two halves — left for data, right for the arrow (next pointer). Draw arrows between boxes. Show the head pointer at the start. For insertion and deletion traces, cross out the old arrows and draw new ones. Label each step clearly: "new_node created → new_node.next set → head updated."

When should you use a linked list instead of a list (array) in Python?

In most Python programs, Python's built-in list is faster and simpler. Linked lists are worth using when: (a) you are frequently inserting or deleting at the head (O(1) vs O(n)), (b) the data size is unknown and you want to avoid reallocation, or (c) you are building a higher-level data structure like a queue that naturally maps onto a linked list. For GCSE exam questions, focus on explaining the structural advantages, not advocating for them in all cases.

---

For Socratic GCSE tutoring and free Computer Science flashcards, see aitutors.me.