// Pantea Aria

// Linked Lists - Create, travers, insert 

// Build a linked list by inserting values 0 to 9
// at the end (tail) of an initially empty list

// Use a loop to repeatedly add each new node to the tail

// free functions for later

// For now, this program will leak memory

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

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

// TODO 1:
// Write the function prototypes for:
// - create_node
struct node *create_node(int data, struct node *next);
// - print_list
void print_list(struct node *head);
// - insert_at_tail
struct node *insert_at_tail(struct node *head, int data);
// - list_length
int list_length(struct node *head);
// - insert_at_middle
struct node *insert_at_middle(struct node *head, int data);



int main(void) {

    // TODO 2:
    // Declare a pointer called head and initialise it to NULL
    // This will represent an empty linked list
    struct node *head = NULL;

    // TODO 3:
    // Use a loop to insert values 0–9 at the START of the list
    // (Hint: create_node should be used here)
    // After each insertion, print the list
    for (int i = 0; i < 10; i++) {
        struct node *new_node = create_node(i, head);
        head = new_node;
        print_list(head);
    }


    // TODO 4:
    // Create a second list called head2
    // Insert values 0–9 at the END of the list using insert_at_tail
    // After each insertion:
    //   - Print the list length
    //   - Print the list contents


    // TODO 5:
    // Insert the value 99 into the middle of head2
    // Print the new length and the updated list


    // TODO 6:
    // Create a third list (empty)
    // Insert 42 into the middle of this empty list
    // Print the result


    return 0;
}


// TODO 7:
// Implement create_node
// - Allocate memory
// - Check if malloc returned NULL
// - Initialise data and next
// - Return the new node
struct node *create_node(int data, struct node *next) {
    struct node *new = malloc(sizeof(struct node));
    if (new == NULL) {
        return NULL;
    }
    new->data = data;
    new->next = next;

    return new;
}



// TODO 8:
// Implement print_list
// - Traverse from head to NULL
// - Print each data value
void print_list(struct node *head) {
    // make a temporary pointer to travers my linked list
    struct node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
} 


// TODO 9:
// Implement insert_at_tail
// - Create a new node
// - If list is empty, return new node as head
// - Otherwise traverse to the last node
// - Attach new node at the end
// - Return head



// TODO 10:
// Implement list_length
// - Traverse the list
// - Count how many nodes exist
// - Return the count



// TODO 11:
// Implement insert_at_middle
// - Create a new node
// - If list is empty, return new node
// - Find the position size/2
// - Move to the node before that position
// - Adjust pointers to insert the new node
// - Return head