Lesson 10 · Linear structures

Singly Linked Lists

A singly linked list is a sequence of dynamically allocated nodes where each node points to the next. Because you can only move forward, mastering algorithms like cycle detection and finding the middle requires specific pointer tricks.

The One-Way Constraint

Unlike arrays, linked lists do not support random access. To find the 10th element, you must start at the head and follow the next pointers 9 times.

Because a singly linked list node has no prev pointer, you cannot easily walk backward. To delete a node, you must have a pointer to the node immediately before it.

No O(1) random access by index
Forward traversal only
Requires a 'previous' pointer for deletions

The Runner Technique (Two Pointers)

Many singly linked list problems are solved using two pointers moving at different speeds. This is known as the runner technique.

To find the middle of a list in one pass, place a slow pointer that moves one step at a time, and a fast pointer that moves two steps. When fast reaches the end, slow will be exactly in the middle.

Fast pointer moves 2x speed
Slow pointer moves 1x speed
Finds the middle without knowing the length

Key reference

Terms, operations, and practical uses

Node structure

NodeAn object containing a piece of data and a single pointer/reference to the next node in the sequence.
Head PointerThe only required reference to manage the list, pointing to the very first node.
Null ReferenceThe value stored in the final node's 'next' pointer, indicating the end of the list.

Algorithmic techniques

Runner TechniqueUsing two pointers that traverse the list at different speeds (e.g., slow moves 1 step, fast moves 2 steps).
Floyd's Cycle DetectionUsing the runner technique to detect infinite loops. If the fast pointer laps and equals the slow pointer, a cycle exists.
Dummy NodeA fake head node used to simplify edge cases when inserting or deleting the very first real node.

Operations

TraversalThe O(N) process of starting at the head and following pointers until null is reached.
In-Place ReversalFlipping all 'next' pointers to face backward using three tracking variables (prev, current, next_temp).
PredecessorThe node immediately before a target node. You must have a reference to the predecessor to delete a node in a singly linked list.

Code example

Finding the Middle of a Linked List

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

head = Node(1, Node(2, Node(3, Node(4, Node(5)))))

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

print('Middle node is', slow.val)

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return 0;
}

class Main {
    static class Node {
        int val;
        Node next;
        Node(int x) { val = x; }
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
    }
}

InputList: 1 -> 2 -> 3 -> 4 -> 5

OutputMiddle node is 3

Example

Run the example step by step

Output

Floyd's Cycle Detection

If a linked list has a loop, naive traversal will result in an infinite loop. We can use the fast/slow runner technique to detect cycles.

If fast and slow pointers enter a cycle, the fast pointer will eventually lap the slow pointer and they will point to the exact same node. If fast reaches null, there is no cycle.

Also called the Tortoise and Hare algorithm
Detects loops in O(N) time
Uses strictly O(1) extra space

List Reversal

Reversing a singly linked list is a classic operation. It is done in-place by carefully changing the next pointers of each node to point to the previous node.

This requires three pointers during traversal: prev (initially null), current (the node being modified), and next_temp (to temporarily store the remainder of the list before modifying current.next).

Reverses connections, not data
Requires 3 tracking variables
Operates in O(N) time and O(1) space