// Arup Guha
// 7/27/2020
// Solution to 2020 Summer COP 3502 Final Exam Part A Q2

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

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

node* insert(node* front, int val);
int countInListRec(node* listPtr, int value);
int countInList(node* listPtr, int value);
void freeList(node* list);

int main(void) {

    // Here is a test.
    node* list = NULL;
    list = insert(list, 6);
    list = insert(list, 8);
    list = insert(list, 7);
    list = insert(list, 8);
    list = insert(list, 8);
    list = insert(list, 10);
    list = insert(list, 8);
    list = insert(list, 9);
    printf("%d\n", countInListRec(list, 8));
    printf("%d\n", countInList(list, 8));
    freeList(list);
    return 0;
}

// Recursive version.
int countInListRec(node* listPtr, int value) {

    // No items in empty list.
    if (listPtr == NULL) return 0;

    // Sets res to 0 or 1 depending on if value is at first node.
    int res = 0;
    if (listPtr->data == value) res = 1;

    // Recursively add in the rest of the list.
    return res + countInListRec(listPtr->next, value);
}

// Iterative version.
int countInList(node* listPtr, int value) {

    // Initial counter.
    int res = 0;

    // Go thorugh the list.
    while (listPtr != NULL) {

        // See if we want to count it and do so, if necessary.
        if (listPtr->data == value)
            res++;

        // Go to the next item.
        listPtr = listPtr->next;
    }

    // Ta da!
    return res;
}

// Insert to front.
node* insert(node* front, int val) {
    node* tmp = malloc(sizeof(node));
    tmp->data = val;
    tmp->next = front;
    return tmp;
}

// Frees the dynamically allocated memory for all nodes in list pointed to by list.
void freeList(node* list) {
    if (list != NULL) {
        freeList(list->next);
        free(list);
    }
}