Singly Linked Lists

A singly linked list is a linear data structure made of individual nodes, where each node holds a value and a single pointer to the next node in the sequence. Unlike a Python list, which stores its elements in one contiguous block of memory, a linked list’s nodes can live anywhere in memory — they are connected only by these pointers. This makes certain operations, like inserting at the front, extremely cheap, while others, like jumping to the 500th element, become slow. Understanding linked lists is essential in DSA because they are the foundation for stacks, queues, and more advanced structures, and they appear constantly in coding interviews.

Overview: How Singly Linked Lists Work

Picture a scavenger hunt where each clue tells you where to find the next clue, but you have no way of jumping ahead — you must follow the trail one step at a time. That is exactly how a singly linked list works. Each node is a small object with two pieces of data: the value it stores, and a reference called next that points to the following node (or to None if it is the last node). The list itself only needs to remember one thing: a reference to the first node, called the head. Everything else is reachable by following next pointers, one hop at a time.

This design has a direct consequence: a singly linked list has no random access. To reach the 5th element, you must start at the head and follow four next pointers, because there is no arithmetic shortcut the way there is with an array (where element i lives at a computable memory offset). This is the central tradeoff of linked lists versus Python’s built-in list (which is implemented as a dynamic array): you give up O(1) indexing in exchange for O(1) insertion and deletion at the front, and no need to shift elements when the structure grows or shrinks in the middle.

Because a node only knows about the node after it (not before), a singly linked list can only be traversed in one direction — forward. This is the key difference from a doubly linked list, which adds a prev pointer at the cost of extra memory per node. If you never need to walk backward or delete an arbitrary node in O(1) given only a reference to it, a singly linked list is simpler and uses less memory.

Time and Space Complexity

The complexity of every operation comes down to one question: does it require a traversal from the head, or can it be done with a fixed number of pointer updates? Operations that only touch the head (or a node you already have a reference to) are O(1). Operations that require searching for a value, an index, or the tail (without a cached tail pointer) are O(n), because in the worst case you must visit every node.

Operation	Time Complexity	Why
Access by index / search by value	O(n)	No random access — must walk from head, following next pointers one at a time
Insert at head (prepend)	O(1)	Just create a node and repoint head — no traversal needed
Insert at tail (no tail pointer)	O(n)	Must traverse to the last node before attaching the new one
Insert at tail (tail pointer maintained)	O(1)	Direct reference to the last node avoids traversal
Insert after a known node	O(1)	Only two pointer reassignments, regardless of list size
Delete at head	O(1)	head is simply repointed to head.next
Delete by value	O(n)	Must search for the node (and the node before it) first
Space (overall structure)	O(n)	One Node object per element, each with an extra pointer field

The space complexity of the list itself is O(n) for n elements, but note that each node also carries the overhead of the next pointer — something a plain array-backed list does not pay per element. Most linked-list operations use O(1) extra space beyond the list itself, since they only need a small, fixed number of temporary variables (like previous and current) no matter how large the list is.

Examples

Example 1: Building a Linked List and Printing It

This example defines a minimal Node class and a SinglyLinkedList wrapper with an append method that adds to the end, plus a to_list helper that converts the linked list into a Python list so we can easily print and verify it.

from __future__ import annotations


class Node:
    def __init__(self, value: int, next: Node | None = None) -> None:
        self.value = value
        self.next = next


class SinglyLinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None

    def append(self, value: int) -> None:
        new_node = Node(value)
        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 to_list(self) -> list[int]:
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result


linked_list = SinglyLinkedList()
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
print(linked_list.to_list())

Output:

[10, 20, 30]

Each call to append walks from head until it finds a node whose next is None (the current last node), then attaches the new node there. After three appends, the chain is 10 -> 20 -> 30 -> None. Notice this append is O(n) per call because it re-traverses the whole list every time — a production implementation would cache a tail reference to make appends O(1), which is discussed in Best Practices.

Example 2: Inserting at the Head and Deleting by Value

This example shows the cheap O(1) operation (prepend) alongside the more expensive O(n) operation (delete, which must search for the target value).

from __future__ import annotations


