Linked Lists

A linked list stores sequence order in references between separately allocated nodes rather than in contiguous slots.

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: "Node | None" = None

Variants and invariants

• Singly linked nodes point forward; the tail points to None.
• Doubly linked nodes point forward and backward; updates must preserve both directions.
• Circular lists connect the tail back to an endpoint and need an explicit termination rule for traversal.

Maintaining head, tail, and size fields improves some operations but creates more invariants that every mutation must preserve.

Cost model

Operation	Singly linked list
Access/search by position or value	$O(n)$
Insert after a known node	$O(1)$
Remove after a known predecessor	$O(1)$
Append with a maintained tail	$O(1)$
Remove tail	$O(n)$

The constant-time insertion/deletion claim excludes the cost of finding the node. A doubly linked list can remove a known node in $O(1)$ because it also knows the predecessor.

Trade-offs

Linked lists offer stable node identity and cheap local splicing, but pay for references, allocation, pointer chasing, and weaker cache locality. They are valuable inside structures such as intrusive lists and hash-table chains, but a dynamic array is usually the better default sequence.

Source

• Open Data Structures: Linked Lists