#include <conio.h>
#include <iostream>
class Elem
{
    int val;
    class Elem* next;
public:
    Elem(int in) : next(0), val(in){}
    friend class List;
};
class List {
    Elem* head, * tail;
    unsigned N=0;
public:
    List() : tail(0) {tail = head; }
    void push_back(int data);
    int pop_front();
    void push(int data);
    void insert(int data, unsigned n);
};
void List :: push_back(int data)
{
    Elem* e = new Elem(data);
    if (head == NULL)
    {
        head = e;
        tail = e;
    }
    else {
        tail->next = e;
        tail = e;
    }
    N++;
}
void List::push(int data)
{
    Elem* e = new Elem(data);
    e->next = head;
    head = e;
    N++;
}
void List::insert(int data, unsigned n)
{
    if (n > N)
    {
        perror("Program Error");
        return;
    }
    if (n == 0)
    {
        push(data);
        return;
    }
    if (n == N)
    {
        push_back(data);
        return;
    }
    Elem* e = head;
    int counter = 0;
    while (counter < n - 1)
    {
        e = e->next;
        counter++;
    }
    Elem* p1 = new Elem(data);
    Elem* p2 = e->next;
    e->next = p1;
    p1->next = p2;
    ++N;
}
int List::pop_front()
{
    Elem* e = head;
    int out = e->val;
    head = e->next;
    delete e;
    --N;
    return out;
}

int main()
{
    List list;
    for (int i = 1; i <= 10; ++i)
        list.push_back(i * i);
    list.insert(0, 0);
    for (int i = 1; i <= 11; ++i)
    {
        int k = list.pop_front();
        std::cout << k <<'\t';
    }
}