// Pantea Aria

// linked list
// - create_node
// - print_list
// - insert_at_tail
// - delete_first
// - delete_all
// - search_and_delete

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

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

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node *insert_at_tail(struct node *head, int data);

struct node *delete_first(struct node *head);
struct node * delete_all(struct node *head);
struct node *search_and_delete(struct node *head, int value);

int main(void) {
    struct node *head = NULL;

    // TODO: Print the empty list
    print_list(head);

    printf("Search and delete from empty list\n");
    // TODO: Try deleting 99 from an empty list
    head = search_and_delete(head, 1000);
    print_list(head);

    // TODO: Build a list that stores 0..9 by inserting at the tail
    for (int i = 0; i < 10; i++) {
        head = insert_at_tail(head, i);
    }
    print_list(head);
    
    printf("delete first '0'\n");
    // TODO: Delete 4 (middle case)
    head = delete_first(head);
    print_list(head);
    
    //delete_all(head);
   // print_list(head);
    

    printf("Search and delete 4\n");
    // TODO: Delete 4 (middle case)
    head = search_and_delete(head, 4);
    print_list(head);

    printf("Search and delete 1000\n");
    // TODO: Delete 99 (not found case)
    head = search_and_delete(head, 1000);
    print_list(head);

    printf("Search and delete 9\n");
    // TODO: Delete 9 (tail case)
    head = search_and_delete(head, 9);
    print_list(head);

    printf("Search and delete 0\n");
    // TODO: Delete 0 (head case)
    head = search_and_delete(head, 0);
    print_list(head);

    // TODO: Free all remaining nodes to prevent memory leaks
    head = delete_all(head);

    print_list(head);

    return 0;
}

// TODO: Allocate memory for a new node using malloc.
// TODO: If malloc fails, return NULL.
// TODO: Set new_node->data and new_node->next, then return new_node.
struct node *create_node(int data, struct node *next) {
    // TODO
    struct node *new = malloc(sizeof(struct node));
    if (new != NULL) {
        new->data = data;
        new->next = next;
        return new;
    } else {  
        return NULL;
    } 
}

// TODO: Traverse from head to NULL and print each node’s data.
// TODO: Print something like: "list:" then the values on one line.
void print_list(struct node *head) {
    // TODO
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");    
}

// TODO: Insert a new node (with given data) at the end of the list.
// Cases to handle:
// - Empty list: new node becomes the head.
// - Non-empty list: traverse to last node, then link it to new node.
// Return the (possibly updated) head.
struct node *insert_at_tail(struct node *head, int data) {
    // TODO
    struct node *new = create_node(data, NULL);
    if (head == NULL) {
        return new;   //head = new; return head;
    } else {
        // find the last node
        struct node *last = head;
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = new;
    }    
                   
    return head;
}

// TODO: Delete the first node (if it exists) and free it.
// Return the new head pointer.
struct node *delete_first(struct node *head) {
    // TODO
    if (head == NULL) {
        return NULL;   //return head;
    }  
    // head->10->2->X
    // head->2->X
    struct node *tmp = head;
    head = head->next;
    free(tmp);

    return head;
}

// TODO: Free every node in the list.
// Hint: you must save the next pointer before calling free on current.
// issues here
struct node *delete_all(struct node *head) {
    // TODO
    struct node *current = head;

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

// TODO: Find the first node whose data == value, remove it from the list,
// and free it.
// Cases to handle:
// - Empty list
// - Value not found
// - Deleting head node
// - Deleting middle/tail node
// Return the updated head.
struct node *search_and_delete(struct node *head, int value) {
    if (head == NULL) {
        return NULL;
    }
    struct node *prev = NULL;
    struct node *curr = head;
    while (curr != NULL && curr->data != value) {
        prev = curr;
        curr = curr->next;
    }
    // 1. if prev = NULL, the first node should be removed
    if (prev == NULL) {
        head = curr->next;
    } else if (curr == NULL) {
        return head;
    } else {    
        prev->next = curr->next;
    }
    free (curr);        

    return head;
}