#include <stdio.h>

// make sure you handle errors with deleting nodes from an empty list etc

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

struct LinkedList {
	struct Node *first;
};

struct LinkedList * createList() {
	struct LinkedList * list;
	list = malloc( sizeof(struct LinkedList));
	list->first = NULL;
	return list;
}

struct Node * makeNode(int data) {
	struct Node * new_node;
	new_node = malloc( sizeof(struct Node));
	new_node->data = data;
	new_node->next = NULL;
	return new_node;
}

void insertNodeFirst(int data, struct LinkedList * list) {
	struct Node * new_node = makeNode(data);
	new_node->next = list->first;
	list->first = new_node;
	return;
}

void insertNodeMiddle(int data, int location, struct LinkedList * list) {
	struct Node * previous;
	struct Node * temp;
	struct Node * toInsert = makeNode(data);
	int index = searchList(location, list);
	int count;

	if (index == 0) {
		insertNodeFirst(data, list);
		return;
	}
	previous = list->first;
	for (count = 0; count < index; count++) {
		previous = previous->next;
	}
	temp = previous->next;
	previous->next = toInsert;
	toInsert->next = temp;
	return;
}


void insertNodeLast(int data, struct LinkedList * list) {
	struct Node * new_node = makeNode(data);
	struct Node * temp;
	if(list->first == NULL) {
		insertNodeFirst(data, list);
		return;
	}
	temp = list->first;
	while (temp->next != NULL) {
		temp = temp->next;
	}
	temp->next = new_node;
	return;
}

void printList(struct LinkedList * list) {
	struct Node * p;
	printf("Printing updated list:\n");
	for (p = list->first; p != NULL; p = p->next) {
		printf("Data: %d\n", p->data);
	}
	return;
}

void deleteNodeFirst (struct LinkedList * list) {
	struct Node * temp;
	temp = list->first;
	list->first = temp->next;
	free(temp);
}

void deleteNodeLast(struct LinkedList * list) {
	struct Node * temp;
	temp = list->first;
	while ((temp->next)->next != NULL) {
		temp = temp->next;
	}
	temp->next = NULL;
}

void deleteNodeMiddle(int data, struct LinkedList * list) {
	struct Node * previous;
	int index = searchList(data, list);
	int count;

	if (index == 0) {
		deleteNodeFirst(list);
		return;
	}
	previous = list->first;
	for (count = 0; count < index - 1; count++) {
		previous = previous->next;
	}
	previous->next = (previous->next)->next;
}

void deleteList(struct LinkedList * list) {
	struct Node * temp;
	while (list->first != NULL) {
		temp = list->first;
		list->first = temp->next;
		free(temp);
	}
return;
}

// return index of first node with the required data
int searchList(int data, struct LinkedList * list) {
	int count = 0;
	struct Node * temp;
	temp = list->first;
	while (temp != NULL) {
		if (temp->data == data) return count;
		temp = temp->next;
		count++;
	}
	return count;
}

int main() {

	struct LinkedList * list = createList();
	insertNodeLast(5, list);
	insertNodeFirst(6, list);
	insertNodeFirst(5, list);
	insertNodeFirst(4, list);
	insertNodeFirst(3, list);
	insertNodeFirst(2, list);
	insertNodeFirst(1, list);
	insertNodeMiddle(999, 3, list);
	printList(list);
	deleteNodeFirst(list);
	insertNodeLast(2, list);
	printList(list);
	printf("The node with 4 has index %d\n", searchList(4, list));
	deleteNodeLast(list);
	deleteNodeMiddle(6, list);
	printList(list);
	deleteList(list);
	printList(list);

	return 0;
}