Singly Linked List

A singly-linked list is a chain of nodes, each holding a value and a pointer to the next node. Insert/delete at the head is O(1); access by index is O(n) because you must walk from the head.

Complexity

Average				Worst				Space
Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion	Worst
`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`

How it works

Each node = (value, next_pointer). The list owns a head pointer. To insert at the head: new_node.next = head; head = new_node. To delete the head: head = head.next. Insert/delete at the tail or in the middle requires first walking to that position — O(n).

Python implementation

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt


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

    def push_front(self, val):           # O(1)
        self.head = Node(val, self.head)

    def pop_front(self):                 # O(1)
        if self.head is None:
            raise IndexError("pop from empty list")
        val = self.head.val
        self.head = self.head.next
        return val

    def find(self, val):                 # O(n)
        node = self.head
        while node:
            if node.val == val:
                return node
            node = node.next
        return None

    def __iter__(self):
        node = self.head
        while node:
            yield node.val
            node = node.next


ll = SinglyLinkedList()
ll.push_front(3); ll.push_front(2); ll.push_front(1)
print(list(ll))            # [1, 2, 3]
ll.pop_front()
print(list(ll))            # [2, 3]

Trade-offs

O(1) insert/delete at the head; useful as a stack or for splice operations.
O(n) random access — no index lookup.
Per-node overhead (pointer + object header) makes linked lists much slower than arrays in cache.
In Python, a list is almost always the better choice; reach for a linked list only when you need O(1) splice or are implementing another structure.

← Back to Algorithms

5. Operations Step by Step

Every operation on a singly linked list is a matter of rewiring next pointers. Inserting after a known node touches two pointers and is O(1). Inserting at the head is the same, with the head reference playing the role of the previous node. Deleting the node after a known node sets prev.next = prev.next.next. What is not O(1) is finding the place to operate: locating index i, a value, or the node before a given node requires walking from the head. That is why the complexity table lists insertion and deletion as O(1) only when the position is already known.

A tail pointer makes appends O(1) and turns the list into an efficient queue, but deleting the tail is still O(n) because there is no back pointer to the second-to-last node. That limitation is the main reason doubly linked lists exist.

6. Reversal and Two-Pointer Techniques

Reversal is the classic linked-list exercise: walk the list once, flipping each next pointer to point backwards, keeping three references so nothing is lost. Many other problems use two pointers moving at different speeds. A fast pointer moving two steps per iteration and a slow pointer moving one find the middle node when the fast pointer reaches the end, and detect a cycle if the two ever meet (Floyd's algorithm). A pointer started k nodes ahead finds the k-th node from the end in one pass.

A sentinel, or dummy head, node simplifies many of these algorithms. By starting the list with a node that holds no value, insertion and deletion at the front become the same code as anywhere else, because there is always a previous node. Merging two sorted lists, removing all nodes with a given value, and partitioning a list around a pivot are all shorter and less error-prone with a dummy head that is discarded at the end.

7. Worked Example

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def from_list(xs):
    head = None
    for x in reversed(xs):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val); head = head.next
    return out

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

h = from_list([3, 7, 9, 12])
print(to_list(reverse(h)))        # [12, 9, 7, 3]
print(middle(from_list([1, 2, 3, 4, 5])).val)   # 3

__slots__ removes the per-instance dictionary, which noticeably reduces memory for lists with many nodes.

8. Linked List vs Array

Operation	Singly linked list	Dynamic array (Python list)
Index access	O(n)	O(1)
Insert / delete at front	O(1)	O(n)
Append at end	O(1) with tail pointer	O(1) amortized
Insert after known node	O(1)	O(n)
Memory per element	Value + pointer + object header	One pointer
Cache locality	Poor	Good

In Python, a list or collections.deque is almost always faster in practice. Linked lists matter for understanding, for interview problems, and in languages or systems where nodes are embedded in other structures, such as kernel lists, LRU caches, and hash table chaining.

9. Pitfalls

Forgetting to handle the empty list and the single-node list.
Losing the rest of the list by overwriting next before saving it.
Not updating the head or tail reference when the first or last node changes.
Recursive traversals hit Python's recursion limit on long lists; iterate instead.

When testing list code, draw the pointers for a three-node list on paper and check each assignment; most bugs show up as a lost or cyclic link.

Doubly Linked List, Skip List
Stack, Queue, Array