Barebones but Sequence compliant Singly Linked List

Question

I haven't written a linked list from scratch in a couple years, so I decided to take a stab at it again. After working on it on and off for a little over a week, I'm finally happy with it.

It implements Sequence. Since it overrides each method, having it extend an ABC wasn't really necessary, but I thought that it would be a good indicator of what the class can be used for.

This is a plain, basic LL. The only reference I'm holding is of the head, so most operations on it are inefficient.

It's composed of two parts: A basic Node class that I delegate a lot of the work to, and a LinkedList wrapper that handles size and maintains the node structure.

Example of use:

>>> ll = LinkedList.from_iterable(range(20))
>>> ll
<0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19>

>>> del ll[5]
ll
<0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19>

ll[15 : 0 : -3]
<16, 13, 10, 7, 3>

>>> ll.index(14)
13

The main things that I want commented on:

• Node.from_iterable has an awkward bit. Right now, I'm checking inside the loop if cur has been initialized yet each iteration, just to handle the very first element. I tried calling next on iterable to pre-initialize head before the loop, but then if iterable is empty I'll get a StopIteration thrown. I tried giving next a sentinel value, but then I needed to check for it later... It ended up getting messier than what I'm already doing, so I left it as-is.

• remove is ugly. In most other methods I was able to fall-back on some lower-level constructs to do most of the work. remove though proved to be kind of a corner case that doesn't share a lot with other functionality.

Or anything else that is worth mentioning. I think this is the first time I've gone all out in creating a structure like this in Python, so I welcome any feedback.

from __future__ import annotations
from typing import Generic, TypeVar, Optional, Iterator, Iterable, Union, Sequence, Tuple
from dataclasses import dataclass
from itertools import islice
from functools import reduce


T = TypeVar("T")


@dataclass
class _Node(Generic[T]):
    data: T
    tail: Optional[_Node[T]] = None

    def insert_after(self, new_data: T) -> None:
        old_tail = self.tail
        self.tail = _Node(new_data, old_tail)

    def remove_next(self) -> None:
        if self.tail:
            self.tail = self.tail.tail

    def __iter__(self) -> Iterable[_Node[T]]:
        cur = self

        while cur:
            yield cur
            cur = cur.tail

    def find_last(self) -> _Node[T]:
        cur = self  # Isn't actually necessary. self will never be an empty iterable

        for node in self:
            cur = node

        return cur

    def copy(self) -> Tuple[_Node[T], _Node[T], int]:
        """Produces a copy of the given node (including a shallow copy of the entire tail).
        Returns a tuple of (copy_head, copy_last_node, copy_list_length)."""
        return _Node.from_iterable(node.data for node in self)

    @staticmethod
    def from_iterable(iterable: Iterable[T]) -> Tuple[_Node[T], _Node[T], int]:
        """Constructs a node-list from an iterable.
        Returns a tuple of (head, last_node, list_length). head and last_node will be None if iterable is empty."""
        head = None
        cur = None
        count = 0

        for t in iterable:
            new_node = _Node(t)

            # TODO: Eww. How to cleanly pre-initialize?
            # TODO: Moving this out of the loop causes issues with next throwing when iterable is empty.
            if cur:
                cur.tail = new_node
                cur = cur.tail

            else:
                head = new_node
                cur = head

            count += 1

        return head, cur, count

    def mul_node(self, n: int) -> Optional[_Node[T]]:
        """__mul__, but will return None if n is <= 0."""
        if n <= 0:
            return None

        else:
            initial_head, cur_last, _ = self.copy()

            for _ in range(n - 1):
                copy_head, copy_tail, _ = self.copy()
                cur_last.tail = copy_head
                cur_last = copy_tail

            return initial_head

    def __repr__(self) -> str:
        return f"<{'-'.join(str(node.data) for node in self)}>"


def _wrap_negative_index(i: int, length: int) -> int:
    """Wraps negative indices to the back of the list."""
    return i if i >= 0 else length + i


