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