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)