class LinkedList(Sequence[T]):
    def __init__(self):
        self._head: Optional[_Node] = None
        self._size: int = 0

    def _node_iter(self) -> Iterable[_Node[T]]:
        if self._head:
            return self._head

        else:
            return []

    def _find_last_node(self) -> Optional[_Node]:
        return self._head.find_last() if self._head else None

    def _pop_head(self) -> _Node[T]:
        """Helper that replaces and returns the head. DOES NOT MODIFY THE SIZE!"""
        popped = self._head
        self._head = self._head.tail

        return popped

    def prepend(self, elem: T) -> None:
        self.insert(0, elem)

    def append(self, elem: T) -> None:
        self.insert(len(self), elem)

    def insert(self, key: int, elem: T) -> None:
        if not self or key <= 0:
            new_head = _Node(elem, self._head)
            self._head = new_head

        else:
            node_before = self._get_ith_node(min(key - 1, len(self) - 1))
            node_before.insert_after(elem)

        self._size += 1

    def count(self, elem: T) -> int:
        return reduce(lambda found, t: found + 1 if elem == t else found,
                      self,
                      0)

    def index(self, elem: T, start: int = 0, stop: Optional[int] = None) -> int:
        self._assert_inbounds(start)
        checked_stop = stop if stop is not None else len(self) - 1

        indexed_search_slice = islice(enumerate(self), start, checked_stop)

        try:
            return next(i for i, t in indexed_search_slice if t == elem)

        except StopIteration:  # If the generator is empty, next will raise a StopIteration
            raise ValueError(f"{elem} is not in the list in the range specified.")

    def extend(self, iterable: Iterable[T]) -> None:
        new_nodes, _, count = _Node.from_iterable(iterable)

        if last_node := self._find_last_node():
            last_node.tail = new_nodes

        else:
            self._head = new_nodes

        self._size += count

    def pop(self, key: Optional[int] = None) -> T:
        key = _wrap_negative_index(key, len(self)) if key is not None else len(self) - 1
        self._assert_inbounds(key)

        if key == 0:
            popped = self._pop_head()

        else:
            node_before = self._get_ith_node(key - 1)
            popped = node_before.tail
            node_before.remove_next()

        self._size -= 1

        return popped.data

    # TODO: Neaten up
    def remove(self, elem: T):  # TODO: Eww
        prev_node = None
        for node in self._node_iter():
            if node.data == elem:
                if prev_node:
                    prev_node.remove_next()

                else:
                    self._pop_head()

                self._size -= 1
                return

            prev_node = node

        raise ValueError(f"{elem} not in list.")

    def reverse(self):
        self._head, *_ = _Node.from_iterable(reversed(self))

    def __bool__(self):
        return bool(self._head)

    def __iter__(self):
        return (node.data for node in self._node_iter())

    def __len__(self):
        return self._size

    def _assert_inbounds(self, *wrapped_indices: int):
        for index in wrapped_indices:
            if not 0 <= index < len(self):
                raise IndexError(f"Index {index} out of bounds for list of size {len(self)}.")

    def _get_ith_node(self, i: int) -> _Node[T]:
        self._assert_inbounds(i)

        return next(islice(self._head, i, None))

    def __getitem__(self, key: Union[int, slice]) -> Union[T, LinkedList[T]]:
        if isinstance(key, int):
            node = self._get_ith_node(_wrap_negative_index(key, len(self)))
            return node.data

        else:
            if key.step > 0:
                ll_slice = islice(self, key.start, key.stop, key.step)  # FIXME: Need to handle a negative step
                return LinkedList.from_iterable(ll_slice)

            else:
                surrogate = list(self)
                start = len(self) - 1 if key.start is None else key.start
                stop = -1 if key.stop is None else key.stop
                indices = range(start, stop, key.step)

                return LinkedList.from_iterable(surrogate[i] for i in indices)

    def __setitem__(self, key: int, elem: T) -> None:
        # TODO: Allow for slice assignment?
        node = self._get_ith_node(_wrap_negative_index(key, len(self)))
        node.data = elem

    def __delitem__(self, key: int) -> None:
        self.pop(_wrap_negative_index(key, len(self)))

    def __contains__(self, elem: T) -> bool:
        return any(t == elem for t in self)

    def __repr__(self) -> str:
        return f"<{', '.join(str(t) for t in self)}>"

    def __reversed__(self) -> Iterator[T]:
        return reversed(list(self))  # I think this is the best option for a simple SL LL

    def __add__(self, iterable: Iterable[T]) -> LinkedList[T]:
        copy_head, copy_end, copy_count = _Node.from_iterable(self)
        added_head, added_end, added_count = _Node.from_iterable(iterable)

        copy_end.tail = added_head
        return LinkedList._from_existing_nodes(copy_head, copy_count + added_count)

    def __iadd__(self, iterable: Iterable[T]) -> LinkedList[T]:
        self.extend(iterable)
        return self

    def __mul__(self, n: int) -> LinkedList[T]:
        if not self or n <= 0:
            return LinkedList.from_iterable([])

        else:
            return LinkedList._from_existing_nodes(self._head.mul_node(n), max(0, len(self) * n))

    def __imul__(self, n: int) -> LinkedList[T]:
        if self._head:
            self._head = self._head.mul_node(n)
            self._size *= max(n, 0)

        return self

    @staticmethod
    def _from_existing_nodes(head: _Node[T], node_count: int) -> LinkedList[T]:
        l_list = LinkedList()
        l_list._size = node_count
        l_list._head = head

        return l_list

    @staticmethod
    def from_iterable(iterable: Iterable[T]) -> LinkedList[T]:
        head, _, count = _Node.from_iterable(iterable)
        return LinkedList._from_existing_nodes(head, count)

