Doubly Linked List 2 ways in python

doubly_linked_list.py

from typing import Optional

from typing_extensions import Self


class Node:
    def __init__(self, value: Optional[any] = None):
        self.prev: Optional[Self] = None
        self.next: Optional[Self] = None
        self.value: any = value


class DLL:
    """
    Doubly Linked List implementation using null terminators
    to identify the first and last nodes.

    If a node does not have a previous node, then it is the first.
    If a node does not have a next node, then it is the last.
    """

    def __init__(self):
        self.first: Optional[Node] = None
        self.last: Optional[Node] = None

    def insert_after(self, existing_node: Node, new_node: Node):
        new_node.prev = existing_node
        if not existing_node.next:
            self.last = new_node
        else:
            new_node.next = existing_node.next
            new_node.next.prev = new_node
        existing_node.next = new_node

    def insert_before(self, existing_node: Node, new_node: Node):
        new_node.next = existing_node
        if not existing_node.prev:
            self.first = new_node
        else:
            new_node.prev = existing_node.prev
            new_node.prev.next = new_node
        existing_node.prev = new_node

    def insert_first(self, new_node: Node):
        if not self.first:
            self.first = new_node
            self.last = new_node
            new_node.prev = None
            new_node.next = None
        else:
            self.insert_before(self.first, new_node)

    def insert_last(self, new_node: Node):
        if not self.last:
            # if there is not a `last` node then there is not a `first` node,
            # so we can simply insert at the beginning
            self.insert_first(new_node)
        else:
            self.insert_after(self.last, new_node)

    def remove(self, node: Node):
        if not node.prev:
            self.first = node.next
        else:
            node.prev.next = node.next

        if not node.next:
            self.last = node.prev
        else:
            node.next.prev = node.prev

    def find(self, value: any, *, forwards=True, node: Optional[Node] = None) -> any:
        node = self.first if node is None else node
        while node:
            if node.value == value:
                return node
            node = node.next if forwards else node.prev


class DLLWithSentinel:
    """
    Doubly linked list using a sentinel node.

    The use of a sentinel node removes all the null checks
    and greatly simplifies the algorithms for inserting
    and removing nodes.

    The sentinel node also joins the first and last nodes together
    creating a circular list of nodes
    """

    def __init__(self):
        self._sentinel: Node = Node()
        self._sentinel.next = self._sentinel
        self._sentinel.prev = self._sentinel

    @property
    def first(self):
        return self._sentinel.next

    @property
    def last(self):
        return self._sentinel.prev

    def insert_after(self, existing_node: Node, new_node: Node):
        new_node.prev = existing_node
        new_node.next = existing_node.next
        existing_node.next.prev = new_node
        existing_node.next = new_node

    def insert_before(self, existing_node: Node, new_node: Node):
        new_node.next = existing_node
        new_node.prev = existing_node.prev
        existing_node.prev.next = new_node
        existing_node.prev = new_node

    def insert_first(self, new_node: Node):
        self.insert_after(self._sentinel, new_node)

    def insert_last(self, new_node: Node):
        self.insert_before(self._sentinel, new_node)

    def remove(self, node: Node):
        if node is self._sentinel:
            raise Exception("sentinel node cannot be removed")

        node.prev.next = node.next
        node.next.prev = node.prev

    def find(self, value: any, *, forwards=True, node: Optional[Node] = None) -> any:
        node = self.first if node is None else node
        while node != self._sentinel:
            if node.value == value:
                return node
            node = node.next if forwards else node.prev

test_doubly_linked_list.py

from typing import Union

import pytest

from doubly_linked_list import DLL, DLLWithSentinel, Node


@pytest.mark.parametrize("dll", [DLL(), DLLWithSentinel()])
def test_insert_first(dll: Union[DLL, DLLWithSentinel]):
    node = Node("1")
    dll.insert_first(node)
    # node1
    assert dll.first == node
    node2 = Node("2")
    dll.insert_first(node2)
    # node2 -> node 1
    assert dll.first == node2
    assert node.prev == node2
    node3 = Node("3")
    dll.insert_after(node2, node3)
    # node2 -> node3 -> node1
    assert node2.next == node3
    assert node3.prev == node2
    assert node3.next == node


@pytest.mark.parametrize("dll", [DLL(), DLLWithSentinel()])
def test_insert_last(dll: Union[DLL, DLLWithSentinel]):
    node = Node()
    dll.insert_last(node)
    assert dll.first == node
    assert dll.last == node

    node2 = Node()
    dll.insert_last(node2)
    assert dll.first == node
    assert dll.last == node2


@pytest.mark.parametrize("dll", [DLL(), DLLWithSentinel()])
def test_insert_middle(dll: Union[DLL, DLLWithSentinel]):
    for i in range(9):
        dll.insert_last(Node(f"{i+1}"))

    assert dll.last.value == "9"

    node5 = dll.find("5")
    assert node5.value == "5"
    assert node5.next.value == "6"

    dll.insert_after(node5, Node("10"))
    assert node5.next.value == "10"

    assert node5.prev.value == "4"
    dll.insert_before(node5, Node("11"))
    assert node5.prev.value == "11"

    node10 = dll.find("10")
    dll.remove(node10)
    assert node5.next.value == "6"