Fun with Python Iterators: Linked Lists Made Easy

This requires Python 3.7+, since I use the handy dataclasses library.

I finally bothered to sit down and figure out how to properly write iterators in Python, and it’s made implementing magic methods fun. I timed myself and all of these methods were written in 17 minutes.

By moving the iteration into syntactic sugar, we save ourselves a lot of pain and make the code a helluva lot clearer than the first time I wrote a linked list.

Notably, the ugly return tuple of value, current node, next node makes methods like __add__ and last easy to implement.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from __future__ import annotations

from copy import deepcopy
from dataclasses import dataclass
from operator import eq, ge, gt, le, lt, ne
from typing import Callable, Dict, TypeVar

T = TypeVar("T")

class LinkedList:
    val: T
    next: LinkedList = None

    def __iter__(self):
        return self._next()

    def __next__(self):
        yield from self._next()

    def _next(self):
        if self is not None:
            curr = self
            while curr is not None:
                # this ugly return makes a lot of manipulation easier
                yield (curr.val, curr,
                curr =

    def __getitem__(self, idx: int) -> T:
        for i, (x, curr, tail) in enumerate(self):
            if i == idx:
                return x
        raise IndexError

    def __len__(self):
        return sum(1 for _ in self)

    def __contains__(self, x: T) -> bool:
        return any(x == y for y, *_ in self)

    def __deepcopy__(self, memodict: Dict = {}):
        l = LinkedList(self[0])
        p = l
        for x, *_ in
   = LinkedList(x)
            p =
        return l

    def _cmp(self, other, cmp: Callable, *, how_many: Callable = all):
        return how_many(cmp(x, y) for (x, *_), (y, *_) in zip(self, other))

    def __eq__(self, other: LinkedList) -> bool:
        return self._cmp(other, eq)

    def __ne__(self, other: LinkedList) -> bool:
        return self._cmp(other, ne, how_many=any)

    def __gt__(self, other: LinkedList) -> bool:
        return self._cmp(other, gt)

    def __ge__(self, other: LinkedList) -> bool:
        return self._cmp(other, ge)

    def __le__(self, other: LinkedList) -> bool:
        return self._cmp(other, le)

    def __lt__(self, other: LinkedList) -> bool:
        return self._cmp(other, lt)

    def __bool__(self):
        return self is not None

    def __reversed__(self):
        """Not lazy and not in place."""
        if self is None:
            return None
        l = LinkedList(self[0])
        for x, *_ in
            l = LinkedList(x, l)
        return l

    def __add__(self, other: LinkedList) -> LinkedList:
        head = deepcopy(self)
        l = head
        c = l.last() = deepcopy(other)
        return head

    def __iadd__(self, other: LinkedList) -> LinkedList:
        l = self.last() = other
        return self

    def __str__(self) -> str:
        return " -> ".join(str(x) for x, *_ in self)

    def last(self) -> LinkedList:
        # returns last node in list
        for x, curr, tail in self:
            if tail is None:
                return curr

    def __repr__(self) -> str:
        return str(self)

Related Posts

Use of emphasis in speech

Generating a lot of language data with a theorem prover

"Litany Against Fear" in Present Tense

When it's time to party we will party hard

these are people who died

divine carrot

the frog

what it’s like to get nail phenolization

Why 0 to the power of 0 is 1

Lines and Points are Circles