Linked List

code: python

from typing import Optional, Any

class Node:

def __init__(self, data: Any):

self.data: Any = data

class LinkedList:

def __init__(self):

# O(1), O(1)

def insert(self, data: Any, prev_node: Node) -> Node:

new_node = Node(data)

if prev_node is None:

self.head = new_node

else:

new_node.next = prev_node.next

prev_node.next = new_node

return new_node

# O(n), (1)

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

if self.head is None:

return False

if self.head == node:

self.head = self.head.next

return True

current = self.head

while current.next:

if current.next == node:

current.next = node.next

return True

current = current.next

return False

# 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():

llist = LinkedList()

node1 = llist.insert(1, None)

llist.insert(2, node1)

llist.insert(3, node1)

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

def test_delete_middle():

llist = LinkedList()

node1 = llist.insert(1, None)

node2 = llist.insert(2, node1)

llist.insert(3, node2)

llist.delete(node2)

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

def test_delete_last():

llist = LinkedList()

node1 = llist.insert(1, None)

node2 = llist.insert(2, node1)

node3 = llist.insert(3, node2)

llist.delete(node3)

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

def test_delete_single_node():

llist = LinkedList()

node = llist.insert(1, None)

llist.delete(node)

assert str(llist) == ""

def test_find():

llist = LinkedList()

node1 = llist.insert(1, None)

node2 = llist.insert(2, node1)

llist.insert(3, node2)

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

assert llist.find(4) is None

def test_length():

llist = LinkedList()

assert len(llist) == 0

node1 = llist.insert(1, None)

assert len(llist) == 1

llist.insert(2, node1)

llist.insert(3, node1)

assert len(llist) == 3