/*
Let the user type in positive numbers, not necessarily unique.  Store them in
ascending order in a dynamically allocated doubly linked list.  The smallest
number will be at the head of the list, and the biggest number at the tail.
Then print the list from head to tail and from tail to head.

Each number is stored in a structure called a node_t.  Each node is malloc'ed
separately.  The variable head holds the address of the first node, or is NULL
if there are no node's yet.  The variable tail holds the address of the last
node, or is NULL if there are no nodes yet.

The next field of each node holds the address of the next node, or is NULL if
there is no next node.  The prev field of each node holds the address of the
previous node, or is NULL if there is no previous node.  The 0 that the user
types in to terminate the input is not stored in the list.
*/

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

typedef struct node_t {
	int n;	/* the number */
	struct node_t *prev;	/* the address of the previous node */
	struct node_t *next;	/* the address of the next node */
} node_t;

int main()
{
	node_t *head = NULL;
	node_t *tail = NULL;
	node_t *new;	/* the new node that the user typed in */
	node_t *p, *q;	/* for looping through the list */
	int n;	/* each number that the user types in */

	printf(
	"Please type positive numbers.\n"
	"Press RETURN after each number.\n"
	"Type a negative number to delete the corresponding positive number.\n"
	"Type 0 when done.\n"
	);

	for (;;) {
		scanf("%d", &n);
		if (n == 0) {
			break;
		}

		if (n > 0) {	/* Insert a new node (four cases). */
			new = malloc(sizeof(node_t));
			if (new == NULL) {
				fprintf(stderr, "Can't allocate %lu bytes.\n", sizeof(node_t));
				return EXIT_FAILURE;
			}
			new->n = n;
			if (head == NULL) {
				/* Case 1: the list was empty. */
				new->next = new->prev = NULL;
				head = tail = new;
			}

			else if (n < head->n) {
				/* Case 2: insert new at the head of the list. */
				new->next = head;
				new->prev = NULL;
				head->prev = new;
				head = new;
			}

			else if (new->n >= tail->n) {
				/* Case 3: insert new at the tail of the list. */
				new->prev = tail;
				new->next = NULL;
				tail->next = new;
				tail = new;
			}

			else {
				/* Case 4: insert new into the interior of the list.
				Search the list to find the insertion point. */
				for (p = head; (q = p->next) != NULL; p = p->next) {
					if (q->n >= n) {
						break;
					}
				}

				/* Insert new between the nodes that p and q point to. */
				new->next = q;
				new->prev = p;
				p->next = new;
				q->prev = new;
			}
		}

		else {	/* Delete an existing node. */
			n = -n;

			/* Let p point to the node to be deleted. */
			for (p = head; p != NULL; p = p->next) {
				if (p->n == n) {
					goto found;
				}
			}
			fprintf(stderr, "The number %d is not on the list.\n", n);
			continue;

			found:;
			if (p == head) {	/* Delete the first node. */
				head = p->next;
			} else {
				p->prev->next = p->next;
			}

			if (p == tail) {	/* Delete the last node. */
				tail = p->prev;
			} else {
				p->next->prev = p->prev;
			}

			free(p);
		}
	}

	printf("Print the list from head to tail:\n");
	for (p = head; p != NULL; p = p->next) {
		printf("%d\n", p->n);
	}

	printf("\nPrint the list from tail to head:\n");
	for (p = tail; p != NULL; p = p->prev) {
		printf("%d\n", p->n);
	}

	return EXIT_SUCCESS;
}