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

struct node {
    int data;
    struct node *next;
};

struct node *head;

void insert_at_beginning(int value);
void insert_at_last(int value);
void insert_at_position(int value, int position);
void insert_after_value(int value, int data);

void delete_at_beginning();
void delete_at_last();
void delete_at_position(int position);
void delete_after_value(int value);

void print_list();
void print_reverse(struct node* current);

int find_index(int_value);

void find_all_indices(int value);

void reverse_list();

int main() {
    int option, choice, value, position, data;
    while (1) {
        printf("\nMENU\n");
        printf("1. Insert values\n");
        printf("2. Delete values from the list\n");
        printf("3. Traverse the list\n");
        printf("4. Find the index of 1st occurence of value in list\n");
        printf("5. Find all indices correspoding to occurence of value\n");
        printf("6. Reverse the sequence of value in the list\n");
        printf("Enter your option: ");
        scanf("%d", &option);
        
        switch(option){
            case 1:
                printf("1. Insert at beginning\n");
                printf("2. Insert after last\n");
                printf("3. Insert at position\n");
                printf("4. Insert after a particular value\n");
                printf("5. Exit\n");
                printf("Enter your choice: ");
                scanf("%d", &choice);
                
                switch (choice) {
                    case 1:
                        printf("Enter value to insert: ");
                        scanf("%d", &value);
                        insert_at_beginning(value);
                        break;
                    case 2:
                        printf("Enter value to insert: ");
                        scanf("%d", &value);
                        insert_at_last(value);
                        break;
                    case 3:
                        printf("Enter value to insert: ");
                        scanf("%d", &value);
                        printf("Enter position to insert: ");
                        scanf("%d", &position);
                        insert_at_position(value, position);
                        break;
                    case 4:
                        printf("Enter value to insert after: ");
                        scanf("%d", &value);
                        printf("Enter data to insert: ");
                        scanf("%d", &data);
                        insert_after_value(value, data);
                        break;
                    case 5:
                        exit(0);
                    default:
                        printf("Invalid choice\n");
                        break;
                }
                break;
            case 2:
                printf("1. Delete at beginning\n");
                printf("2. Delete after last\n");
                printf("3. Delete at position\n");
                printf("4. Delete after a particular value\n");
                printf("5. Exit\n");
                printf("Enter your choice: ");
                scanf("%d", &choice);
                
                switch (choice) {
                    case 1:
                        delete_at_beginning(value);
                        break;
                    case 2:
                        delete_at_last(value);
                        break;
                    case 3:
                        printf("Enter position to delete: ");
                        scanf("%d", &position);
                        delete_at_position(position);
                        break;
                    case 4:
                        printf("Enter value to delete a node after that particular value: ");
                        scanf("%d", &value);
                        delete_after_value(value);
                        break;
                    case 5:
                        exit(0);
                    default:
                        printf("Invalid choice\n");
                        break;
                }
                break;
            case 3:
                printf("1. Print all the values in list\n");
                printf("2. Print values in reverse\n");
                printf("3. Exit\n");
                printf("Enter your choice: ");
                scanf("%d", &choice);
                
                switch (choice) {
                    case 1:
                        print_list();
                        break;
                    case 2:
                        printf("List in reverse order: ");
                        print_reverse(head);
                        printf("\n");
                        break;
                }
                break;
            case 4:
                printf("Enter value to find index: ");
                scanf("%d", &value);
                int index = find_index(value);
                if (index == -1) {
                    printf("Value not found\n");
                } 
                else {
                    printf("Index of first occurrence of %d: %d\n", value, index);
                }
                break;
            case 5:
                printf("Enter value to find all indices: ");
                scanf("%d", &value);
                find_all_indices(value);
                break;
            case 6:
                reverse_list();
                printf("List reversed successfully\n");
                break;
        }
    }
}

void insert_at_beginning(int value) {
    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = head;
    head = new_node;
    printf("Value %d inserted at beginning\n", value);
}

void insert_at_last(int value) {
    if (head == NULL) {
        insert_at_beginning(value);
        return;
    }

    struct node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }

    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = NULL;
    current->next = new_node;

    printf("Value %d inserted after last\n", value);
}

void insert_at_position(int value, int position) {
    if (position == 0) {
        insert_at_beginning(value);
        return;
    }

    struct node *current = head;
    int i = 0;
    while (i < position - 1 && current != NULL) {
        current = current->next;
        i++;
    }

    if (current == NULL) {
        printf("Invalid position\n");
        return;
    }

    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = current->next;
    current->next = new_node;

    printf("Value %d inserted at position %d\n", value, position);
}

// Function to insert a new node after a particular value in the linked list
void insert_after_value(int value, int data) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct node* current = head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    if (current == NULL) {
        printf("Value not found\n");
        return;
    }
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = current->next;
    current->next = new_node;
}


// Function to delete the first node from the linked list
void delete_at_beginning() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct node* temp = head;
    head = head->next;
    free(temp);
}

// Function to delete the last node from the linked list
void delete_at_last() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct node* current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

// Function to delete a node at a particular position/index in the linked list
void delete_at_position(int position) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    if (position == 0) {
        delete_at_beginning();
        return;
    }
    struct node* current = head;
    int i;
    for (i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next;
    }
    if (current == NULL || current->next == NULL) {
        printf("Invalid position\n");
        return;
    }
    struct node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

// Function to delete the node after a particular value in the linked list
void delete_after_value(int value) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct node* current = head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    if (current == NULL || current->next == NULL) {
        printf("Value not found or last node\n");
        return;
    }
    struct node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

void print_list() {
    struct node *current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void print_reverse(struct node* current) {
    if (current == NULL) {
        return;
    }
    print_reverse(current->next);
    printf("%d ", current->data);
}

// Function to find the index of the first occurrence of a value in the linked list
int find_index(int value) {
    int index = 0;
    struct node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return index;
        }
        index++;
        current = current->next;
    }
    return -1; // Value not found
}

// Function to find all indices corresponding to the occurrence of a value in the linked list
void find_all_indices(int value) {
    int index = 0;
    struct node* current = head;
    printf("Indices of all occurrences of %d: ", value);
    while (current != NULL) {
        if (current->data == value) {
            printf("%d ", index);
        }
        index++;
        current = current->next;
    }
    printf("\n");
}

// Function to reverse the sequence of values in the linked list
void reverse_list() {
    struct node *prev_node, *current_node, *next_node;
    current_node = head;
    prev_node = NULL;
    while (current_node != NULL) {
        next_node = current_node->next;
        current_node->next = prev_node;
        prev_node = current_node;
        current_node = next_node;
    }
    head = prev_node;
}