#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* next;
node(int d){
data=d;
node*next=NULL;
}
};
//TO INSERT A NODE AT HEAD
void insertAtHead(node*&head,int data){
node* n = new node(data); // we create a new node n , we initilise it by calling node(data), so it stores the data , only thing left is to link it to the next node
// which is done by n->next=head (n ke next waale part mein next node ka ddress daalo which is same as the address in head)
n->next = head;
head = n; //ab link head to the new node cretaed ... by putting vlue of n in head pointer.
}
//TO INSERT AT END
void insertAtEnd(node*&head,int data){
if(head==NULL){
insertAtHead(head,data);
}
else
{
node*temp=head;
while(temp!=NULL){
temp=temp->next;
}
temp->next = new node(data);
return;
}
}
//TO INSERT AT MIDDLE
int len(node*&head){
int length=0;
node*temp=head;
while(temp!=NULL){
length =length +1;
temp=temp->next;
}
return length;
}
void insertAtMiddle(node*&head,int data,int pos){
if(head==NULL || pos==0){
insertAtHead(head,data);
}
else if(pos>len(head)){
insertAtEnd(head,data);
}
else
//inserting at middle
{ node*temp=head;
int jump=1;
while(jump <= pos-1){
temp=temp->next;
jump=jump+1;
}
node*n= new node(data);
n->next=temp->next;
temp->next= n;
}
}
void print(node*&head){
while(head !=NULL){
cout<data<<endl;
head = head->next;
}
}
int main(){
node* head = NULL;
insertAtHead(head,1);
insertAtHead(head,2);
insertAtHead(head,3);
insertAtMiddle(head,4,2);
insertAtEnd(head,6);
print(head);
return 0;
}