/*
 * Ex. No. 5: IMPLEMENTATION OF LINKED LIST
 * Student Record Management System using a singly linked list
 * Supports: INSERT (beginning/end/position), DELETE (beginning/end/position),
 *           SEARCH, DISPLAY
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NAME_LEN 50

struct Node {
    int regNo;
    char name[NAME_LEN];
    struct Node *next;
};

struct Node *head = NULL;

/* Count nodes in list */
int countNodes(void) {
    int count = 0;
    struct Node *cur = head;
    while (cur != NULL) {
        count++;
        cur = cur->next;
    }
    return count;
}

/* Allocate and fill a new node */
struct Node *makeNode(int regNo, const char *name) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->regNo = regNo;
    strncpy(node->name, name, NAME_LEN - 1);
    node->name[NAME_LEN - 1] = '\0';
    node->next = NULL;
    return node;
}

/* i) Insert at Beginning */
void insertBeginning(int regNo, const char *name) {
    struct Node *node = makeNode(regNo, name);
    node->next = head;
    head = node;
    printf("Inserted at beginning.\n");
}

/* ii) Insert at End */
void insertEnd(int regNo, const char *name) {
    struct Node *node = makeNode(regNo, name);
    if (head == NULL) {
        head = node;
    } else {
        struct Node *cur = head;
        while (cur->next != NULL)
            cur = cur->next;
        cur->next = node;
    }
    printf("Inserted at end.\n");
}

/* iii) Insert at a Given Position (1-based) */
void insertAtPosition(int pos, int regNo, const char *name) {
    int size = countNodes();
    if (pos < 1 || pos > size + 1) {
        printf("Invalid position.\n");
        return;
    }
    if (pos == 1) {
        insertBeginning(regNo, name);
        return;
    }
    struct Node *prev = head;
    for (int i = 1; i < pos - 1; i++)
        prev = prev->next;
    struct Node *node = makeNode(regNo, name);
    node->next = prev->next;
    prev->next = node;
    printf("Inserted at position %d.\n", pos);
}

/* iv) Delete from Beginning */
void deleteBeginning(void) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct Node *doomed = head;
    head = head->next;
    free(doomed);
    printf("Deleted from beginning.\n");
}

/* v) Delete from End */
void deleteEnd(void) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    if (head->next == NULL) {
        free(head);
        head = NULL;
        printf("Deleted from end.\n");
        return;
    }
    struct Node *cur = head;
    while (cur->next->next != NULL)
        cur = cur->next;
    free(cur->next);
    cur->next = NULL;
    printf("Deleted from end.\n");
}

/* vi) Delete from a Given Position (1-based) */
void deleteAtPosition(int pos) {
    int size = countNodes();
    if (size == 0) {
        printf("List is empty.\n");
        return;
    }
    if (pos < 1 || pos > size) {
        printf("Invalid position.\n");
        return;
    }
    if (pos == 1) {
        deleteBeginning();
        return;
    }
    struct Node *prev = head;
    for (int i = 1; i < pos - 1; i++)
        prev = prev->next;
    struct Node *doomed = prev->next;
    prev->next = doomed->next;
    free(doomed);
    printf("Deleted position %d.\n", pos);
}

/* vii) Search by register number */
void search(int regNo) {
    struct Node *cur = head;
    int pos = 1;
    while (cur != NULL) {
        if (cur->regNo == regNo) {
            printf("Found: RegNo=%d, Name=%s, Position=%d\n", cur->regNo, cur->name, pos);
            return;
        }
        cur = cur->next;
        pos++;
    }
    printf("Register number %d not found.\n", regNo);
}

/* viii) Display all students */
void display(void) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct Node *cur = head;
    int pos = 1;
    printf("--- Student Records ---\n");
    while (cur != NULL) {
        printf("%d) RegNo=%d, Name=%s\n", pos, cur->regNo, cur->name);
        cur = cur->next;
        pos++;
    }
}

/* Free all remaining nodes before exit */
void freeList(void) {
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
    head = NULL;
}

void readName(char *name) {
    scanf(" %49[^\n]", name);
}

int main(void) {
    int choice, regNo, pos;
    char name[NAME_LEN];

    do {
        printf("\n===== Student Record Management System =====\n");
        printf("1. Insert at Beginning\n");
        printf("2. Insert at End\n");
        printf("3. Insert at a Given Position\n");
        printf("4. Delete from Beginning\n");
        printf("5. Delete from End\n");
        printf("6. Delete from a Given Position\n");
        printf("7. Search\n");
        printf("8. Display\n");
        printf("9. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter register number: ");
                scanf("%d", &regNo);
                printf("Enter name: ");
                readName(name);
                insertBeginning(regNo, name);
                break;
            case 2:
                printf("Enter register number: ");
                scanf("%d", &regNo);
                printf("Enter name: ");
                readName(name);
                insertEnd(regNo, name);
                break;
            case 3:
                printf("Enter position: ");
                scanf("%d", &pos);
                printf("Enter register number: ");
                scanf("%d", &regNo);
                printf("Enter name: ");
                readName(name);
                insertAtPosition(pos, regNo, name);
                break;
            case 4:
                deleteBeginning();
                break;
            case 5:
                deleteEnd();
                break;
            case 6:
                printf("Enter position: ");
                scanf("%d", &pos);
                deleteAtPosition(pos);
                break;
            case 7:
                printf("Enter register number to search: ");
                scanf("%d", &regNo);
                search(regNo);
                break;
            case 8:
                display();
                break;
            case 9:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice.\n");
        }
    } while (choice != 9);

    freeList();
    return 0;
}