Linked Lists

This lesson covers linked lists — a fundamental dynamic data structure in the OCR A-Level Computer Science (H446) specification. Linked lists form the basis of many more complex structures such as stacks, queues, and graphs.

---

What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains:

1. Data — the value stored in the node.
2. A pointer (reference) — the memory address of the next node in the list.

Nodes are not stored contiguously in memory. Instead, each node can be anywhere in memory, and the pointer connects them together like links in a chain.

Key Terminology

Term	Definition
Node	A single element in the linked list, containing data and a pointer.
Head	A pointer to the first node in the list.
Tail	The last node in the list (its pointer is null/None).
Pointer/Reference	A value that stores the memory address of another node.
Null	A special value indicating "no next node" (end of the list).

---

Singly Linked Lists

In a singly linked list, each node has a pointer to the next node only. Traversal can only go in one direction — from head to tail.

Structure

Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

Example:
Head -> [10|*] -> [20|*] -> [30|*] -> NULL

Pseudocode (OCR Style)

record Node
    data: integer
    next: Node   // pointer to the next node (or null)
end record

head = null      // empty list

Python Implementation

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

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

    def is_empty(self):
        return self.head is None

    def insert_at_front(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("NULL")

---

Doubly Linked Lists

In a doubly linked list, each node has two pointers:

1. next — points to the next node.
2. prev — points to the previous node.

This allows traversal in both directions.

Structure

NULL <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> NULL

Example:
NULL <- [*|10|*] <-> [*|20|*] <-> [*|30|*] -> NULL

Python Implementation

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

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

    def insert_at_front(self, data):
        new_node = DoublyNode(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node

    def traverse_forward(self):
        current = self.head
        while current is not None:
            print(current.data, end=" <-> ")
            current = current.next
        print("NULL")

---

Operations on Linked Lists

1. Insert at Front — O(1)

Before: Head -> [10|*] -> [20|*] -> NULL
Insert 5 at front:
After:  Head -> [5|*] -> [10|*] -> [20|*] -> NULL

Steps:

1. Create a new node with the data.
2. Set the new node's next pointer to the current head.
3. Update head to point to the new node.

2. Insert at End — O(n)

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    current = self.head
    while current.next is not None:
        current = current.next
    current.next = new_node

You must traverse the entire list to find the last node, hence O(n).

3. Insert at Position — O(n)

def insert_at_position(self, data, position):
    if position == 0:
        self.insert_at_front(data)
        return
    new_node = Node(data)
    current = self.head
    for i in range(position - 1):
        if current is None:
            raise IndexError("Position out of range")
        current = current.next
    new_node.next = current.next
    current.next = new_node

4. Delete a Node — O(n)

To delete a node, you must find the previous node and update its pointer to skip the deleted node.