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

typedef struct Node
{
	int data;	// data of a node: list is made of these elements
	struct Node *next;	// link to the next node
} node;

node *create_node(int val)
{
	node *n;
	n = malloc(sizeof(node));
	n->data = val;
	n->next = NULL;
	return n;
}

void print_list(node *h)
{
	node *p;
	p = h;
	while (p != NULL)
	{
		printf("%d --> ", p->data);
		p = p->next;
	}
	printf("NULL\n");
}

int main()
{
	node *head = NULL;	// head maintains the entry to the list
	node *p = NULL, *q = NULL;
	int v = -1, a;

	printf("Inserting at end\n");

	scanf("%d", &v);
	while (v != -1)
	{
		q = create_node(v);
		if (head == NULL)
			head = q;
		else
		{
			p = head;
			while (p->next != NULL)
				p = p->next;

			p->next = q;
		}
		scanf("%d", &v);
	}

	print_list(head);

	printf("Inserting at beginning\n");

	scanf("%d", &v);
	while (v != -1)
	{
		q = create_node(v);
		q->next = head;
		head = q;
		scanf("%d", &v);
	}

	print_list(head);

	printf("Inserting after\n");

	scanf("%d", &v);
	while (v != -1)
	{
		q = create_node(v);

		scanf("%d", &a);
		p = head;
		while ((p != NULL) && (p->data != a))
			p = p->next;

		if (p != NULL)
		{
			q->next = p->next;
			p->next = q;
		}

		scanf("%d", &v);
	}

	print_list(head);

	printf("Deleting from end\n");

	if (head != NULL)
	{
		p = head;
		while (p->next != NULL)
		{
			q = p;
			p = p->next;
		}

		q->next = NULL;
		free(p);
	}

	print_list(head);

	printf("Deleting from beginning\n");

	if (head != NULL)
	{
		p = head;
		head = head->next;
		free(p);
	}

	print_list(head);

	printf("Deleting after\n");

	scanf("%d", &a);
	p = head;
	while ((p != NULL) && (p->data != a))
		p = p->next;

	if (p != NULL)
	{
		q = p->next;
		if (q != NULL)
		{
			p->next = q->next;
			free(q);
		}
	}

	print_list(head);

}