Data Structure and Algorithm

/********* Singly Linked List **********/

#include "iostream.h"
#include "conio.h"

struct Linked_List //Structure to Represent Linked List
{
 int info;
 struct Linked_List *next,*head;
};

typedef Linked_List list; //Now list represent Linked List

list *New; //Global Variable of type list

void create(int ITEM) //Function to create a node of a list
{
 New = new list; //create a node
 New -> info = ITEM; //insert Item
 New -> next = NULL; //Assign next to NULL
}

void insert(int ITEM,int loc,list *&lst) //Function to insert Item on list
{
 if(loc <= 0) //Location must start from 1
  {
   cout << "\nInvalid Location";
   getch();
   return; //Exit from Function
  }

 if(loc == 1)
  {
   if(lst == NULL) //If List Doesn't Exist
    {
     lst = new list; //Create a list
     lst -> info = ITEM; //Copy Item to Node
     lst -> next = NULL; //Assign next to NULL1
     lst -> head = lst; //Update Head
    }

   else
    {
     create(ITEM); //Create a Node
     New -> next = lst -> head; //Link New node at First of head
     lst -> head = New; //Update Head of List
     lst = lst -> head;
    }
  }

 else
  {
   list *lptr = lst -> head; //Start from beginning of List
   for(int i = 2;i < loc;i++) //From Second node to seconlast node
    {
     lptr = lptr -> next; //Move the Pointer
     if(lptr == NULL)
      {
       cout << "\nInvalid Location";
       getch();
       return;
      }
    }

  create(ITEM); //Create a Node
  New -> next = lptr -> next; //Update next of New Node
  lptr -> next = New; //Assign New to next of lptr
 }
}

/*
Function to remove a node
 1. From Beginning
 2. Inbetween 2 Nodes
*/

list* remove(int ITEM,list *&lst)
{
 list *lptr = lst,*loc,*deleted;
 if(lptr -> info == ITEM) //If first item to be Deleted
  {
   lst = lst -> next; //Move lst
   lst -> head = lst; //Update head
   return lptr; //return deleted Node
  }

 //Find Item
  loc = lptr;
  lptr = lptr -> next;
  while(lptr -> next != NULL)
   {
    loc = lptr;
    lptr = lptr -> next; //Move lptr
    if(lptr -> info == ITEM) //if Item is found
     break; //Break from Loop
    loc = NULL; //Item not Found
   }

 if(loc != NULL) //if Item found
 {
  //delete Item
  deleted = loc -> next;
  loc -> next = loc -> next -> next;
  return deleted; //return Deleted
 }

 else
  return NULL; //Item not Found
}

void display(list *lst) //Function to Display elements of List
{
 list *temp = lst;
 cout << temp -> info << ' '; //Print First Item
 while(temp -> next != NULL) //Until Last
  {
    temp = temp -> next; //Move temp
    cout << temp -> info << ' '; //Print Item
   }
}

int main()
{
 list *l = NULL,*temp;
 int n = 0,i = 1;
 cout << "Enter Numbers\n";
 cout << "Input -999 to Stop\n";
 while(n != -999) //scan Input until user enters -999
  {
   cin >> n;
   if(n != -999)
  insert(n,i++,l); //insert Item on List
  }

 cout << endl << "List Created : ";
 display(l); //display List l
 cout << endl << endl;

 cout << "Delete : ";
 cin >> n;
 temp = remove(n,l); //Delete Node from List l
 if(temp != NULL)
  {
   cout << "\nDeleted : " << temp -> info << endl; //Print Deleted Node
   cout << "Data on List : ";
   display(l); //Print Current Elements of List
  }

 else
  cout << "\nData Not Found";

 getch();
 return 0;
}