3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Oops. # FIXME: Need to handle a negative step isn't supposed to be there. I dealt with that. \$\endgroup\$ – Carcigenicate Nov 24 '19 at 23:27
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks, I had never seen dummy nodes in this context before. \$\endgroup\$ – Carcigenicate Nov 25 '19 at 12:00
1
\$\begingroup\$

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.")
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks. Those are both much cleaner. \$\endgroup\$ – Carcigenicate Nov 25 '19 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.