Double-Linked List Python implementation

A while ago I read an article about implementing linked lists on Python and to practice I reproduced the same interface with some additions (adding a tail, mypy type hints and a few tests).

Then I forgot about it, until recently I read something about sorting linked lists (I think in the DOOM source code analysis book I've read but it's not relevant) and I thought "I have this Python implementation, why not practice ordering that list?", so I grabbed the code, started working on it and, apart from a bugfix (tests are wonderful but you need to do proper ones and not just happy cases), I ended up adding new functions like insert_after(), sort(), flip(), clear(), making the linked list iterable and improving some operations performance along the way (also refreshing the big-O notation).

The beauty of having spent some time iterating on adding those new functions and "enhancements" is that now the code looks so slick and still useful, as you can specify your own sorting logic, normal or reverse, etc.. Here's for example the relevant code to make the list iterable and sortable:

def __init__(self) -> None:
    self.head: Optional["LinkedListNode"] = None
    self.tail: Optional["LinkedListNode"] = None

    self._iteration_cursor: Optional[LinkedListNode] = self.head

def __iter__(self) -> "LinkedList":
    self._iteration_cursor = self.head
    return self

def __next__(self) -> LinkedListNode:
    if self._iteration_cursor:
        current_node = self._iteration_cursor
    else:
        raise StopIteration
    self._iteration_cursor = self._iteration_cursor.next_node
    return current_node

# ...

def sort(self, comparison_function: Callable, reverse: bool = False) -> None:
    ordered_list = sorted(self, key=comparison_function, reverse=reverse)

    self.clear()

    for node in ordered_list:
        self.append(data=node.data)

And a sample usage taken from the tests:

def node_comparison_function(node):
    return int(node.data["id"]) if node else 0

node_1_data = {"id": 1}
node_2_data = {"id": 2}
node_3_data = {"id": 3}
node_4_data = {"id": 4}

linked_list = LinkedList()
linked_list.append(node_1_data)
linked_list.append(node_2_data)
linked_list.append(node_3_data)
linked_list.append(node_4_data)

# 1 2 3 4 -> 4 3 2 1
linked_list.sort(comparison_function=node_comparison_function, reverse=True)

It was a nice exercise and after yesterday a friend sending me a link to Nicholas Zakas Javascript implementation of a single linked list I like how my approach is quite extensible and fast, but in exchange requires you to explicitly find the nodes before being able to remove() or insert_after(). Although having to write list.remove(list.find(xxxx)) instead of list.remove(xxxx) doesn't feels terrible to me (explicit over implicit?), and the list interface becomes more tight as uses nodes everywhere possible instead of raw data, leaving that for inserts and searches only.

All of this was just meant to say that if you want a Python double-linked list implementation quite deeply tested, type annotated, with reversing, inserting at head/tail/anywhere, searching and sorting by custom function in both directions, I built one: https://github.com/Kartones/PythonAssorted/tree/master/double-linked-list .