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)

• Carcigenicate: Oops. # FIXME: Need to handle a negative step isn't supposed to be there. I dealt with that.

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.

• Carcigenicate: Thanks, I had never seen dummy nodes in this context before.

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