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

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

	node *createNode(int data);
	node *addNode(node *head, int data);
	int dataExists(node *head, int target);
	node *deleteNode(node *head, int target);
	void printList(node *head);
	void printReversedList(node *head);
	void printOptions();

	// Initialize node
	node *createNode(int data) {
		node *n = malloc(sizeof(node));
		n->data = data;
		n->next = NULL;
		n->prev = NULL;
		return n;
	}

	// Returns head of linked list
	// If no nodes exist in linked list, return new node as head
	// Otherwise, append node at end of list and return head
	node *addNode(node *head, int data) {
		node *n = createNode(data);
		if (!head)
			return n;

		// Function must return head, so temp pointer must
		// be used to traverse list to preserve head of list
		node *temp = head;
		while (temp->next)
			temp = temp->next;

		temp->next = n;
		n->prev = temp;
		return head;
	}

	// Return 1 if data exists in list
	// Returns 0 otherwise
	int dataExists(node *head, int target) {
		// No need to preserve pointer to head when traversing here
		while (head) {
			if (head->data == target)
				return 1;
			head = head->next;
		}
		return 0;
	}

	// Deletes and frees first instance of target in list if it exists
	// Return head after deletion
	node *deleteNode(node *head, int target) {
		// If list is empty, return head
		if (!head)
			return head;

		// Store head in temp to either delete head if target found at head
		// or to be used to maintain head pointer while traversing list
		node *temp = head;

		// Target found at head of list
		if (head->data == target) {
			head = head->next;
			free(temp);
			if (head)
				head->prev = NULL;
			return head;
		}

		// Traverse list, stop if at end of list or next node contains target
		while (temp->next && temp->next->data != target)
			temp = temp->next;

		// If reached end of list, no target found, return head
		if (!(temp->next))
			return head;

		// Reaching here indicates that next node contains target
		node *delNode = temp->next;
		temp->next = temp->next->next;
		if (temp->next)
			temp->next->prev = temp;
		free(delNode);

		return head;
	}

	// Free all nodes in list
	void freeList(node *head) {
		node *next;
		while (head) {
			next = head->next;
			free(head);
			head = next;
		}
	}

	// Prints all nodes from list
	void printList(node *head) {
		if (!head)
			printf("List is empty");
		while (head) {
			printf("%d -> ", head->data);
			head = head->next;
		}
		printf("\n");
	}

	// Prints all nodes from list
	void printReversedList(node *head) {
		if (!head) {
			printf("List is empty\n");
			return;
		}
		while (head->next)
			head = head->next;

		while (head) {
			printf("%d <-", head->data);
			head = head->prev;
		}
		printf("\n");
	}

	// Print options menu
	void printOptions() {
		printf("1) Add data to list\n");
		printf("2) Delete data from list\n");
		printf("3) Check if data is in list\n");
		printf("4) Print list\n");
		printf("5) Print reverse list\n");
		printf("6) Quit\n");
		printf("\n:");
	}

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

		int choice = 0;
		int data;

		while (choice != 6) {
			printOptions();
			scanf("%d", &choice);

			switch (choice) {

			case 1: // Add data
				printf("Enter an integer to add to list\n:");
				scanf("%d", &data);
				head = addNode(head, data);
				printf("%d added to list\n", data);
				break;

			case 2: // Delete data
				printf("Enter an integer to delete from list\n:");
				scanf("%d", &data);
				if (dataExists(head, data)) {
					head = deleteNode(head, data);
					printf("%d deleted\n", data);
				} else
					printf("%d is not in list\n", data);
				break;

			case 3: // Does data exist?
				printf("Enter an integer to check if it exists in the list\n:");
				scanf("%d", &data);
				printf("%d is %sin list\n", data, dataExists(head, data) ? "" : "NOT ");
				break;

			case 4: // Print List
				printList(head);
				break;

			case 5: // Print Reversed List
				printReversedList(head);
				break;

			default:
				break;
			}
			printf("\n");
		}

		freeList(head);

		return 0;
	}