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

typedef struct node
{
    int data;
    struct node *next;
} NODE;

//Create a new node using malloc and return the pointer to it
NODE * CreateNode(int newdata){
	
   NODE * newnode;
   newnode = (NODE *) malloc (sizeof(NODE));
   if (newnode == NULL){
   
      printf ("No Memory left !!\n");
      return NULL;
	  
   }
   newnode->data = newdata;
   newnode->next = NULL;

   return newnode;
}

//Insert a new node (newdata) at the end of the linked list
void Insert(NODE ** headPtr, NODE * newdata){
	
	NODE *curr;
	
	if ((*headPtr) == NULL) {
		*headPtr = newdata;
		return;
	} else {
		curr = (*headPtr);
		while(curr->next != NULL){
			curr = curr->next;
		}
		curr->next = newdata;
	}
}

//Delete a node (containing data rmdata) and free it
int  Delete(NODE ** headPtr, int rmdata){

  NODE * temp, *prev, *curr;
  
  if ((*headPtr) == NULL){
   
     printf("No deletion in an empty list !!\n");
     return 1;
	  
  } else if ( (*headPtr)->data == rmdata ){ // If the node is at the beginning of the list
   
     temp = *headPtr;
     *headPtr = (*headPtr)->next;
     free (temp); //Make sure you call free temp !
	 
     return 0;
	  
  }else{ // Traverse the list to find the node 
	
	 //Set the prev and curr pointers to point to the first and second elements in the list
     prev = *headPtr;
     curr = (*headPtr)->next;
	  
     // Traversal of list here 
     while (curr != NULL && (curr)->data != rmdata ){
	  
        prev = curr;
        curr = curr->next;
		 
     }
     if(curr != NULL){ //Delete the node based on the position found in the while loop
	  
       temp = curr;
       prev->next = curr->next;
       free(temp); //Make sure you call free temp !
       return 0;
		
     }
     else{
	  
       printf("Node wasn't found !!\n");
       return 1;
		
     }
  } 
}

//Print the linked list starting with the node pointed to by the head
void PrintList(NODE * head){

   NODE * curr;
   if (head == NULL)
   {
      printf ("Empty List !!\n");
   }
   else
   {
      //curr points to the first node in the list
      curr = head;
      printf("List of nodes: ");
      while (curr != NULL)
      {
          printf("%d ", curr->data);
          curr = curr->next; //Move to the next node
      }
	  
      printf("\n");
   }
   
}   

int main(){

    NODE * head, *temp;
    int data,i,num = 3;
	//num is an optional variable which specifies the number of nodes to be created initially
	
    // Initialize the linked list
    head = NULL;

    // Create a few nodes
	for(i=0;i<num;i++){
		printf("\nEnter the data to be inserted : ");
		scanf("%d", &data);
		temp = CreateNode(data);
		Insert (&head, temp);
	}
	
	//Print out the list
    PrintList(head);

    // Deletion of a node
	
    printf("\nEnter the data to be deleted : ");
    scanf("%d", &data);
    if(!Delete(&head, data))
		printf("Data %d was deleted !!\n", data);
		
	//Print out the list
    PrintList(head);


    return 0;
}