Describe a linked list as nodes joined by pointers, implement insertion and deletion, and contrast it with an array

What this dot point is asking

SEAB wants you to describe a linked list as nodes joined by pointers, implement insertion and deletion, and contrast it with an array. The central idea is that a linked list trades the array's instant indexing for cheap insertion and deletion: because nodes are connected by pointers rather than stored contiguously, you change links instead of shifting elements.

The answer

Nodes and pointers

A linked list is a sequence of nodes. Each node holds a value and a pointer (reference) to the next node. A head pointer marks the start, and the last node's pointer is null to mark the end:

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

# head -> [A|*] -> [B|*] -> [C|null]

Nodes need not sit together in memory; the pointers thread them into order.

Traversal

To visit every node, start at the head and follow next until you reach null:

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

There is no index arithmetic, so reaching position $i$ takes $i$ steps: access is $O(n)$.

Insertion and deletion by relinking

The payoff is cheap structural change once you have the right node. To insert node X after node A:

1. Set X.next = A.next (point X at whatever A pointed to).
2. Set A.next = X.

The order matters: link X first, or the rest of the list is lost. To delete the node after A, set A.next = A.next.next, bypassing it. No elements shift, so given the position these are $O(1)$.

Linked list versus array

Arrays give instant random access; linked lists give cheap insertion and deletion and grow without reallocation, at the cost of pointer storage and slow indexing.

Examples in context

Example 1. A music playlist. A playlist where songs are frequently inserted and removed mid-list is a natural linked list: dropping a track between two others just reroutes two pointers, with no need to shift the rest of the queue as an array would require.

Example 2. Building stacks and queues. A stack or queue with no fixed capacity is often built on a linked list, because pushing or enqueuing is an $O(1)$ relink at one end and the structure grows one node at a time without reallocating a whole array. The linked list provides exactly the cheap end-operations these structures need.

Try this

Q1. State the time complexity of accessing the 5th node of a linked list and explain why. [2 marks]

• Cue. $O(n)$ - you must follow next pointers from the head, counting steps, with no index arithmetic.

Q2. Describe the pointer changes to delete the node after node A in a singly linked list. [2 marks]

• Cue. Set A.next = A.next.next, bypassing the node; it is then unreferenced and reclaimed. No elements shift.

Q3. Give one advantage of a linked list over an array. [1 mark]

• Cue. $O(1)$ insertion or deletion at the front (or at a known node) by relinking, and it grows without reallocating.