// Week 8 Thursday Lecture
// Create a list with nodes by adding nodes with data 0..9 to the 
// tail of an empty list
// Search for values in the list
// We will leave the function to free nodes until later
// For now we will have a memory leak in this program

#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("List to search:\n");
    struct node *head = NULL;

    int found = list_search(head, 99);
    if (found == 1) {
        printf("Found 99\n");
    }

    head = insert_at_tail(head, 13);

    found = list_search(head, 13);
    if (found == 1) {
        printf("Found 13\n");
    }

    head = insert_at_tail(head, 17);
    head = insert_at_tail(head, 42);
    head = insert_at_tail(head, 5);
    print_list(head);

    // Test not in the list
    found = list_search(head, 99);
    if (found == 1) {
        printf("Found 99\n");
    }

    // first in the list
    found = list_search(head, 13);
    if (found == 1) {
        printf("Found 13\n");
    }

    // last in the list
    found = list_search(head, 5);
    if (found == 1) {
        printf("Found 5\n");
    }

    // between 2 nodes
    found = list_search(head, 42);
    if (found == 1) {
        printf("Found 42\n");
    }

   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) {
    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;
}

int list_search(struct node *head, int value) {
    struct node *current = head;
    while (current != NULL) {
        if (current->data == value) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}