class Node:
    """
    Node for Linked List
    """
    def __init__(self, data: int):
        self.data = data
        self.next = None

def insert(node, data: int):
    """
    Insertion at the beginning to avoid
    traversing the list
    """
    tmp = Node(data)
    tmp.next = node
    node = tmp
    return node

def print_list(node):
    """
    Recursively traverse the list and
    print data
    """
    if node is None:
        return
    print(node.data, end=' ')
    print_list(node.next)

# Recursive find
def find_recursive(node, data):
    """
    Recursively traverse the list and
    return a node when its data mathes a provided data
    """
    if node is None:
        return
    if node.data == data:
        return node
    return find_recursive(node.next, data)

def find_predecessor(node, data):
    """
    Find a predecessor of a node of which data matches a provided data
    """
    if node is None or node.next is None:
        return
    if node.next.data == data:
        return node
    else:
        return find_predecessor(node.next, data)


def find(head, data):
    """
    Find a node iteratively for a provided data
    """
    tmp = head
    while tmp:
        if tmp.data == data:
            break
        tmp = tmp.next
    return tmp

def delete(head, data):
    """
    Deleting a node requires a pointer to a predecessor
    """
    cur = find_recursive(head, data)
    if cur:
        pred = find_predecessor(head, data)
        if pred is None:
             head = cur.next
        else:
            pred.next = cur.next
    return head


def test_simple():
    head = Node(1)
    assert head.data == 1

    head = insert(head, 2)
    assert head.data == 2
    assert head.next.data == 1

    head = insert(head, 3)
    print_list(head)

    assert find(head, 7) == None
    assert find(head, 3) == head
    assert find(head, 2) == head.next

    assert find_predecessor(head, 3) == None
    assert find_predecessor(head, 2) == head
    assert find_predecessor(head, 1) == head.next

    head = delete(head, 2)
    assert head.data == 3
    assert head.next.data == 1

if __name__ == '__main__':
    test_simple()