#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

class Node{
public:
    int data;
    Node *next;
};

typedef Node* List;

void initializer(List &L)
{
    L = NULL;
}
int length(List L)
{
    int dem = 0;
    while(L->next!=NULL)
    {
        dem ++;
    }
    return dem;
}
bool isEmpty(List L)
{
    if (L == NULL)
    {
        return true;
    } else return false;
}
Node* MakeNode(Node *P,int data)
{
    P = new Node;
    P->data = data;
    P->next = NULL;
    return P;
}
void insertFirst(List &L,int data)
{
    Node *P;
    P = MakeNode(P,data);
    P->next = L;
    L = P;
}
void insertK(List &L,int data,int k){
    Node*P ;
    if(k<1 || k > length(L)+1)
    {
        cout<<"Vi tri khong hop le " <<endl;
    }
    else if(k ==1)
    {
        insertFirst(L,data);
    }
    else
    {
        Node *Q = L;
        int vitri = 1;
        P = MakeNode(P,data);

        while(Q!= NULL && vitri != k-1)
        {
            vitri++;
            Q = Q->next;
        }
        P->next = Q->next;
        Q->next = P;
    }
}
void Xuat(List L)
{
    Node *Q = L;
    while(Q!=NULL){
        cout<<Q->data <<" ";
        Q= Q->next;
    }
    cout<<endl;
}
void Menu(List L)
{
    int data;
    int position;
    int choice;
while(1){
    cout<<"1 : Nhap vao dau Danh Sach "<<endl;
    cout<<"2 : Nhap vao vi tri cho truoc"<<endl;
    cout<<"3 : Xuat Danh Sach "<<endl;
    cout<<"4 : Ket Thuc "<<endl;
    cout<<" Ban chon so : "; cin>>choice;
    system("cls");
    switch(choice)
        {
        case 1:
            cout<<"Import data you need add "; cin>>data;
            insertFirst(L,data);
            break;
        case 2:
            cout<<"Import data you need add "; cin>>data;
            cout<<"Import position you need add data "; cin>>position;
            insertK(L,data,position);
            break;
        case 3:
            Xuat(L);
            break;
        case 4:
            break;
        default :
            cout<<"Nhap so tu 1 den 4" <<endl;
            break;
        }
    }
}
int main()
{
    List L;
    initializer(L);
    Menu(L);
    return 0;
}