Answer 1

Using a dummy node is one way to simplify the logic in _Node.from_iterable and LinkedList.remove. We incur a constant-space cost of one extra node, and in return we don't need to write a separate branch of logic to handle the empty/null head case:

@dataclass
class _DummyNode(_Node[T]):
    data: Optional[T] = None
    tail: Optional[_Node[T]] = None

@staticmethod
def from_iterable(iterable: Iterable[T]) -> Tuple[Optional[_Node[T]], Optional[_Node[T]], int]:
    """Constructs a node-list from an iterable.
    Returns a tuple of (head, last_node, list_length). head and last_node will be None if iterable is empty."""
    dummy_head: _DummyNode[T] = _DummyNode()
    cur: _Node[T] = dummy_head
    count = 0

    for t in iterable:
        cur.tail = _Node(t)
        cur = cur.tail
        count += 1

    return dummy_head.tail, None if count == 0 else cur, count

class LinkedList(Sequence[T]):
    def __init__(self):
        self._dummy_head: _DummyNode[T] = _DummyNode()
        self._size: int = 0

    def _all_node_iter(self) -> Iterable[_Node[T]]:
        """Iterable over all nodes, including the dummy head node"""
        yield self._dummy_head
        yield from self._node_iter()

    def _node_iter(self) -> Iterable[_Node[T]]:
        """Iterable over only the real nodes"""
        cur = self._dummy_head.tail
        while cur:
            yield cur
            cur = cur.tail

    # [...]

    def remove(self, elem: T) -> None:
        for prev, cur in zip(self._all_node_iter(), self._node_iter()):
            if cur.data == elem:
                prev.remove_next()
                self._size -=1
                return
        raise ValueError(f"{elem} not in list.")

    # [...]

This does involve changing the design of LinkedList to use _dummy_head instead of _head, but other methods like insert can be refactored with simpler logic in a similar way.

Answer 2

from_iterable

Based on my answer to this linked list question

def from_iterable(iterable: Iterable[T]) -> Tuple[_Node[T], _Node[T], int]:
    """Constructs a node-list from an iterable.
    Returns a tuple of (head, last_node, list_length). head and last_node will be None if iterable is empty."""
    it = iter(iterable)

    try:
        head = current = _Node(next(it))
        count = 1
    except StopIteration:
        return None, None, 0

    for count, t in enumerate(it, 2):
        current.tail = current = _Node(t)

    return head, current, count

n = _Node.from_iterable(range(6))

(
  _Node(data=0, tail=_Node(data=1, tail=_Node(data=2, tail=_Node(data=3, tail=_Node(data=4, tail=_Node(data=5, tail=None)))))),
  _Node(data=5, tail=None),
  6
)

remove

For the remove you can use 2 ways to make it more clear: you can do the check whether the head is the element to remove outside of the loop, and use the pairwise itertools recipe to iterate over the node 2 by 2

from itertools import tee
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)



def remove(self, elem: T): 
    if self.head.data == elem:
        self._pop_head()
        self._size -= 1
        return
    for first, second in pairwise(self._node_iter()):
        if second.data == elem:
            first.remove_next()
            self._size -= 1
            return
    raise ValueError(f"{elem} not in list.")

Or you can use pop This results in cleaner code, but 2 iterations until the index

def remove(self, elem: T):
    for i, value in enumerate(self):
        if value == elem:
            self.pop(i)
            return
    raise ValueError(f"{elem} not in list.")