Linked Lists in Python: Singly, Doubly, and Circular, From Scratch

A Python list keeps its elements in one contiguous block of memory, so reaching element 5,000 is a single multiplication and one memory read. A linked list keeps every element in its own object and reaches element 5,000 by following 5,000 references, one at a time. Put like that it sounds strictly worse, and for most day-to-day work in Python it is.

Learn it anyway, because a linked list is not really a list. It is the pattern nodes joined by references, and that pattern is the substrate for most of what comes later in this series. A binary search tree is a linked list that branches. A graph is nodes pointing at other nodes. An LRU cache is a hash table welded onto a doubly linked list. Once you can do pointer surgery on a straight line without losing half the data, the tree and graph code stops looking like magic.

So this post builds three of them from scratch — singly, doubly and circular — traces every reference assignment by hand, counts the work behind each complexity claim, and then says plainly why list and collections.deque still beat anything you write at the Python level.

The idea

A linked list is made of nodes. Each node holds two things: a value, and a reference to the next node. The list itself holds one reference, head, pointing at the first node. The final node's next is None, and that is the only thing that marks the end.

That is the whole structure. Two consequences follow, and between them they explain everything else.

There is no index arithmetic. A Python list can compute where element i lives, because the elements sit at consecutive addresses: the address is the base plus i times the pointer size. A linked list's nodes are wherever the allocator happened to put them, so the only way to find the third node is to ask the second, and the only way to find the second is to ask the first. Reaching position k costs k steps, always.

Nothing ever shifts. Inserting at the front of a Python list of 1,000,000 elements moves 1,000,000 pointers up one slot. Inserting at the front of a linked list creates one node, writes its next and moves head — two reference writes, however long the list is. Deleting is the same: if you already hold the node in front of the one you want gone, removing it is a single assignment.

That trade — pay for traversal, get free splicing — is the entire personality of the structure.

Watching it work

Start with an empty list and run five operations. Every reference write is shown, because the references are the algorithm.

push_front(7) — create a node holding 7 whose next is the old head, which is None. Point head at it. The list was empty, so tail points at it too. The list is 7.

push_front(3) — create a node holding 3 whose next is the current head, the node holding 7. Point head at the new node. tail does not move. The list is 3 -> 7.

push_back(12) — create a node holding 12 with next of None, set the current tail's next to it so the node holding 7 points at it, and move tail. The list is 3 -> 7 -> 12. Without the tail reference this would have meant walking from the head to find the last node.

remove(7) — this one needs a search. Start at the head with no predecessor. The head holds 3, so remember it as the predecessor and step forward. The second node holds 7 — a hit. Set the predecessor's next to the found node's next, so the node holding 3 now points at the node holding 12. The list is 3 -> 12. Two node visits to find it, one reference write to unlink it. The node holding 7 is now unreachable, and CPython's reference counting frees it immediately.

pop_front() — remember the head, move head to head.next, return the remembered value. The list is 12, and the call returned 3.

Only remove was expensive, and only because of the search. The unlink itself was one assignment.

The code

Here is the complete singly linked list. It keeps a tail reference so appending is cheap, and a _length counter so len() does not have to walk.

from typing import Iterator, Optional


class Node:
    """One link in the chain: a value, and a reference to whatever comes next."""

    # No per-instance __dict__. A linked list creates one object per element,
    # so the saving is paid n times over.
    __slots__ = ("value", "next")

    def __init__(self, value: int, next_node: Optional["Node"] = None) -> None:
        self.value = value
        self.next = next_node


