Singly Linked List in Python: Nodes, Traversal and Big-O

A singly linked list is the simplest structure that is not an array: a chain of small objects, each holding one value and the address of the next. You never get to see the whole chain at once; you hold the first node and follow links. That one constraint explains every cost in the structure, and most linked list interview questions are tricks for living with it.

The problem it solves

An array keeps its items side by side in one block of memory, which makes reading item k instant and makes inserting at the front expensive, since everything has to shift. A linked list makes the opposite trade. Nodes live anywhere in memory and are joined only by links, so adding a node at the front is one new object and one pointer, whatever the length, while reaching the 500th item means following 499 links.

That trade is useful wherever a program mostly works at the ends of a sequence or already holds a reference to the node it wants: queues, undo stacks, free lists inside allocators, and the recency list inside an LRU cache. In everyday Python a built-in list or deque is usually the better choice; in interviews, linked lists are popular because the pointer manipulation shows how carefully you reason.

The intuition

Four facts carry the structure:

1. A node is two fields: value and next. A fresh node's next is None.
2. The list is just its head. There is no container holding the nodes, no index and no length field unless you add one. The last node's next is None, and that is the only way to know the chain has ended.
3. Order lives in the links, not in memory. The nodes can be scattered anywhere; following next is the only way forward, so reaching item k costs k hops.
4. Variables are names for nodes. Two variables can point at the same node, and changing it through one is visible through the other. Losing every reference to a node loses the rest of the chain behind it.

From these follow the costs. Inserting or removing at the head is O(1). Appending at the tail is O(n) if you only have the head, and O(1) if you also keep a tail pointer. Searching, indexing and computing the length without a counter are all O(n). One-way links also mean a node cannot reach its predecessor, which is the problem a doubly linked list solves.

Watch it run

The animation builds the lesson's list. One node is two fields: a value and the address of the next node, and a fresh node links to nothing. head.next = Node(7): the first node now stores where the second one lives, and that address is the entire list structure. Two more nodes, two more links; the boxes are scattered across memory and only the links say what order they are in. You hold exactly one thing, the head, and reading head.value is instant, O(1). But there is no index. To reach node 1 you follow one link and land on 7; node 2 takes two links and lands on 15; node 3 takes three and lands on 2. The last node links to nothing: there is no length field anywhere, and the chain just stops linking. So node 500 costs 499 hops. The links are cheap, but reaching anything other than the head is O(n).

The code

The node, building a list from Python values, walking it, and reaching index k while counting hops. __slots__ keeps each node to exactly its two fields:

import random

class Node:
    __slots__ = ("value", "next")               # two fields, nothing else

    def __init__(self, value, next=None):
        self.value, self.next = value, next

def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)                    # each new node points at the old head
    return head

def to_list(head):
    out = []
    while head is not None:                     # None is the end of the chain
        out.append(head.value)
        head = head.next
    return out

def get(head, k):
    """The k-th value, and how many links were followed to reach it."""
    node, hops = head, 0
    while node is not None and hops < k:
        node, hops = node.next, hops + 1
    if node is None:
        raise IndexError(k)
    return node.value, hops

head = from_list([3, 7, 15, 2])
print(to_list(head), head.value, head.next.next.next.next)   # [3, 7, 15, 2] 3 None
print(get(head, 3))                                          # (2, 3)
alias = head.next                               # a second name for the node holding 7
alias.value = 70
print(to_list(head))                            # [3, 70, 15, 2]

Note that from_list builds back to front: pushing at the head is the cheap operation, so the last value goes in first. Changing the node through alias changed the list, because there was only ever one node. Next, the cost of appending when all you have is the head, and the fix:

def append_without_tail(head, value):
    hops = 0
    if head is None:
        return Node(value), hops
    node = head
    while node.next is not None:                # walk to the last node first
        node, hops = node.next, hops + 1
    node.next = Node(value)
    return head, hops

h, total = None, 0
for v in range(1000):
    h, hops = append_without_tail(h, v)
    total += hops
print(total)                                    # 498501

class LinkedList:
    """Head, tail and a size counter: O(1) at both ends that matter."""
    def __init__(self):
        self.head = self.tail = None
        self.size = 0

    def push_front(self, value):
        self.head = Node(value, self.head)
        if self.tail is None:
            self.tail = self.head
        self.size += 1

    def append(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node               # no walk: we already know the end
            self.tail = node
        self.size += 1

    def pop_front(self):
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return node.value

    def find(self, value):
        node, i = self.head, 0
        while node is not None:
            if node.value == value:
                return i
            node, i = node.next, i + 1
        return -1

    def __len__(self):
        return self.size

ll = LinkedList()
for v in (7, 15):
    ll.append(v)
ll.push_front(3)
print(to_list(ll.head), len(ll), ll.find(15), ll.find(9))   # [3, 7, 15] 3 2 -1

Building 1,000 items by walking to the end each time followed 498,501 links, the quadratic sum 0 + 1 + ... + 998. The class does the same in zero hops, and len is instant because the counter is updated on every change. Finally, 300 seeded runs of random pushes, appends, pops and searches are compared with a plain Python list after every operation, including the tail pointer and the hop count of get:

ok = True
for seed in range(300):
    rng = random.Random(seed)
    ll, ref = LinkedList(), []
    for _ in range(rng.randint(0, 200)):
        op, v = rng.random(), rng.randint(0, 9)
        if op < 0.35:
            ll.push_front(v); ref.insert(0, v)
        elif op < 0.7:
            ll.append(v); ref.append(v)
        elif op < 0.85 and ref:
            ok &= ll.pop_front() == ref.pop(0)
        else:
            ok &= ll.find(v) == (ref.index(v) if v in ref else -1)
        ok &= len(ll) == len(ref) and to_list(ll.head) == ref
        ok &= (ll.tail is None) == (not ref) and (not ref or ll.tail.value == ref[-1])
        if ref:
            k = rng.randrange(len(ref))
            ok &= get(ll.head, k) == (ref[k], k)
print(ok)                                       # True

The complexity

• Push or pop at the head: O(1).
• Append at the tail: O(1) with a tail pointer, O(n) without.
• Index, search, length without a counter: O(n).
• Removing the last node: O(n) even with a tail pointer, because the new tail's predecessor has to be found.
• Memory: one object per item, each with its own overhead, against one pointer per item in a Python list.

The Big-O cheat sheet lists these next to arrays and doubly linked lists.

Where it goes wrong

• Losing the head. Walking with head = head.next in the caller's only variable throws the front of the list away. Walk with a separate cursor.
• Forgetting None. Reading .next or .value on None is the classic crash; check before stepping.
• A stale tail. Removing the last node without updating tail leaves it pointing at a detached node, as pop_front above has to handle.
• Assuming fast iteration. Scattered nodes are slower to walk than an array of the same length, even though both are O(n), because each hop is a separate memory access.

When it shows up in interviews

Usually as the warm-up to a pointer problem: reverse a linked list, find the middle, detect a cycle, merge two sorted lists, or insert and delete at a position. All of them assume you can build a node, walk with a cursor and stop at None without thinking.

How to say it in an interview

"A singly linked list is a chain of nodes, each holding a value and a reference to the next, ending in None. I only hold the head, so pushing or popping at the front is O(1), but reaching index k follows k links, so indexing and search are O(n). If I need fast appends I keep a tail pointer, and if I need the length I keep a counter. I'd choose it when I mostly work at the ends or already hold the node; otherwise an array-backed list wins on memory and locality."