Linked Lists

This lesson covers linked lists — a fundamental dynamic data structure where elements are stored in nodes connected by pointers. Linked lists are a key topic in A-Level Computer Science and provide the foundation for understanding many other data structures.

---

What is a Linked List?

A linked list is a dynamic data structure consisting of a sequence of nodes. Each node contains:

1. Data — the value stored in the node.
2. Pointer (next) — a reference to the next node in the list.

The first node is called the head. The last node's pointer is set to null (or None), indicating the end of the list.

HEAD → [Data|Next] → [Data|Next] → [Data|Next] → NULL

Example

HEAD → [10|●] → [20|●] → [30|●] → NULL

This linked list contains three nodes storing the values 10, 20, and 30.

---

Types of Linked Lists

Type	Description
Singly linked list	Each node has a pointer to the next node only. Traversal is one-directional.
Doubly linked list	Each node has pointers to both the next and previous nodes. Traversal is bidirectional.
Circular linked list	The last node points back to the first node, forming a loop.

Singly Linked List

HEAD → [A|●] → [B|●] → [C|●] → NULL

Doubly Linked List

NULL ← [●|A|●] ⇄ [●|B|●] ⇄ [●|C|●] → NULL

Circular Linked List

HEAD → [A|●] → [B|●] → [C|●] → (back to HEAD)

---

Implementing a Singly Linked List

Node Class

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Pointer to the next node

Linked List Class

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

    def is_empty(self) -> bool:
        return self.head is None

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

    def add_to_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

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

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

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

---

Operations and Time Complexity

Operation	Description	Time Complexity
Add to front	Insert a new node at the head	O(1)
Add to end	Traverse to the last node and insert	O(n)
Search	Traverse from head until found or end	O(n)
Delete	Find the node and update pointers	O(n)
Access by index	Traverse from head to position i	O(n)

Exam Tip: Linked lists do NOT support random access. To access the kth element, you must start at the head and follow k pointers. This is O(n), unlike arrays where access is O(1).

---