class SinglyLinkedList:
    """A singly linked list that also remembers its tail.

    head points at the first node, tail at the last, and every node points
    forward only. The tail reference is what makes appending O(1) instead of
    a full walk from the head.
    """

    def __init__(self) -> None:
        self.head: Optional[Node] = None
        self.tail: Optional[Node] = None
        self._length = 0

    def push_front(self, value: int) -> None:
        """Insert at the head. O(1) — no other node is even read."""
        self.head = Node(value, self.head)
        if self.tail is None:  # the list was empty, so this node is both ends
            self.tail = self.head
        self._length += 1

    def push_back(self, value: int) -> None:
        """Append at the tail. O(1) only because the tail reference exists."""
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self._length += 1

    def pop_front(self) -> int:
        """Remove and return the first value. O(1)."""
        if self.head is None:
            raise IndexError("pop_front from an empty list")
        node = self.head
        self.head = node.next
        if self.head is None:  # the list just became empty
            self.tail = None
        self._length -= 1
        return node.value

    def remove(self, value: int) -> bool:
        """Delete the first node holding value. O(n): the search is the cost."""
        previous: Optional[Node] = None
        current = self.head
        while current is not None:
            if current.value == value:
                if previous is None:  # deleting the head moves head forward
                    self.head = current.next
                else:
                    previous.next = current.next
                if current is self.tail:  # deleting the tail moves tail back
                    self.tail = previous
                self._length -= 1
                return True
            previous, current = current, current.next
        return False

    def index_of(self, value: int) -> int:
        """First position holding value, or -1. O(n) — there is no shortcut."""
        for position, node_value in enumerate(self):
            if node_value == value:
                return position
        return -1

    def __len__(self) -> int:
        return self._length

    def __iter__(self) -> Iterator[int]:
        current = self.head
        while current is not None:
            yield current.value
            current = current.next

    def __repr__(self) -> str:
        if self.head is None:
            return "(empty)"
        return " -> ".join(str(value) for value in self) + " -> None"


numbers = SinglyLinkedList()
numbers.push_front(7)
numbers.push_front(3)
numbers.push_back(12)
print("list:        ", numbers, "| length", len(numbers))
print("index_of(12):", numbers.index_of(12))
print("remove(7):   ", numbers.remove(7), "->", numbers)
print("pop_front(): ", numbers.pop_front(), "->", numbers)
print("remove(99):  ", numbers.remove(99), "(nothing to delete)")
print("empty list:  ", SinglyLinkedList())

list:         3 -> 7 -> 12 -> None | length 3
index_of(12): 2
remove(7):    True -> 3 -> 12 -> None
pop_front():  3 -> 12 -> None
remove(99):   False (nothing to delete)
empty list:   (empty)

How the code maps to the idea

Three invariants hold after every operation, and essentially every linked list bug is one of them broken:

1. head is None exactly when tail is None, exactly when _length is 0.
2. tail.next is always None — the tail is genuinely the last node.
3. _length equals the number of nodes you can reach from head.

Read the methods again with those three in mind and each if explains itself.

push_front writes the new node's next before moving head. Node(value, self.head) builds the node pointing at the current first node, and only then is self.head reassigned. Do it the other way round and the old first node is already unreachable. That ordering trap is the most common linked list bug, and it reappears in reversal below.

remove carries a previous reference because a singly linked node cannot look backwards. To unlink a node, something has to be told to skip it, and the only thing that can be told is the node in front. That is exactly the limitation the doubly linked list removes later.

The edge cases all live in remove. Deleting the head means there is no predecessor, so head moves instead. Deleting the tail means tail must move back to previous. Deleting the only node hits both branches at once and correctly leaves head and tail None. A value that is not there falls out of the loop and returns False without touching anything.

__iter__ is a generator, which is what makes list(numbers), sum(numbers), 12 in numbers and a plain for loop work for free. __len__ returns a counter rather than walking, which is O(1) instead of O(n) — but a counter is a fourth thing that can go out of sync, which is why every mutating method adjusts it on every path.

Now measure the claim that indexing is expensive rather than asserting it:

def value_at(items: SinglyLinkedList, index: int) -> "tuple[int, int]":
    """Return (value, nodes visited). Reaching position k always costs k + 1."""
    current = items.head
    visited = 0
    while current is not None:
        visited += 1
        if visited - 1 == index:
            return current.value, visited
        current = current.next
    raise IndexError("index out of range")


hundred = SinglyLinkedList()
for value in range(100):
    hundred.push_back(value)

for index in [0, 1, 49, 99]:
    value, visited = value_at(hundred, index)
    print(f"index {index:>3} -> value {value:>3}, nodes visited {visited:>3}")

total = sum(value_at(hundred, index)[1] for index in range(100))
print("touching all 100 positions by index:", total, "node visits")

index   0 -> value   0, nodes visited   1
index   1 -> value   1, nodes visited   2
index  49 -> value  49, nodes visited  50
index  99 -> value  99, nodes visited 100
touching all 100 positions by index: 5050 node visits

That last number is the one to remember. Visiting all 100 positions by index costs 1 + 2 + … + 100 = 5,050 node visits, which is n(n + 1) / 2. A loop written as for each index, fetch that index turns an O(n) job into an O(n²) one; on a Python list the same loop is 100 visits. Iterate a linked list with for value in items, never by position.

