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