Linked Lists

"""A singly linked list implementation.

Typical usage example:

l = SinglyLinkedList()
l.insertBeginning(1)
# [1]
l.insertAfter(l.head(), 2)
# [1,2]
l.insertAfter(l.head().next(), 3)
# [1,2,3]
l.removeAfter(l.head())
# [1,3]
l.removeBeginning()
# [3]
"""
from __future__ import annotations
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.l = SinglyLinkedList()

    def tearDown(self):
        self.l = None

    def test_simple(self):
        self.assertEqual(str(self.l), '[]')
        self.l.insertBeginning(1)
        self.assertEqual(str(self.l), '[1]')
        self.l.insertBeginning(2)
        self.assertEqual(str(self.l), '[2,1]')
        n = self.l.head().next()
        self.l.insertAfter(n, 0)
        self.assertEqual(str(self.l), '[2,1,0]')
        n = self.l.head()
        self.l.removeAfter(n)
        self.assertEqual(str(self.l), '[2,0]')
        self.l.removeBeginning()
        self.assertEqual(str(self.l), '[0]')
        self.l.removeAfter(self.l.head())
        self.assertEqual(str(self.l), '[0]')
        self.l.removeBeginning()
        self.assertEqual(str(self.l), '[]')

class Node(object):
    """A node for a singly linked list.

    Attributes:
        v: the value stored at this node.
        n: a pointer to the next node in the linked list.
    """
    __slots__ = ['v', 'n']

    def __init__(self, v, n: Node=None):
        self.v = v
        self.n = n

    def __str__(self):
        return str(self.v)

    def next(self) -> Node:
        """Returns the Node after this Node.

        Args: None.
        
        Returns:
            Node - the Node after this one.
        """
        return self.n

class SinglyLinkedList(object):
    """A singly linked list.

    Attributes:
        h: the first node in this linked list.
    """
    def __init__(self):
        self.h = None

    def __str__(self):
        ns = []
        curr = self.h
        while curr:
            ns.append(str(curr))
            curr = curr.n
        return f"[{','.join(ns)}]"

    def head(self):
        """Returns the first Node in this linked list.

        Args: None.
        
        Returns:
            Node - the first Node.
        """
        return self.h

    def insertAfter(self, n: Node, value):
        """Inserts the input value after the input Node.

        Args:
            n: the Node after which to insert the new <value>.
            value: any value.

        Return: None.
        """
        n.n = Node(value, n.n)

    def removeAfter(self, n: Node):
        """Removes the next Node after the input Node.

        Args:
            n: the Node after which to remove.

        Return: None.
        """
        if not n.n:
            return
        n.n = n.n.n

    def insertBeginning(self, value):
        """Inserts the input value at the head of the linked list.

        Args:
            value: any value.

        Return: None.
        """
        self.h = Node(value, self.h)

    def removeBeginning(self):
        """Removes the Node at the head of the linked list.

        Args: None.

        Return: None.
        """
        if not self.h:
            return
        self.h = self.h.n