Three operations worth knowing by heart

Reversing the list

Reversal is the classic linked list exercise because it forces you to confront the ordering trap: the moment you overwrite current.next, the rest of the list is gone. So you save it first. Three references move in lockstep — previous, the head of the reversed part built so far, starting at None; current, the node being flipped; and upcoming, a one-line memory of where current.next pointed before it was overwritten.

Trace it on 1 -> 2 -> 3. Before the loop, previous is None and current is the node holding 1.

• Flip 1. Save upcoming = node 2. Set 1.next = None. Move previous to node 1, current to node 2. The reversed part is 1; the untouched part is 2 -> 3.
• Flip 2. Save upcoming = node 3. Set 2.next = node 1. Move previous to node 2, current to node 3. The reversed part is 2 -> 1; the untouched part is 3.
• Flip 3. Save upcoming = None. Set 3.next = node 2. Move previous to node 3, current to None. The reversed part is 3 -> 2 -> 1, and nothing is left.

The loop ends because current is None, and previous is sitting on the last node it flipped — the new head.

def reverse(items: SinglyLinkedList) -> None:
    """Reverse in place by flipping every next reference. O(n) time, O(1) space."""
    previous: Optional[Node] = None
    current = items.head
    items.tail = current  # the old head is about to become the last node

    while current is not None:
        upcoming = current.next  # save it first: the next line destroys this link
        current.next = previous  # flip
        previous = current       # then shuffle both pointers one node along
        current = upcoming

    items.head = previous  # previous stopped on the final real node


counting = SinglyLinkedList()
for value in [1, 2, 3, 4]:
    counting.push_back(value)

print("before reverse:", counting)
reverse(counting)
print("after reverse: ", counting)
print("head is", counting.head.value, "and tail is", counting.tail.value)

before reverse: 1 -> 2 -> 3 -> 4 -> None
after reverse:  4 -> 3 -> 2 -> 1 -> None
head is 4 and tail is 1

Each node is visited exactly once and does a fixed amount of work, so reversal is O(n) time. It allocates nothing — three local references regardless of length — so it is O(1) space. Nothing moves in memory; only the arrows change direction.

Finding the middle in one pass

Send two references down the list. slow takes one step per iteration, fast takes two. When fast runs out of list, slow is halfway.

The invariant is simple: after k iterations, slow has moved k nodes and fast has moved 2k. For an odd length n = 2m + 1, fast reaches the last node after exactly m steps and stops, leaving slow on index m — the exact middle. For an even length n = 2m, fast steps off the end after m steps, leaving slow on index m, which is the upper of the two middle nodes.

def middle_value(items: SinglyLinkedList) -> Optional[int]:
    """The middle value in one pass: fast moves two nodes for every one of slow."""
    slow = fast = items.head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return None if slow is None else slow.value


for size in range(1, 6):
    sample = SinglyLinkedList()
    for value in range(1, size + 1):
        sample.push_back(value)
    print(f"{sample!r:<30} middle -> {middle_value(sample)}")

1 -> None                      middle -> 1
1 -> 2 -> None                 middle -> 2
1 -> 2 -> 3 -> None            middle -> 2
1 -> 2 -> 3 -> 4 -> None       middle -> 3
1 -> 2 -> 3 -> 4 -> 5 -> None  middle -> 3

Both guards in the while are load-bearing. fast is not None catches even lengths, where fast lands exactly on None. fast.next is not None catches odd lengths, where fast lands on the last node and fast.next.next would raise AttributeError. Drop either and the function crashes on half of all inputs.

You could instead call len() and walk half the list, but that is two passes and needs a length you may not have. This is the two pointers technique applied to a structure with no indices.

Detecting a cycle

If some node's next points back at an earlier node, a walk from the head never terminates. That is not hypothetical: it is what a mis-written splice produces, and it hangs your program rather than raising anything. __repr__ above would loop forever too, so you cannot print your way out of it.

Floyd's cycle detection finds it with the same two pointers, in O(1) space. Run slow at one node per step and fast at two. If the list ends, fast falls off and there is no cycle. If there is a cycle, both pointers eventually enter it, and then fast gains exactly one position on slow every step. A gap that shrinks by one each step and can never exceed the loop length L must reach zero within L steps, so a collision is guaranteed.

