Chapter 2: Basic Abstract Data Types. Problem 2.2.b

//implement a list as linked list

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void Delete(NODE** head, int elemToDelete); 
void CreateList(NODE** head); 
void PrintList(NODE* head); 
void Insert( NODE** head, int elemToInsert); 

void main()
{
    NODE* head = NULL; 
    CreateList(&head); 
    PrintList(head);
    Insert(&head, 0);
       Insert(&head, 11); 
    PrintList(head); 
    Delete(&head,0); 
    Delete(&head, 11);
    Delete(&head, 4);
    PrintList(head); 
}

void CreateList(NODE** head)
{
    if( !head )
        return;
    
    NODE* current = *head;
    for( int i = 1; i < 11; i++ )
    {
        NODE* newNode = new NODE;
        if( !newNode )
            return;
        newNode->nValue = i;
        newNode->next = NULL; 

        if( current == NULL )
        {
            //first node
            current = newNode;
            *head = current;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }
}

void PrintList(NODE* head)
{
    if( !head )
        return;

    cout << "List is --> " << endl;
    for( NODE* current = head; current != NULL; current = current->next )
        cout << "[" << current->nValue << "]" << endl;
}

void Insert( NODE** head, int elemToInsert )
{
    if( !head )
        return; 

    NODE* prev = NULL; //this points to the element after which we need to insert the element. 
    NODE* current = *head;
    for( ; current != NULL; current = current->next )
    {
        if( current->nValue > elemToInsert )
            break;
        else
            prev = current;
    }

    NODE* newNode = new NODE; 
    newNode->nValue = elemToInsert;
    newNode->next = NULL; 

    if( prev == NULL )
    {
        //we need to insert the element at the head of the list
        newNode->next = *head; 
        *head = newNode;
    }
    else
    {
        //we need to insert the element after prev
        NODE* temp = prev->next; 
        prev->next = newNode;
        newNode->next = temp; 
    }
}

void Delete(NODE** head, int elemToDelete)
{
    if( !head )
        return;

    NODE* prev = NULL; 
    NODE* current = *head;

    for( ;current != NULL; current = current->next )
    {
        if( current->nValue == elemToDelete )
            break;
        else
            prev = current;
    }

    if( current == NULL )
    {
        //element not found.. nothing to be deleted. 
        cout << "element not found" << endl;
    }
    else
    {
        //current points to the element that needs to be deleted.
        //prev points to the one before current
        if( prev == NULL )
        {
            //head node needs to be deleted
            *head = (*head)->next; 
        }
        else
        {
            prev->next = current->next;
        }
        delete current;
    }
}