Singly Linked List — Complete Implementation with All Operations

Master the singly linked list with complete Python and Java implementations of every operation — insert at head/tail/position, delete by value/position, search, reverse, detect and remove loops, find middle, merge sorted lists, and all classic interview techniques.

Introduction

The singly linked list is the simplest form of linked list and the most frequently tested in interviews. Every node has exactly one pointer — next — pointing forward. This simplicity makes it the ideal structure for understanding pointer manipulation, recursion, and the classic two-pointer technique.

This lesson implements every operation completely, explains why each works the way it does, and presents the patterns that unlock dozens of interview problems.

Insertion Operations

Insert at Head — O(1)

python example

def insert_at_head(self, data):
    """
    Insert a new node at the beginning of the list.
    The new node becomes the new head.
    """
    new_node = Node(data)
    new_node.next = self.head   # New node points to old head
    self.head = new_node        # Head now points to new node

    if self.tail is None:       # If list was empty, tail = head
        self.tail = new_node

    self._size += 1

Visualization:

Before: head	[10] → [25] → None
After: head	[5] → [10] → [25] → None
Steps	2 pointer assignments = O(1)

Insert at Tail — O(1) with tail pointer

python example

def insert_at_tail(self, data):
    """
    Insert at the end of the list.
    O(1) because we maintain a tail pointer.
    Without tail pointer, this would be O(n).
    """
    new_node = Node(data)

    if self.head is None:
        self.head = self.tail = new_node
    else:
        self.tail.next = new_node   # Current tail points to new node
        self.tail = new_node        # Update tail to new node

    self._size += 1

Insert at Position — O(n)

Example

def insert_at_position(self, data, position): """ Insert at given position (0-indexed). Position 0 = insert at head. Position n = insert at tail. """ if position < 0 or position > self._size: raise IndexError(f"Position {position} out of range [0, {self._size}]") if position == 0: self.insert_at_head(data) return if position == self._size: self.insert_at_tail(data) return # Traverse to node just BEFORE the insertion position current = self.head for _ in range(position - 1): current = current.next # Insert new node between current and current.next new_node = Node(data) new_node.next = current.next current.next = new_node self._size += 1

Visualization for insert at position 2:

Example

Before: [1] → [2] → [3] → [4] → None Insert 99 at position 2: Traverse to position 1 (node with data=2). current = node(2) new_node(99).next = current.next (= node(3)) current.next = new_node(99) After: [1] → [2] → [99] → [3] → [4] → None

Deletion Operations

Delete Head — O(1)

python example

def delete_head(self):
    """Remove and return the first element."""
    if self.head is None:
        raise ValueError("Cannot delete from empty list")

    removed_data = self.head.data
    self.head = self.head.next   # Move head to next node

    if self.head is None:        # List is now empty
        self.tail = None

    self._size -= 1
    return removed_data

Delete Tail — O(n) for singly linked list

python example

def delete_tail(self):
    """
    Remove and return the last element.
    O(n) for singly linked list — must find second-to-last node.
    (A doubly linked list can do this in O(1).)
    """
    if self.head is None:
        raise ValueError("Cannot delete from empty list")

    if self.head == self.tail:   # Only one node
        removed = self.head.data
        self.head = self.tail = None
        self._size -= 1
        return removed

    # Find the second-to-last node
    current = self.head
    while current.next != self.tail:
        current = current.next

    removed = self.tail.data
    current.next = None    # Second-to-last becomes new tail
    self.tail = current

    self._size -= 1
    return removed

Delete by Value (First Occurrence) — O(n)

python example

def delete_by_value(self, value):
    """
    Delete the first node with the given value.
    Returns True if found and deleted, False if not found.
    """
    if self.head is None:
        return False

    # Special case: head is the target
    if self.head.data == value:
        self.delete_head()
        return True

    # Traverse to find the node BEFORE the target
    current = self.head
    while current.next is not None:
        if current.next.data == value:
            # Skip over the target node
            if current.next == self.tail:   # Deleting tail
                self.tail = current
            current.next = current.next.next
            self._size -= 1
            return True
        current = current.next

    return False   # Value not found

Delete at Position — O(n)

python example

def delete_at_position(self, position):
    """Delete node at given position (0-indexed)."""
    if position < 0 or position >= self._size:
        raise IndexError(f"Position {position} out of range")

    if position == 0:
        return self.delete_head()

    current = self.head
    for _ in range(position - 1):
        current = current.next

    removed = current.next.data

    if current.next == self.tail:
        self.tail = current

    current.next = current.next.next
    self._size -= 1
    return removed

Search — O(n)

python example