Finding where the loop starts takes a second phase, and the arithmetic is worth seeing. Let mu be the number of nodes before the loop and L the loop length. When the pointers meet, slow has travelled d steps and fast 2d. Both are at the same place inside the loop, so d - mu and 2d - mu are equal modulo L, which means d is a multiple of L. Now walk one reference from the head and one from the meeting point, one step each. After mu steps the first is at the loop entry, and the second has travelled d + mu from the head, which is mu modulo L — also the entry. They meet exactly at the start of the loop.

def has_cycle(head: Optional[Node]) -> bool:
    """Floyd's tortoise and hare. O(n) time, O(1) space."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # identity, not equality: equal values are not one node
            return True
    return False


def cycle_start(head: Optional[Node]) -> Optional[Node]:
    """The first node inside the loop, or None. Phase two of Floyd's algorithm."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            walker = head
            while walker is not slow:  # both now move one step at a time
                walker = walker.next
                slow = slow.next
            return walker
    return None


looped = SinglyLinkedList()
for value in [1, 2, 3, 4, 5, 6]:
    looped.push_back(value)
looped.tail.next = looped.head.next.next  # 6 now points back at 3

straight = SinglyLinkedList()
for value in [1, 2, 3]:
    straight.push_back(value)

print("has_cycle(looped):  ", has_cycle(looped.head))
print("cycle starts at:    ", cycle_start(looped.head).value)
print("has_cycle(straight):", has_cycle(straight.head))
print("has_cycle(empty):   ", has_cycle(None))

has_cycle(looped):   True
cycle starts at:     3
has_cycle(straight): False
has_cycle(empty):    False

Check the arithmetic against that run. Here mu is 2 and L is 4. The pointers meet at the node holding 5 after 4 steps, and 4 is indeed a multiple of L. Walking 2 steps from the head lands on 3; walking 2 steps from node 5 goes 6 then 3. Same node.

Note slow is fast, not slow == fast. Two different nodes can hold equal values, and the moment someone adds an __eq__ that compares them, the equality version reports cycles that do not exist. Compare nodes by identity, always.

Doubly linked lists

Give every node a prev reference as well and one whole class of problem disappears: you never need to hunt for a node's predecessor, because the node knows it itself.

That buys the operation the singly linked list cannot do. If somebody hands you a node — not a value, not a position, the node — you can remove it in constant time. Two reference writes join its neighbours to each other. No search, no traversal, no dependence on length.

class DoublyNode:
    """A node that knows both of its neighbours."""

    __slots__ = ("value", "prev", "next")

    def __init__(self, value: int) -> None:
        self.value = value
        self.prev: Optional["DoublyNode"] = None
        self.next: Optional["DoublyNode"] = None


class DoublyLinkedList:
    """Doubly linked list: O(1) at both ends, and O(1) removal of a known node."""

    def __init__(self) -> None:
        self.head: Optional[DoublyNode] = None
        self.tail: Optional[DoublyNode] = None
        self._length = 0

    def push_back(self, value: int) -> DoublyNode:
        """Append, and hand the node back so the caller can unlink it later."""
        node = DoublyNode(value)
        node.prev = self.tail
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self._length += 1
        return node

    def unlink(self, node: DoublyNode) -> None:
        """Remove a node you already hold. O(1): no search, no traversal."""
        if node.prev is None:  # node was the head
            self.head = node.next
        else:
            node.prev.next = node.next

        if node.next is None:  # node was the tail
            self.tail = node.prev
        else:
            node.next.prev = node.prev

        node.prev = node.next = None  # detach, so a stale reference cannot walk back in
        self._length -= 1

    def forwards(self) -> "list[int]":
        values, current = [], self.head
        while current is not None:
            values.append(current.value)
            current = current.next
        return values

    def backwards(self) -> "list[int]":
        values, current = [], self.tail
        while current is not None:
            values.append(current.value)
            current = current.prev
        return values

    def __len__(self) -> int:
        return self._length


recent = DoublyLinkedList()
handles = [recent.push_back(value) for value in [10, 20, 30, 40]]
print("forwards: ", recent.forwards())
print("backwards:", recent.backwards())

recent.unlink(handles[1])  # drop 20 without searching for it
print("unlink(20):", recent.forwards(), "| length", len(recent))
recent.unlink(handles[3])  # drop the tail
print("unlink(40):", recent.forwards(), "| tail is", recent.tail.value)

forwards:  [10, 20, 30, 40]
backwards: [40, 30, 20, 10]
unlink(20): [10, 30, 40] | length 3
unlink(40): [10, 30] | tail is 30

