# please define a very simple singly linked list
# list items:     4 -> 7 -> 2
# item positions: 0    1    2
# please write a function that, given a value and a position, inserts the value into the list at that position
# 4,7,2 => insert 9 at position 1 => 4,9,7,2

class LinkedList(object):

    def __init__(self):
        HEAD = None

# 4,7,2 => insert 9 at position 0 => 9,4,7,2
    def insert(self, id, pos): # id: 9, pos: 0
        node = Node(id) # Node(9) -> Node.id:9, Node.pointer:None
        # id = 9, pointer = None
        if HEAD is None or pos == 0:
            # -> HEAD:4, 7, 2 -> HEAD:9 -> 4 -> 7 -> 2
            node.pointer = HEAD
            HEAD = node
        else:
            aux = HEAD # aux:4
            old_node = HEAD #old_node:4
            i = 0 # 4 -> [9] -> 7 -> 2
            while aux.pointer is not None:
                old_node.pointer = node # old_node: 4 -> Node:9
                    node.pointer = aux
                    break
                old_node = aux
                aux = aux.pointer


class Node(object):

        def __init__ (self, id):
            self.id = id
            self.pointer = None