#include <stdio.h>
#include <stdlib.h>

struct node{
    int info;
    struct node *link;
};

struct node *start = NULL, *last=NULL;

void ins_at_beg();
void ins_at_pos();
void ins_at_end();
void traverse();

int main(){
    while(1){
        printf("\n\t***MAIN MENU***");
        printf("\n1.Insert at beginning");
        printf("\n2.Insert at intermediate");
        printf("\n3.Insert at end");
        printf("\n4.Display");
        printf("\n5Exit\n");

        switch(getch()){
            case '1': ins_at_beg(); break;
            case '2': ins_at_pos(); break;
            case '3': ins_at_end(); break;
            case '4': traverse();   break;
            case '5': exit(0);      break;

        }
    }
}


void ins_at_beg(){
    struct node *temp;
    temp = (struct node*) malloc(sizeof(struct node));
    printf("\nEnter value to insert: ");
    scanf("%d", &temp->info);

    if(start==NULL){
        temp->link = temp;
        start = temp;
        last = temp;
    }else{
        temp->link = start;
        start = temp;
        last->link = temp;
    }
    printf("\n%d has been inserted at the beginning.",temp->info);
}

void ins_at_end(){
    struct node *temp;

    temp = (struct node*) malloc(sizeof(struct node));
    printf("\nEnter value to insert: ");
    scanf("%d", &temp->info);

    if(start==NULL){
        temp->link = temp;
        start = temp;
        last = temp;
    }else{
        temp->link = start;
        last->link = temp;
        last = temp;
    }

    printf("\n%d has been inserted at the end.",temp->info);
}

void ins_at_pos(){
    int i, pos;

    struct node *temp;
    struct node *temp1;

    temp = (struct node*) malloc(sizeof(struct node));
    temp1 = (struct node*) malloc(sizeof(struct node));

    printf("\nEnter value to insert: ");
    scanf("%d", &temp->info);

    if(start==NULL){
        printf("\nList is empty");
    }else{
        printf("\nEnter which position you want to insert at: ");
        scanf("%d",&pos);
        temp1 = start;
        for(i=-1; i <= pos-1 ;i++){
            temp1 = temp1 -> link;
        }
        temp->link = temp1 -> link;
        temp1 -> link = temp;
        printf("\n%d has been inserted at pos %d", temp->info, pos);

    }

}

void traverse(){
    struct node *temp;

    temp = (struct node*) malloc(sizeof(struct node));
    if(start==NULL){
        printf("\nList is empty");
    }else{
        temp = start;
        while(temp->link != start){
            printf("%d, ", temp->info);
            temp = temp->link;
        }
        printf("%d, ", temp->info);

    }

}