push_back returning the node is the important design decision here, not an afterthought. A doubly linked list whose API only takes values is just a slower singly linked list; the O(1) removal exists only if the caller can hold a handle. That is exactly how an LRU cache works: a dictionary maps each key to its node, so a cache hit is a dictionary lookup, an unlink and a re-insert at the front, all O(1).

The costs are real. Every node carries an extra reference, so memory per element goes up, and every structural change writes twice as many references, so there is twice as much to get wrong. Production implementations dodge most of the None branches with a sentinel: one permanent dummy node whose next is the first real node and whose prev is the last, making the list circular and deleting every empty-versus-nonempty special case. CPython's pure-Python functools.lru_cache does precisely this with a root link.

Circular linked lists

Point the last node's next at the first and the list becomes a ring. There is no end, so there is no None to check — and no natural stopping condition either, which is the thing that bites people. Every traversal needs an explicit "stop when you are back where you started".

A ring needs only one reference to be fully usable. Keep tail, and the head is always tail.next, so both ends are O(1) away.

class CircularLinkedList:
    """A ring. One reference is enough, because the head is always tail.next."""

    def __init__(self) -> None:
        self.tail: Optional[Node] = None
        self._length = 0

    def push_back(self, value: int) -> None:
        """Insert after the tail, keeping the ring closed. O(1)."""
        node = Node(value)
        if self.tail is None:
            node.next = node  # a one-node ring points at itself
        else:
            node.next = self.tail.next  # new node points at the head
            self.tail.next = node
        self.tail = node
        self._length += 1

    def take_turn(self) -> int:
        """Return the front value and send it to the back. Round-robin in O(1)."""
        if self.tail is None:
            raise IndexError("take_turn on an empty ring")
        self.tail = self.tail.next  # the old head becomes the new tail
        return self.tail.value

    def to_list(self) -> "list[int]":
        """Walk once round, stopping when the head comes back into view."""
        if self.tail is None:
            return []
        head = self.tail.next
        values, current = [], head
        while True:
            values.append(current.value)
            current = current.next
            if current is head:
                return values


ring = CircularLinkedList()
for value in [1, 2, 3]:
    ring.push_back(value)

print("ring:          ", ring.to_list())
print("seven turns:   ", [ring.take_turn() for _ in range(7)])
print("ring afterwards:", ring.to_list())

ring:           [1, 2, 3]
seven turns:    [1, 2, 3, 1, 2, 3, 1]
ring afterwards: [2, 3, 1]

take_turn is round-robin scheduling in one line: hand out the front, move it to the back, never allocate. Seven turns over three participants gives 1, 2, 3, 1, 2, 3, 1 and leaves the ring rotated by one. Note that a ring is the same shape Floyd's algorithm hunts for — the difference is intent, one being a loop you built and the other a bug you did not.

Complexity

Every bound below comes from counting node visits and reference writes.

Space is O(n), but the constant is bad. On the 64-bit CPython 3.9 build used to run this post's code, sys.getsizeof reports 48 bytes for a two-slot Node object, and 152 bytes for the same class without __slots__ — 48 for the object plus 104 for its instance dictionary. A Python list stores 8 bytes per element in its pointer array. The node chain therefore costs six times the memory of a list before you count the values at all, or nineteen times if you forget __slots__.

The bigger cost is not in the O. A list's pointer array is contiguous, so the CPU prefetches the next cache line while working on the current one. A node chain is a pointer chase: the address of the next node is unknown until the current one has been loaded, which defeats prefetching and turns a long walk into a run of cache misses. Every current.next is also an interpreted attribute lookup, while list iteration runs in C. Two structures can share the same O(n) and still differ by a factor of fifty in wall-clock time — Big O notation has the full treatment of what the letters do and do not promise.

When to use it, and when not to

In Python, do not write your own unless you need node handles. That is the honest headline. list covers sequences, and it is a dynamic array in C with O(1) indexing and amortised O(1) append. collections.deque covers the both-ends case. Between them they eat almost every use a textbook gives for a linked list.

from collections import deque

recent_pages = deque([10, 20, 30], maxlen=3)
recent_pages.appendleft(5)  # O(1) at the front; list.insert(0, x) is O(n)
print("after appendleft:", list(recent_pages))
recent_pages.append(40)     # maxlen makes it a ring buffer: the far end falls off
print("after append:    ", list(recent_pages))
recent_pages.rotate(1)      # a circular list, in one call
print("after rotate(1): ", list(recent_pages))