def search(self, value):
    """Return index of first occurrence of value, or -1."""
    current = self.head
    index = 0

    while current is not None:
        if current.data == value:
            return index
        current = current.next
        index += 1

    return -1

def contains(self, value):
    return self.search(value) != -1

Reversal — O(n), O(1) Space

Reversing a linked list is one of the most important operations and the most common interview question. The iterative approach is essential.

Iterative Reversal

python example

def reverse(self):
    """
    Reverse the linked list in-place.
    Uses three pointers: prev, current, next_node.
    Time: O(n), Space: O(1)
    """
    prev = None
    current = self.head
    self.tail = self.head   # Current head becomes new tail

    while current is not None:
        next_node = current.next   # Save next (we're about to overwrite it)
        current.next = prev        # Reverse the pointer
        prev = current             # Move prev forward
        current = next_node        # Move current forward

    self.head = prev   # prev is now the last processed node = new head

Step-by-step visualization:

Initial: head	[1] → [2] → [3] → [4] → None
State: None ← [1] [2]	[3] → [4] → None
State: None ← [1] ← [2] [3]	[4] → None
Result: head	[4] → [3] → [2] → [1] → None ✓

Recursive Reversal

python example

def reverse_recursive(self):
    """Recursive reversal. O(n) time, O(n) space (call stack)."""
    self.head = self._reverse_helper(self.head)

def _reverse_helper(self, node):
    """Returns the new head after reversing the list starting at node."""
    # Base case: empty or single node
    if node is None or node.next is None:
        return node

    # Recursively reverse the rest
    new_head = self._reverse_helper(node.next)

    # Make the next node point back to current
    node.next.next = node
    node.next = None

    return new_head

Finding the Middle Node

Floyd's Slow-Fast Pointer Technique:

Example

def find_middle(self): """ Find the middle node using slow and fast pointers. Slow moves 1 step, fast moves 2 steps. When fast reaches end, slow is at middle. Time: O(n), Space: O(1) """ if self.head is None: return None slow = self.head fast = self.head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps return slow # slow is at middle when fast reaches end # For even-length lists, returns the second middle # [1,2,3,4,5] → returns node(3) # [1,2,3,4] → returns node(3) — second of two middles

Detect and Remove a Loop (Cycle)

Floyd's Cycle Detection:

python example

def has_cycle(self):
    """
    Detect if the linked list has a cycle.
    Time: O(n), Space: O(1)
    """
    slow = fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True   # Cycle detected

    return False

def find_cycle_start(self):
    """
    Find the start node of the cycle (if exists).
    After detecting the meeting point, move one pointer to head.
    Both move 1 step — they will meet at the cycle start.
    Time: O(n), Space: O(1)
    """
    slow = fast = self.head
    has_cycle = False

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    slow = self.head   # Reset slow to head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow   # Both meet at cycle start

Complete List of Operations with Complexity

Operation	Time	Space	Notes
Insert at head	O(1)	O(1)
Insert at tail (with tail ptr)	O(1)	O(1)
Insert at tail (no tail ptr)	O(n)	O(1)	Must traverse
Insert at position i	O(n)	O(1)	Traverse to i-1
Delete head	O(1)	O(1)
Delete tail	O(n)	O(1)	Must find second-to-last
Delete by value	O(n)	O(1)
Delete at position	O(n)	O(1)
Search	O(n)	O(1)
Traverse all	O(n)	O(1)
Reverse (iterative)	O(n)	O(1)	3 pointer assignments per step
Reverse (recursive)	O(n)	O(n)	Stack space = list length
Find middle	O(n)	O(1)	Floyd's slow-fast
Detect cycle	O(n)	O(1)	Floyd's tortoise-hare
Find cycle start	O(n)	O(1)	Floyd's two-phase
Merge two sorted lists	O(m+n)	O(1)	Two pointer merge

Merging Two Sorted Linked Lists

python example

def merge_sorted(l1, l2):
    """
    Merge two sorted linked lists into one sorted linked list.
    Time: O(m + n), Space: O(1) — modifies existing nodes
    """
    # Dummy head makes edge cases cleaner
    dummy = Node(0)
    current = dummy

    while l1 is not None and l2 is not None:
        if l1.data <= l2.data:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach remaining nodes
    current.next = l1 if l1 is not None else l2

    return dummy.next   # Skip the dummy head

Summary

The singly linked list is defined by:

O(1) insert/delete at head — the primary advantage
O(n) access by index — the primary disadvantage
Reversal (three-pointer iterative) — the most asked interview operation
Floyd's slow-fast pointer — finds middle, detects cycles, finds cycle start
Tail pointer optimization — gives O(1) append
Dummy head node trick — simplifies edge cases in insertion/deletion/merge

