class Node:
    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next


class List:
    def __init__(self):
        self.head = None
        self.length = 0

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.get_data()
            current = current.get_next()

    def __str__(self):
        result = ""
        for x in list:
            result += str(x)
            result += " "
        return result.strip()

    def is_empty(self):
        return self.head is None

    def size(self):
        return self.length

    def search(self, item):
        return item in self

    # mógłby mieć złożoność stałą, ale wtedy
    # generator zwraca odwrotną kolejność
    # O(n)
    def append(self, data):
        self.length += 1
        if self.head is None:
            self.head = Node(data)
            return
        current = self.head
        while current.get_next() is not None:
            current = current.get_next()
        current.set_next(Node(data))

    # O(pos)
    def pop(self, pos):
        current = self.head
        if pos < 0:
            raise ValueError('Position < 0')
        elif pos == 0:
            self.head = current.get_next()
        else:
            for i in range(0, pos):
                current = current.get_next()
            next_node = current.get_next()
            current.set_next(next_node)

        self.length -= 1
        return current.get_data()

    # O(pos)
    def insert(self, pos, item):
        current = self.head
        if pos < 0:
            raise ValueError('Position < 0')

        if pos == 0:
            self.head = Node(item)
            self.head.set_next(current)
            self.length += 1
            return

        for i in range(0, pos):
            current = current.get_next()
        next_node = current.get_next()
        to_insert = Node(item)
        current.set_next(to_insert)
        to_insert.set_next(next_node)
        self.length += 1