//Q2.3) WAP to implement a linked list, insert data at any position, delete data at any position and then print the linked list.
 
#include <iostream>
#include<stdlib.h>
using namespace std;
 
struct node{
    int data;
    node* next;
    void setData(int d){
        data=d;
        next=NULL;
    }
};
 
void InsertAtHead(node* &head,int data){
    node* newNode=(node*)malloc(sizeof(node));
    newNode->setData(data);
    newNode->next=head;
    head=newNode;
}
 
void InsertAtTail(node* &tail,int data){
    node* newNode=(node*)malloc(sizeof(node));
    newNode->setData(data);
    tail->next=newNode;
    tail=newNode;
}
 
void InsertAtPosition(node* &head,node* &tail,int position,int data){
    if(position==1){
        InsertAtHead(head,data);
        return ;
    }
    node* temp=head;
    int nodeNumber=1;
    while(nodeNumber<position-1){
        temp=temp->next;
        nodeNumber++;
    }
 
    if(temp->next==NULL){
        InsertAtTail(tail,data);
        return ;
    }
    node* newNode=(node*)malloc(sizeof(node));
    newNode->setData(data);
    newNode->next=temp->next;
    temp->next=newNode;
    
}
void DeleteAtPosition(node* &head,node* &tail,int position){
    node* temp=head;
    int nodeNumber=1;
    if(position==1){
        head=temp->next;
        temp->next=NULL;
        free(temp);
        temp=NULL;
        return ;
    }
    while(nodeNumber<position-1){
        temp=temp->next;
        nodeNumber++;
    }
    node* toDelete=temp->next;

    if(toDelete==tail){
        tail=temp;
        tail->next=NULL;
        free(toDelete);
        toDelete=NULL;
        return ;
    }

    temp->next=toDelete->next;
    toDelete->next=NULL;
    free(toDelete);
    toDelete=NULL;
}
void PrintLinkedList(node* &head){
    node* temp=head;
    while(temp!=NULL){
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
 
int main(){
 
    node* head=(node*)malloc(sizeof(node));
    head->setData(1);
    node* tail=head;
    
    InsertAtHead(head,2);
    InsertAtTail(tail,4);
    InsertAtTail(tail,5);
 
    cout<<"Before Insertion: ";
    PrintLinkedList(head);
    
    InsertAtPosition(head,tail,5,7);
    InsertAtPosition(head,tail,3,6);
    InsertAtPosition(head,tail,1,3);
    
    cout<<"After Insertion: ";
    PrintLinkedList(head);
    cout<<endl;
    cout<<"Before Deletion: ";
    PrintLinkedList(head);

    DeleteAtPosition(head,tail,7);
    DeleteAtPosition(head,tail,4);
    DeleteAtPosition(head,tail,1);

    cout<<"After Deletion: ";
    PrintLinkedList(head);

 
    return 0;
}
/*
    OUTPUT:
 
    Before Insertion: 2 1 4 5 
    After Insertion: 3 2 1 6 4 5 7 

    Before Deletion: 3 2 1 6 4 5 7 
    After Deletion: 2 1 4 5 
 
*/