class Node:
    def __init__(self, value: int, next: Node | None = None) -> None:
        self.value = value
        self.next = next


class SinglyLinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None

    def prepend(self, value: int) -> None:
        self.head = Node(value, self.head)

    def delete(self, value: int) -> bool:
        previous = None
        current = self.head
        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                return True
            previous = current
            current = current.next
        return False

    def to_list(self) -> list[int]:
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result


linked_list = SinglyLinkedList()
for value in [3, 2, 1]:
    linked_list.prepend(value)

print("Before delete:", linked_list.to_list())
linked_list.delete(2)
print("After delete:", linked_list.to_list())

Output:

Before delete: [1, 2, 3]
After delete: [1, 3]

prepend creates a new node whose next already points at the old head, then makes that new node the head — a single O(1) operation regardless of list length. Prepending 3, then 2, then 1 produces 1 -> 2 -> 3. Deleting 2 requires delete to walk the list tracking both previous and current; when it finds the node holding 2, it splices it out by pointing previous.next directly at current.next, leaving 1 -> 3.

Example 3: Reversing a Singly Linked List

Reversing a linked list in place is one of the most common interview questions, and it is a great way to see why saving a pointer before overwriting it matters.

from __future__ import annotations


class Node:
    def __init__(self, value: int, next: Node | None = None) -> None:
        self.value = value
        self.next = next


def build_list(values: list[int]) -> Node | None:
    head: Node | None = None
    tail: Node | None = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def reverse_list(head: Node | None) -> Node | None:
    previous = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous


def to_list(head: Node | None) -> list[int]:
    result = []
    current = head
    while current is not None:
        result.append(current.value)
        current = current.next
    return result


original_head = build_list([1, 2, 3, 4, 5])
print("Original:", to_list(original_head))

reversed_head = reverse_list(original_head)
print("Reversed:", to_list(reversed_head))

Output:

Original: [1, 2, 3, 4, 5]
Reversed: [5, 4, 3, 2, 1]

reverse_list walks the list once, and at each node it flips the direction of the next pointer to point backward instead of forward. It uses three variables: previous (the reversed portion built so far), current (the node being processed), and a temporary next_node that saves the rest of the original list before it gets overwritten. This is an O(n) time, O(1) extra space algorithm — no new nodes are allocated, only pointers are rewired.

How It Works Step by Step

Let’s trace reverse_list on the list 1 -> 2 -> 3 -> None in detail, since watching the three pointers move is the best way to internalize the algorithm.

Step	current (before)	next_node saved	current.next set to	previous (after)	current (after)
Start	—	—	—	None	1
1	1	2	None (was previous)	1	2
2	2	3	1 (was previous)	2	3
3	3	None	2 (was previous)	3	None

Once current becomes None, the loop condition current is not None is false, so the loop exits and the function returns previous, which is now node 3 — the new head. Following its next pointers gives 3 -> 2 -> 1 -> None, exactly the reversed list. The key insight is that next_node must be captured before current.next is reassigned, or the rest of the original chain would be lost — the next section shows exactly what happens when that step is skipped.

Common Mistakes

Mistake 1: Overwriting a pointer before saving what it pointed to

A very common bug when reversing (or otherwise rewiring) a linked list is forgetting to save current.next before overwriting it:

def reverse_list_broken(head):
    previous = None
    current = head
    while current is not None:
        current.next = previous
        previous = current
        current = current.next
    return previous

This looks almost identical to the correct version, but the last line, current = current.next, reads current.next after it was just overwritten to point at previous on the line above. So current becomes whatever previous was, not the next node in the original list. For a list of length 1 this happens to work by accident, but for longer lists the traversal effectively collapses after one or two iterations, and the rest of the original list becomes unreachable garbage. The fix, shown in Example 3’s reverse_list, is to capture next_node = current.next into its own variable before touching current.next at all, so the rest of the list is never lost.

def reverse_list(head):
    previous = None
    current = head
    while current is not None:
        next_node = current.next  # save the rest of the list first
        current.next = previous
        previous = current
        current = next_node
    return previous

