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")


@dataclass()
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.next)
                curr = curr.next

    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 self.next:
            p.next = LinkedList(x)
            p = p.next
        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 self.next:
            l = LinkedList(x, l)
        return l

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

    def __iadd__(self, other: LinkedList) -> LinkedList:
        l = self.last()
        l.next = 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

List of places where the US has been involved in regime change, with multiplicity

Accuracy vs Precision

Handy command line benchmarking tool

Stan Rogers

Ultimate Hot Couch Guy

Quote on Java Generics

The Programmer Tendency

Figure out undocumented JSON with gron

Mental Model of Dental Hygiene

Book Review: Swastika Night