after appendleft: [5, 10, 20]
after append:     [10, 20, 40]
after rotate(1):  [40, 10, 20]

Those three lines cover the head insert, the ring buffer and the rotation that the classes above spent a couple of hundred lines providing, and they run in C.

Reach for a hand-written linked list when you need to hold a reference to an element and splice it out in constant time later — the LRU cache pattern, the intrusive-list pattern used throughout operating system kernels, the free-list pattern used by allocators. It is also the answer when you need stable identity: a node's address never changes as the list grows, whereas a dynamic array reallocates and every element moves.

Do not reach for it when you index, sort, slice or scan repeatedly. Sorting a linked list means merge sort, because quick sort's partitioning wants random access — and even then, copying to a list, calling sorted() and rebuilding is usually faster in Python. Do not use one as a stack or a queue either: stacks are a plain list, and queues and deques are collections.deque.

Where it shows up in the real world

collections.deque is implemented in CPython as a doubly linked list of fixed-size blocks, each holding 64 element pointers. That hybrid is why appendleft and popleft are O(1) while indexing into the middle is O(n) — you follow block links to get there. It is the linked structure most Python programmers use daily without noticing.

functools.lru_cache keeps its entries in a circular doubly linked list with a sentinel root, alongside a dictionary from key to link. A cache hit unlinks the entry and relinks it next to the root, a constant number of reference writes no matter how large the cache is. The eviction victim is simply the link on the other side of the root.

collections.OrderedDict maintains a doubly linked list of its keys. That list, not the dictionary, is what makes move_to_end O(1).

The Linux kernel builds nearly all of its bookkeeping on struct list_head, an intrusive circular doubly linked list whose API lives in include/linux/list.h. Process lists, page LRU lists and driver registries all use it, for precisely the O(1) unlink: given a pointer to any object, the kernel removes it from whatever list it is on without a search. Memory allocators do the same with free blocks — glibc's malloc holds free chunks in doubly linked bins.

One correction to the textbooks, though. Adjacency "lists" in graph code, undo stacks and browser history are almost always dynamic arrays in real implementations. The name stuck; the structure did not.

Common mistakes

Overwriting a link before you save it. current.next = previous before reading current.next orphans the entire remainder of the list, and there is no way back. Save upcoming first, every time.

Forgetting tail on delete. Remove the last node without moving tail back and tail still points at a detached node. The list looks fine until the next push_back appends to something no longer in the list, and the new value vanishes.

Using == instead of is for node comparison. Cycle detection is about identity. The moment a node type grows an __eq__ that compares values, an equality test reports a cycle between two distinct nodes holding the same number.

Dropping one of the two guards in the fast-pointer loop. while fast is not None and fast.next is not None needs both. Without the first, even-length lists raise AttributeError on None.next; without the second, odd-length lists raise it on fast.next.next.

Indexing in a loop. for i in range(len(items)): value_at(items, i) looks O(n) and is O(n²), as the 5,050 count showed. Iterate the nodes, not the positions.

Traversing a circular list with while current is not None. There is no None, so the loop never ends. A ring needs the "back where I started" test, and so does anything that prints or measures one.

Practice

1. Add an at(index) method to SinglyLinkedList that raises IndexError for an out-of-range index, and confirm it handles the empty list.
2. Write push_back without a tail reference, then count the node visits for 1,000 appends and show it comes to 499,500.
3. Merge two already-sorted singly linked lists into one sorted list by relinking the existing nodes, allocating no new ones.
4. Decide whether a list reads the same forwards and backwards using O(1) extra space: find the middle, reverse the second half, compare, then reverse it back.
5. Remove the nth node from the end in a single pass, by starting one reference n nodes ahead of the other and moving both until the leader falls off.

Summary

A linked list trades away random access to buy constant-time splicing. In Python that trade rarely pays off on its own — list and collections.deque are faster, smaller and already written — but the structure underneath it is the one every tree, graph and cache in this series is built from. Learn the three-pointer reversal, the slow-and-fast pair, and the habit of naming your invariants before you start rewriting references.

Keep reading

• Arrays and Dynamic Arrays — what a Python list actually is, and why it usually wins this comparison.
• Queues and Deques — collections.deque, the production-grade linked structure you should reach for first.
• Binary Search Trees — the same nodes and references, but each node points at two children instead of one.
• The Two Pointers Technique — the slow-and-fast idea generalised to arrays and strings.