Mistake 2: Forgetting to advance the traversal pointer

Another classic bug is forgetting to move current forward inside a while current is not None loop:

def contains_broken(head, target):
    current = head
    while current is not None:
        if current.value == target:
            return True
    return False

If target is never found, current never changes, so current is not None stays true forever — an infinite loop instead of a clean False. This is easy to miss because the code runs fine (and returns the right answer) whenever the target happens to be near the head, which can make the bug slip past a quick test. The fix is to always advance the pointer on every iteration, even in the failure branch:

from __future__ import annotations


class Node:
    def __init__(self, value: int, next: Node | None = None) -> None:
        self.value = value
        self.next = next


def contains(head: Node | None, target: int) -> bool:
    current = head
    while current is not None:
        if current.value == target:
            return True
        current = current.next
    return False


node_c = Node(30)
node_b = Node(20, node_c)
node_a = Node(10, node_b)

print(contains(node_a, 20))
print(contains(node_a, 99))

Output:

True
False

Here the list is 10 -> 20 -> 30. Searching for 20 finds it on the second node and returns True immediately. Searching for 99 walks all three nodes, never matches, current becomes None after node 30, the loop ends, and the function correctly returns False instead of hanging.

Best Practices

Operation	Python list (array-backed)	Singly Linked List
Index access x[i]	O(1)	O(n)
Insert/delete at front	O(n) — must shift elements	O(1)
Insert/delete at end	O(1) amortized	O(1) with tail pointer, else O(n)

• If you need frequent insertions or deletions at the front of a sequence, prefer a singly linked list (or collections.deque, which supports O(1) append/pop from both ends) over a Python list, which needs O(n) shifting to insert at index 0.
• If you need random access by index, or you mostly append to the end and rarely touch the front, a Python list is almost always the better and simpler choice — it has lower constant-factor overhead and cache-friendly contiguous memory.
• Maintain a cached tail pointer if your list needs frequent O(1) appends; otherwise every append degrades to an O(n) traversal, as seen in Example 1.
• When deleting a node, always keep a previous reference during traversal — a singly linked list cannot look backward, so without previous you cannot repoint the node before the one you want to remove.
• Never use a mutable default argument (like def build(values, node=Node(0))) when writing helper functions that build or accumulate linked structures; the default is created once and shared across every call, silently corrupting later calls. Use None and initialize inside the function body instead.
• For real-world production code, reach for collections.deque unless you specifically need custom per-node behavior (like O(1) insertion in the middle given a node reference) — it is implemented in C and outperforms a hand-rolled linked list for typical queue/stack use cases.

Practice Exercises

• Find the middle node. Write a function find_middle(head) that returns the middle node of a singly linked list in a single pass (hint: use two pointers, one moving twice as fast as the other — when the fast pointer reaches the end, the slow pointer is at the middle).
• Detect a cycle. Write has_cycle(head) that returns True if the list loops back on itself instead of ending in None (hint: Floyd’s cycle detection uses a slow and a fast pointer — if they ever meet, there is a cycle).
• Remove duplicates from an unsorted list. Write remove_duplicates(head) that removes duplicate values from a linked list while preserving the order of first occurrence, using a set to track values already seen. For input 1 -> 2 -> 1 -> 3 -> 2, the expected result is 1 -> 2 -> 3.

Summary

• A singly linked list is a chain of Node objects, each holding a value and a next pointer; the list only tracks the head.
• Access and search are O(n) because there is no random access — every lookup requires traversal from the head.
• Insertion and deletion at the head are O(1); insertion/deletion elsewhere (or by value) is O(n) because finding the position requires traversal.
• Space is O(n) for n nodes, with O(1) extra space for typical pointer-manipulation algorithms like reversal.
• Reversing a list is a classic O(n) time, O(1) space algorithm built on three pointers: previous, current, and a temporary next_node that must be saved before current.next is overwritten.
• Common bugs include overwriting a pointer before saving it (losing the rest of the list) and forgetting to advance the traversal pointer (causing an infinite loop).
• Prefer a linked list (or collections.deque) when front insertions/deletions dominate; prefer a Python list when index access dominates.