Created
November 8, 2022 16:28
-
-
Save withakay/af8bdf8b841d099e18dec17e19382d22 to your computer and use it in GitHub Desktop.
Doubly Linked List 2 ways in python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment