// sample program with insertion and deletion on a sorted linked list

#include <iostream>

using namespace std;

struct NodeType
{
        int i;
        NodeType *Next;
};

NodeType *Head;

void Initialize ()
{
        Head = NULL;
}

void Output ()
{
        NodeType *p = Head;
        while (p != NULL)
        {
                cout << p->i << "\n";
                p = p->Next;
        }
}

void InsertSorted ( NodeType *n )
{
	if ((Head == NULL) || (Head->i > n->i))	 // insertion at first position
	{
		n->Next = Head;
		Head = n;
	}
	else									// insertion after first position
	{
		NodeType *p = Head;					// find position in list
		while ((p->Next != NULL) && (p->Next->i < n->i)) 
			p = p->Next;
		n->Next = p->Next;					// relink list
		p->Next = n;
	}
}

// search a linked list for the node before the one containing a specified value
// note: this function assumes the existence of at least one node
NodeType *Search ( int x )
{
	NodeType *p = Head;
	while ((p->Next != NULL) && (p->Next->i != x))
		p = p->Next;
	return p;
}

void DeleteByValue ( int x )
{
	if (Head == NULL)		// empty list
		return;
	else if (Head->i == x)	// found at first node 
	{
		NodeType *p = Head->Next;
		delete Head;
		Head = p;
	}
	else					// after first node
	{
		NodeType *p = Search (x);	// find ptr to node before
		if (p->Next == NULL)		// do nothing if value is not found
			return;
		NodeType *t = p->Next;		// relink pointers
		p->Next = t->Next;
		delete t;					// delete old node
	}
}

int main ()
{
        Initialize ();

        NodeType *aNode;

        aNode = new NodeType;
        aNode->i = 4;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 1;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 7;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 3;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 6;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 5;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 8;
        InsertSorted (aNode);

        aNode = new NodeType;
        aNode->i = 2;
        InsertSorted (aNode);
     
	Output ();
	cout << "\n\n";

	DeleteByValue (3);
	DeleteByValue (8);
	DeleteByValue (10);
	DeleteByValue (-1);
	DeleteByValue (1);

	Output ();

        return 0;
}