Doubly Linked List

code: python

from typing import Optional, Any

class Node:

def __init__(self, data: Any):

self.data: Any = data

class DoublyLinkedList:

def __init__(self):

# O(1), O(1)

new_node = Node(data)

# insert to top

if prev_node is None:

new_node.next = self.head

if self.head:

self.head.prev = new_node

self.head = new_node

if self.tail is None:

self.tail = new_node

else:

new_node.prev = prev_node

new_node.next = prev_node.next

prev_node.next = new_node

if prev_node == self.tail:

self.tail = new_node

return new_node

# O(1), O(1)

def delete(self, node: Node) -> bool:

if node.prev:

node.prev.next = node.next

else:

self.head = node.next

if node.next:

node.next.prev = node.prev

else:

self.tail = node.prev

return True

# O(n), O(1)

current = self.head

while current:

if current.data == data:

return current

current = current.next

return None

# O(n), O(1)

def __str__(self) -> str:

elements = []

current = self.head

while current:

elements.append(str(current.data))

current = current.next

return " -> ".join(elements)

# O(n), O(1)

def __len__(self) -> int:

count = 0

current = self.head

while current:

count += 1

current = current.next

return count

def test_insert():

dlist = DoublyLinkedList()

node1 = dlist.insert(1)

dlist.insert(2, node1)

dlist.insert(3, node1)

assert str(dlist) == "1 -> 3 -> 2"

assert dlist.head.data == 1

assert dlist.tail.data == 2

def test_delete_middle():

dlist = DoublyLinkedList()

node1 = dlist.insert(1)

node2 = dlist.insert(2, node1)

dlist.insert(3, node2)

dlist.delete(node2)

assert str(dlist) == "1 -> 3"

assert dlist.head.next == dlist.tail

assert dlist.tail.prev == dlist.head

def test_delete_last():

dlist = DoublyLinkedList()

node1 = dlist.insert(1)

node2 = dlist.insert(2, node1)

node3 = dlist.insert(3, node2)

dlist.delete(node3)

assert str(dlist) == "1 -> 2"

assert dlist.tail == node2

def test_delete_single_node():

dlist = DoublyLinkedList()

node = dlist.insert(1)

dlist.delete(node)

assert str(dlist) == ""

assert dlist.head is None

assert dlist.tail is None

def test_find():

dlist = DoublyLinkedList()

node1 = dlist.insert(1)

node2 = dlist.insert(2, node1)

dlist.insert(3, node2)

assert dlist.find(2).data == 2

assert dlist.find(4) is None

def test_length():

dlist = DoublyLinkedList()

assert len(dlist) == 0

node1 = dlist.insert(1)

assert len(dlist) == 1

dlist.insert(2, node1)

dlist.insert(3, node1)

assert len(dlist) == 3