*Next Lesson: Doubly Linked List — Bidirectional traversal, O(1) deletion of any node given its reference, and LRU cache implementation.*

Introduction

This lesson implements every operation completely, explains why each works the way it does, and presents the patterns that unlock dozens of interview problems.

Insertion Operations

Insert at Head — O(1)

python example

def insert_at_head(self, data):
    """
    Insert a new node at the beginning of the list.
    The new node becomes the new head.
    """
    new_node = Node(data)
    new_node.next = self.head   # New node points to old head
    self.head = new_node        # Head now points to new node

    if self.tail is None:       # If list was empty, tail = head
        self.tail = new_node

    self._size += 1

Visualization:

Before: head	[10] → [25] → None
After: head	[5] → [10] → [25] → None
Steps	2 pointer assignments = O(1)

Insert at Tail — O(1) with tail pointer

python example

def insert_at_tail(self, data):
    """
    Insert at the end of the list.
    O(1) because we maintain a tail pointer.
    Without tail pointer, this would be O(n).
    """
    new_node = Node(data)

    if self.head is None:
        self.head = self.tail = new_node
    else:
        self.tail.next = new_node   # Current tail points to new node
        self.tail = new_node        # Update tail to new node

    self._size += 1

Insert at Position — O(n)

Example

Visualization for insert at position 2:

Example

Deletion Operations

Delete Head — O(1)

python example

def delete_head(self):
    """Remove and return the first element."""
    if self.head is None:
        raise ValueError("Cannot delete from empty list")

    removed_data = self.head.data
    self.head = self.head.next   # Move head to next node

    if self.head is None:        # List is now empty
        self.tail = None

    self._size -= 1
    return removed_data

Delete Tail — O(n) for singly linked list

python example

def delete_tail(self):
    """
    Remove and return the last element.
    O(n) for singly linked list — must find second-to-last node.
    (A doubly linked list can do this in O(1).)
    """
    if self.head is None:
        raise ValueError("Cannot delete from empty list")

    if self.head == self.tail:   # Only one node
        removed = self.head.data
        self.head = self.tail = None
        self._size -= 1
        return removed

    # Find the second-to-last node
    current = self.head
    while current.next != self.tail:
        current = current.next

    removed = self.tail.data
    current.next = None    # Second-to-last becomes new tail
    self.tail = current

    self._size -= 1
    return removed

Delete by Value (First Occurrence) — O(n)

python example

def delete_by_value(self, value):
    """
    Delete the first node with the given value.
    Returns True if found and deleted, False if not found.
    """
    if self.head is None:
        return False

    # Special case: head is the target
    if self.head.data == value:
        self.delete_head()
        return True

    # Traverse to find the node BEFORE the target
    current = self.head
    while current.next is not None:
        if current.next.data == value:
            # Skip over the target node
            if current.next == self.tail:   # Deleting tail
                self.tail = current
            current.next = current.next.next
            self._size -= 1
            return True
        current = current.next

    return False   # Value not found

Delete at Position — O(n)

python example

def delete_at_position(self, position):
    """Delete node at given position (0-indexed)."""
    if position < 0 or position >= self._size:
        raise IndexError(f"Position {position} out of range")

    if position == 0:
        return self.delete_head()

    current = self.head
    for _ in range(position - 1):
        current = current.next

    removed = current.next.data

    if current.next == self.tail:
        self.tail = current

    current.next = current.next.next
    self._size -= 1
    return removed

Search — O(n)

python example

def search(self, value):
    """Return index of first occurrence of value, or -1."""
    current = self.head
    index = 0

    while current is not None:
        if current.data == value:
            return index
        current = current.next
        index += 1

    return -1

def contains(self, value):
    return self.search(value) != -1

Reversal — O(n), O(1) Space

Reversing a linked list is one of the most important operations and the most common interview question. The iterative approach is essential.

Iterative Reversal

python example

def reverse(self):
    """
    Reverse the linked list in-place.
    Uses three pointers: prev, current, next_node.
    Time: O(n), Space: O(1)
    """
    prev = None
    current = self.head
    self.tail = self.head   # Current head becomes new tail

    while current is not None:
        next_node = current.next   # Save next (we're about to overwrite it)
        current.next = prev        # Reverse the pointer
        prev = current             # Move prev forward
        current = next_node        # Move current forward

    self.head = prev   # prev is now the last processed node = new head

Step-by-step visualization:

Initial: head	[1] → [2] → [3] → [4] → None
State: None ← [1] [2]	[3] → [4] → None
State: None ← [1] ← [2] [3]	[4] → None
Result: head	[4] → [3] → [2] → [1] → None ✓

Recursive Reversal

python example

def reverse_recursive(self):
    """Recursive reversal. O(n) time, O(n) space (call stack)."""
    self.head = self._reverse_helper(self.head)

def _reverse_helper(self, node):
    """Returns the new head after reversing the list starting at node."""
    # Base case: empty or single node
    if node is None or node.next is None:
        return node

    # Recursively reverse the rest
    new_head = self._reverse_helper(node.next)

    # Make the next node point back to current
    node.next.next = node
    node.next = None

    return new_head

Finding the Middle Node

Floyd's Slow-Fast Pointer Technique:

Example

Detect and Remove a Loop (Cycle)

Floyd's Cycle Detection:

python example

def has_cycle(self):
    """
    Detect if the linked list has a cycle.
    Time: O(n), Space: O(1)
    """
    slow = fast = self.head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True   # Cycle detected

    return False

def find_cycle_start(self):
    """
    Find the start node of the cycle (if exists).
    After detecting the meeting point, move one pointer to head.
    Both move 1 step — they will meet at the cycle start.
    Time: O(n), Space: O(1)
    """
    slow = fast = self.head
    has_cycle = False

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    slow = self.head   # Reset slow to head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow   # Both meet at cycle start

Complete List of Operations with Complexity

Operation	Time	Space	Notes
Insert at head	O(1)	O(1)
Insert at tail (with tail ptr)	O(1)	O(1)
Insert at tail (no tail ptr)	O(n)	O(1)	Must traverse
Insert at position i	O(n)	O(1)	Traverse to i-1
Delete head	O(1)	O(1)
Delete tail	O(n)	O(1)	Must find second-to-last
Delete by value	O(n)	O(1)
Delete at position	O(n)	O(1)
Search	O(n)	O(1)
Traverse all	O(n)	O(1)
Reverse (iterative)	O(n)	O(1)	3 pointer assignments per step
Reverse (recursive)	O(n)	O(n)	Stack space = list length
Find middle	O(n)	O(1)	Floyd's slow-fast
Detect cycle	O(n)	O(1)	Floyd's tortoise-hare
Find cycle start	O(n)	O(1)	Floyd's two-phase
Merge two sorted lists	O(m+n)	O(1)	Two pointer merge

Merging Two Sorted Linked Lists

python example

def merge_sorted(l1, l2):
    """
    Merge two sorted linked lists into one sorted linked list.
    Time: O(m + n), Space: O(1) — modifies existing nodes
    """
    # Dummy head makes edge cases cleaner
    dummy = Node(0)
    current = dummy

    while l1 is not None and l2 is not None:
        if l1.data <= l2.data:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach remaining nodes
    current.next = l1 if l1 is not None else l2

    return dummy.next   # Skip the dummy head

Summary

The singly linked list is defined by:

O(1) insert/delete at head — the primary advantage
O(n) access by index — the primary disadvantage
Reversal (three-pointer iterative) — the most asked interview operation
Floyd's slow-fast pointer — finds middle, detects cycles, finds cycle start
Tail pointer optimization — gives O(1) append
Dummy head node trick — simplifies edge cases in insertion/deletion/merge

*Next Lesson: Doubly Linked List — Bidirectional traversal, O(1) deletion of any node given its reference, and LRU cache implementation.*

Introduction

Insertion Operations

Insert at Head — O(1)

Insert at Tail — O(1) with tail pointer

Insert at Position — O(n)

Deletion Operations

Delete Head — O(1)

Delete Tail — O(n) for singly linked list

Delete by Value (First Occurrence) — O(n)

Delete at Position — O(n)

Search — O(n)

Reversal — O(n), O(1) Space

Iterative Reversal

Recursive Reversal

Finding the Middle Node

Detect and Remove a Loop (Cycle)

Complete List of Operations with Complexity

Merging Two Sorted Linked Lists

Summary

Continue learning this concept

Introduction

Insertion Operations

Insert at Head — O(1)

Insert at Tail — O(1) with tail pointer

Insert at Position — O(n)

Deletion Operations

Delete Head — O(1)

Delete Tail — O(n) for singly linked list

Delete by Value (First Occurrence) — O(n)

Delete at Position — O(n)

Search — O(n)

Reversal — O(n), O(1) Space

Iterative Reversal

Recursive Reversal

Finding the Middle Node

Detect and Remove a Loop (Cycle)

Complete List of Operations with Complexity

Merging Two Sorted Linked Lists

Summary

Continue learning this concept