// Pantea Aria

// Linked Lists - Create, travers, insert, length, search

// 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;
};

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);  
int list_search(struct node *head, int value);

int main(void) {

    printf("==== Creating List ====\n");

    struct node *head = NULL;

    // Insert some values at the tail
    head = insert_at_tail(head, 5);
    head = insert_at_tail(head, 15);
    head = insert_at_tail(head, 25);
    head = insert_at_tail(head, 35);

    print_list(head);


    printf("\n==== Search Tests ====\n");

    // Search for first element
    printf("Search 5: %d\n", list_search(head, 5));

    // Search for middle element
    printf("Search 25: %d\n", list_search(head, 25));

    // Search for last element
    printf("Search 35: %d\n", list_search(head, 35));

    // Search for value not in list
    printf("Search 100: %d\n", list_search(head, 100));


    printf("\n==== Search in Empty List ====\n");

    struct node *empty = NULL;
    printf("Search 10 in empty list: %d\n",
           list_search(empty, 10));

    return 0;
}

    
struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        return NULL;
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

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

//                
struct node *insert_at_tail(struct node *head, int data) {
    struct node *new_node = create_node(data, NULL);
    
    // The list is empty
    if (head == NULL) {
        head = new_node;
    } else {
        struct node *current = head; //NULL
        
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
    return head;
}

// return 1 if the value is found in the given list
// return 0 otherwise
int list_search(struct node *head, int value) {
    if (head == NULL) {
         return 0;
    }
    struct node *curr = head;
    while(curr != NULL) {
        if (curr->data == value) {
            return 1;
        }
        curr = curr->next;
    }        
    // it means value not found
    return 0;

}