how to restrict base class from inheritance!!

In CPP there is a way to restrict the base class from Inheritance. That means , Base class will not allow to create the new derived classes. We can achieve this by making constructor private in the class.
How it works: The basic logic behind this is C++ class access specifier. Derived classes are not allowed to access the private data of the base class. So to create the instance/object of the derived class, it needs base class constructor. So if you make base constructor private, when derived class trying to access the base constructor, it will fail. See the sample code below.

#include<iostream>
using namespace std;

class base
{
//public:
    base()
    {
        cout<<"base constructor\n";
    }
};

class derive:base
{
public:
    derive()
    {
        cout<<"derived constructor\n";
    }
};

main()
{
    derive d;
}

In the above code,  In the base class construtor is private and we derived a new class derive. It looks good till now. But the problem is in main() where we created the instance/object of the derive class. Because of base constructor is private, it will throw the below error.

restrict.cpp: In constructor 'derive::derive()':
restrict.cpp:7: error: 'base::base()' is private
restrict.cpp:17: error: within this context

Printing source code of the program itself in C!!

The concept of printing the source code of the program itself is called quine. Here we will see the implementatin of printing source code of the program in C language.

How it works: As quine concept says, to implement this, we need to see the whole program in two parts like code and data where data is the textual form of code. So most cases data is the code which placed between the quotes. Below is the simple C program to print source code.

main()
{
char str[]="main(){ char str[]=%c%s%c;printf(str,34,str,34);}";
printf(str,34,str,34);
}

OutPut:
main(){ char str[]="main(){ char str[]=%c%s%c;printf(str,34,str,34);}";printf(str,34,str,34);}

Explaination: As we have seen above, it should be devided into two parts like code and data. So here value of the character array str is data which is placed between the double quotes. And remaining is code. For displaying that data, we need to use printf() function.Here comes the trick, for displaying double quotes("), we used equivalent ASCII value 34. and we are done. So for printf, first str from left is replaced with data, 34 is for quotes, another str is for variable and 34 for quotes. Final printf internally looks like below.

printf("main(){ char str[]=%c%s%c",34,str,34);

Here the output displayed in one single line. If you want next line, just add '%c'  to the string data and ASCII value of the new line (10) to the printf() function. Below is the C Program for that.

#include<stdio.h>
main()
{
char str[]="#include<stdio.h<%cmain()%c{ %cchar str[]=%c%s%c;%cprintf(str,10,10,10,34,str,34,10,10,10);%c}%c";
printf(str,10,10,10,34,str,34,10,10,10);
}

Output:

#include<stdio.h>
main()
{
char str[]="#include<stdio.h<%cmain()%c{ %cchar str[]=%c%s%c;%cprintf(str,10,10,10,34,str,34,10,10,10);%c}%c";
printf(str,10,10,10,34,str,34,10,10,10);
}

How to test it: How to know that, whether your program is generating exact source code or not.Just execute it and get the output in new C file. Compile that C file, if it executes successfully, your program is working and generating source code of the program itself.

what is quine?

A quine is a computer program which takes no input and produces a copy of its own source code. That means, when you run the program, it should print exactly those lines which written by programmer in that program. These programs are also called self-replicating programs, self-reproducing programs, and self-copying programs.

How quine works: To implement this , we need to see the program in two parts, one is code and another is data. And data represents the textual form of the code(like placing code between quation marks). This is similar to "say 'say'" where first say is code and second say in quotes is data.
 
Implementation of the quine's concept completely depends on the programming language instructions. It may not be possible to impelement in some programming languages, mostly in all programming languages you can implement quine. Here is the quine implementation in C language.

Print 1 to n with out conditional statement !!

Here we will see how to print 1 to n numbers with out using any loop(for or while) and with out using any if statement in C. I already posted on post on with out using loop but used conditional statement like if statement. In this post I will explaing with out using conditionla statement as well.

How it works: Printing N times can be achieved by repeated calling function by using recursion or by calling main() function as specified here. But stoping that calling function is important here. To stop calling main() function we need some termination condition. So to terminate it, we will use logical AND (&&) operation. The basic concept of AND operation is , if the first value(here it is 10-count) is false, it wont go for the second value. So main() function will be called until first value becomes zero.
Algorithm:

1. Get the global variable or static variable with one
2. print the value
3. increment the global varaible
4. do AND operation (on N+1-count) and main() function.

C Program:

#include<stdio.h>

int count=1;
main()
{
    printf("Number %d\n",count);
    count++;
    (11-count)&& main();
}

Explaination: We used the global variable count (you can also use static variable instead of global), and it is initialised to one. Because here we want to display from 1 to 10 numbers. And then main() starts , there we are printing the value of count and incrementing the count. And here comes the trick, for repeated printing we are calling main() function and for stoping this, we used logical AND operation. In AND operation we used 11-count , this statement becomes zero when the count value is 11 and eventually logical AND operation becomes false and it wont call the main() function. And stop calling the main() function.

Print n times with out using loop C program!!!

Here I will explain how to do this.The basic idea is repeatedly calling print function. So solution lies in the previous statement itself . i.e repeatedly calling the function. And use one global variable to maintain the count. We can do this in two ways.

• Recursive method
• Non-recursive method

Recursive method: Most important part in recursive function is termination condition. So to break the recursive  function, just use the global variable (here it is n). If the n value matches required value(here it is 10 ), stop calling and return. other wise increment global value and call the function. That's it. Below is the C Code.

int n=0;
void print()
{
    printf("%d\n",n);
    if(n==10)
        return;
    n++;
    print();
}
int main()
{
    print();
}

In the above C program, we are calling user defined function print(). To terminate that process we are using one global variable n,  and we are checking global variable and if it reaches the required value, we are terminating the process.

Non-recursive method: This is similar to recursive method only, but the difference is instead of calling user defined function, just call main() function itself. And the remaining logic is same like maintaining the global variable and termination condition. C code is given below.

int x=0;
int main()
{
    if(x==10)
        return 0;
    x++;
    printf("%d\n",x);
    main();
}

AVL Tree C program!!!

Below is C program for AVL Tree implementation.

#include<stdio.h>
#include<malloc.h>

typedef struct bst
{
 int info;
 int height;
 struct bst *left;
 struct bst *right;
}NODE;

typedef NODE* ROOT;

/*********************************
for setting/updating the height of the tree at each node
*************************************/
int set_height(ROOT r)
{
 int left_h = -1;
 int right_h = -1;
 if(r->left)
  left_h = r->left->height;
 if(r->right)
  right_h = r->right->height;
 if(left_h >= right_h)
  r->height = left_h+1;
 else
  r->height = right_h+1;
 return r->height;
}

/*********************************
return -1 if data1 is less than data2 
return 1 if data1 is greater than data2 
returns zero on equal
*************************************/
int compare(int data1, int data2)
{
 if(data1<data2)
  return -1;
 if(data1>data2)
  return 1;
 else
  return 0;
}

/*******************************
Doing Left-Left rotation
*******************************/
void rotate_LL(ROOT *r)
{
 NODE *r1, *r2 = *r,*t1,*t2,*t3;

 r1 = r2->left;
 t1 = r1->left;
 t2 = r1->right;
 t3 = r2->right;

 //actual rotation happens here
 r1->right = r2;
 r2->left = t2;

 // update the r1 , r2 height
 set_height(r1);
 set_height(r2);

 *r = r1;
}

/*******************************
Doing Right-Left rotation
*******************************/
void rotate_RL(ROOT *r)
{
 NODE *r1,*r2, *r3=*r,*t1,*t2,*t3,*t4;

 r1 = r3->left;
 r2 = r1->right;
 t2 = r2->left;
 t3 = r2->right;

 // actaul rotatiosn happens here
 r1->right = t2;
 r3->left = t3;
 r2->left = r1;
 r2->right = r3;

 //updte the new heihts for r1, r2, r3
 set_height(r1);
 set_height(r2);
 set_height(r3);

 *r = r2; 
}

/*******************************
Doing Left-Right rotation
*******************************/
void rotate_LR(ROOT *r)
{
 NODE *r1=*r, *r2,*r3,*t1,*t2,*t3,*t4;

 r3 = r1->right;
 r2 = r3->left;
 t2 = r2->left;
 t3 = r2->right;

 // actaul rotatiosn happens here
    r1->right = t2;
    r3->left = t3;
    r2->left = r1;
    r2->right = r3;

    //updte the new heihts for r1, r2, r3
    set_height(r1);
    set_height(r2);
    set_height(r3);

    *r = r2;
}

/*******************************
Doing Right-Right rotation
*******************************/
void rotate_RR(ROOT *r)
{
 NODE *r1=*r,*r2,*t1,*t2,*t3;

 r2 = r1->right;
 t1 = r1->left;
 t2 = r2->left;
 t3 = r2->right;

    // actaul rotatiosn happens here
 r1->right = t2;
 r2->left = r1;

 set_height(r1);
 set_height(r2);
 
 *r = r2;
}

/********************************************
It will returns rotation type.
1. Left-Left (LL)
2. Right-Left(RL)
3. Left-Right(RL)
4. Right-Right(RR)
********************************************/
int find_rotation_type(int parent_data, int child_data, int data)
{
 if(compare(data, parent_data)<0) // inserting left
 {
  if(compare(data, child_data)<0)
   return 1;
  else if(compare(data, child_data)==0)
   return 0;
  else 
   return 2;

 }
 else //inserting right
 {
  if(compare(data, child_data)>0)
   return 4;
  else if(compare(data, child_data)==0)
   return 0;
  else 
   return 3;
 }
}

/********************************************
Calling the corresponding AVL-rotation method
********************************************/
void do_rotation(ROOT *r, int rotation_type)
{
 if(rotation_type == 1)
  rotate_LL(r);
 else if(rotation_type == 2)
  rotate_RL(r);
 else if(rotation_type == 3)
  rotate_LR(r);
 else if(rotation_type == 4)
  rotate_RR(r);
 else
  printf("invalid rotation type \n");
}
/************************************************************
Try to insert the elements 50,25,10,5,7,3,30,20,8,15.
This order will cover all four rotations
************************************************************/
int insert(ROOT *r, int data)
{
 NODE *new_node, *root = *r;
 int left_h = -1, right_h = -1;
 int diff,rotation_type;

 //tree is empty
 if(root == NULL)
 {
  new_node = (NODE *)malloc(sizeof(NODE));
  new_node->info = data;
  new_node->height = 0;
  new_node->left = new_node->right = NULL;
  *r = new_node;
  return 0;
 }
 if(root->left)
  left_h = root->left->height;
 if(root->right)
  right_h = root->right->height;

 if(compare(data, root->info)<0)
 {
  left_h = insert(&(root->left), data);
  rotation_type = find_rotation_type(root->info, root->left->info, data);
 }
 else if(compare(data, root->info)>0)
 {
  right_h = insert(&(root->right), data);
  rotation_type = find_rotation_type(root->info, root->right->info, data);
 }
 else
 {
  printf("Duplicate key!!\n");
  return -1;
 }

 diff = left_h-right_h;
 if(diff>1 || diff<-1)
 {
        printf("Tree is Un-Balanced at node data %d ", root->info);
        if(rotation_type == 1)
            printf("need to do LL rotation\n");
        if(rotation_type == 2)
            printf("need to do RL rotation\n");
        if(rotation_type == 3)
            printf("need to do LR rotation\n");
        if(rotation_type == 4)
            printf("need to do RR rotation\n");
        //this call is for doing rotation
        do_rotation(r,rotation_type);
        printf("rotation done successfully\n");
  root = *r;
 }
 //set the height for the node and return the height
 return set_height(root);
}

/**************************************
Printing In-Order traversal of AVL Tree
**************************************/

void print_inorder(NODE *root)
{
 NODE *temp = root;
 if(temp)
 {
  print_inorder(temp->left);
  printf("%d ",temp->info);
  print_inorder(temp->right);
 }
}

/**************************************
Printing Pre-Order traversal of AVL Tree
**************************************/

void print_preorder(NODE *root)
{
 NODE *temp = root;
 if(temp)
 {
  printf("%d ",temp->info);
  print_preorder(temp->left);
  print_preorder(temp->right);
 }
}

/**************************************
Printing Post-Order traversal of AVL Tree
**************************************/

void print_postorder(NODE *root)
{
 NODE *temp = root;
 if(temp)
 {
  print_postorder(temp->left);
  print_postorder(temp->right);
  printf("%d ",temp->info);
 }
}

int main()
{
 ROOT r = NULL;
 int i,num,data,choice;
 printf("enter the no. of elements\n");
 scanf("%d",&num);
 printf("Enter the elements\n");
 for(i=0;i<num;i++)
 {
  scanf("%d",&data);
  insert(&r,data);
 }
 printf("1. Insert\n2. In-order\n3. Pre-order\n4. Post-order\n5. Height of the tree\n other input for exit\n");
 printf("Enter the choice\n");
 scanf("%d",&choice);
 while(1)
 {
  switch(choice)
  {
   case 1:
     printf("Enter the element\n");
     scanf("%d",&data);
     insert(&r,data);
     break;
   case 2:
     printf("Inorder is \n ");
     print_inorder(r);
     printf("\n");
     break;
   case 3:
     printf("\nPreorder is \n ");
     print_preorder(r);
     printf("\n");
     break;
   case 4:
     printf("\nPostorder is \n ");
     print_postorder(r);
     printf("\n");
     break;
   case 5:
     //height of the root node height is heoght of the tree   
     printf("\nHeight of the tree is %d\n",r->height);
     break;
   default:
     return 0;
     break;
  }
  printf("1. Insert\n2. In-order\n3. Pre-order\n4. Post-order\n5. Height of the tree\n other input for exit\n");
  printf("Enter the choice\n");
  scanf("%d",&choice);
 }
}

AVL trees!!!

AVL (Adelson-Velskii and Landis scientists who found this tree) trees are balanced Binary search trees. All the operations like addition, deletion and searching in the worst case of O(log(n)).

What are AVL Trees: AVL trees are balanced binary search trees. A tree said to be balanced if the height of the left sub tree and right sub tree difference should be at most one at each node. i.e left sub tree and right sub tree difference should either 0, 1, -1.

Why AVL Trees: The problem with Binary Search Tree (BST) is that, if the given input values are in any sorted order(ascending or descending) the BST will be completely left or right as shown below. So Search will take worst case of O(n) where n is the no. of nodes in the BST.

Left skewed BST



Right skewed BST













 From the above images it is very clear that , BST is not advisable to construct for  sorted input values.

How to construct AVL Tree: Construction of AVL tree is same as Binary search tree, but the difference is after inserting the new node into the tree or deleting a node from the tree, again need to check each node for the balance. if the tree is not balanced, we need to re-structure  or rebuild the tree for balancing using rotation.

Algorithm for AVL Tree:
Step1: Get the element to insert into the tree.
Step2: if the tree is empty, make the node as root node.
Step3: If the tree is not empty, traverse the tree until it reaches NULL in such a way that
           if(element > node->element)
                      move node to node->right
           else if(element < node->element)
                     move node to node->left

Step4: After inserting check for the height of the node in Tree
Step5: If any node is not balanced, find the rotation type.
Step6: After doing the rotation, adjust the new heights of the rotated nodes
 
Example of the AVL Tree: Below is the AVL tree which satisfies Binary search tree property at each node and the difference between left sub tree height and right sub tree height is at most 1.

AVL Tree

Here is C Program for AVL trees.

K - Reverse linked list program

Below is the C code for reversing each k-elements in the linked list.
Example: for k value 3

Input:  1->2->3->4->4->5->6->7->8

Output: 3->2->1->6->5->4->8->7

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int info;
 struct node *next;
};

typedef struct node Node;

Node* append(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 if(info == 101) // this is for making the list circular
 newNode->next = h;
 return h;
// printf("temp -> info is %d\n",temp->info);
}


/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}

/*****************************************************************************
This function reverse each  K-nodes in the list. e.g for k=3
input:  1->2->3->4->4->5->6->7->8
result: 3->2->1->6->5->4->8->7
*****************************************************************************/
Node *kreverse(Node *head, int k)
{
 Node *temp_head,*new_head,*tail,*temp;
 int k_temp = k;
 new_head = head;
 head = head->next;
 new_head->next = NULL;
 tail = new_head;
 while(head && k_temp-1)
 {
  temp = head->next;
  head->next = new_head;
  new_head = head;
  head = temp;
  k_temp--;
 }
 k_temp = k;
 while(head)
 {
  temp = head->next;
  head->next = NULL;
  tail->next = head;
  temp_head = tail;
  tail = head;
  head = temp;
  while(head && k_temp-1)
  {
   temp = head->next;
   head->next = temp_head->next;
   temp_head->next = head;
   head = temp;
   k_temp--;
  }
  temp_head = tail;
  k_temp = k;
 }
 return new_head;
}

main()
{
 Node *head = NULL;
 int i;
 for (i=1;i<=20;i++)
 {
  head = append(head,i*10);
 }
 display(head);
 head =  kreverse(head,3);
 display(head);

}

Find nth element from last in linked list!!!

Finding nth element from last in a linked list is one of the common question in C/C++ interviews. Below are the steps to achieve this.
              Basically what we are going to do is taking two pointers temp and nthNode and make the difference between the two pointer should be 'n'. Now move both the pointers simultaniously until first pointer temp reaches NULL. At any point of time, the diffrenece between these two pointers is always 'n'. We need from last, so we are moving first node to end of the list.

• Take the first pointer temp and move it to 'n' nodes from starting.
• Take the second pointer nthNode and point it to starting of the list.
• Move both the pointers one by one until first pointer temp  reaches NULL
• Second pointer nthNode where it is pointing is the nth node from last



Input



result



Below is the C code snippet for finding the nth node from last.

Node *nthFrmLast(Node *h, int nthPos)
{
 Node *temp = h;
 Node *nthNode = h;
 if(h == NULL)
 {
  printf("list is empty\n");
  return NULL;
 }
 int i;
 for (i=0;i<nthPos;i++)  // repeating n times or moving nodes from start/head
 {
  if(nthNode == NULL) // if the postion is greater than the no. of elements in a list 
  {
   // the no. elements are  less than pos u enterred
   return nthNode;
  }
  else
   nthNode = nthNode->next;
 }
 while(nthNode!=NULL)
 {
  temp = temp->next;
  nthNode = nthNode->next;
 }
 return temp;

}

Here is the complete working C code for finding nth element from end in linked list.

Finding nth element from last in linked list C program!!

Below is the C code for finding nth element from last in a linked list. Here is the explanation to do this.

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

//linked list structure
struct node
{
 int info;
 struct node *next;
};

//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;

//inserting or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}

/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}


/*****************************************************************************
let me explain the concept first. for finding nth elemnt from back/end,
first we need take the temparory node(nthNode) and move it to nth position 
from start/head. then take the second temparary node(temp), and move both 
temparary nodes until first temparary node(nthNode) reaches end/NULL. and the 
postion where second temparary node(temp) points is the one nth postion from 
end/back.
*****************************************************************************/

Node *nthFrmLast(Node *h, int nthPos)
{
 Node *temp = h;
 Node *nthNode = h;
 if(h == NULL)
 {
  printf("list is empty\n");
  return NULL;
 }
 int i;
 for (i=0;i<nthPos;i++)  // repeating n times or moving nodes from start/head
 {
  if(nthNode == NULL) // if the postion is greater than the no. of elements in a list 
  {
   // the no. elements are  less than pos u enterred
   return nthNode;
  }
  else
   nthNode = nthNode->next;
 }
 while(nthNode!=NULL)
 {
  temp = temp->next;
  nthNode = nthNode->next;
 }
 return temp;

}


int main()
{
 Node *head = NULL;
 int i,pos;
 for (i=1;i<10;i++)
 {
  head = insert(head,i*10);
 }
 display(head);
 printf("Enter the position from last (value should be +ve)\n");
 scanf("%d",&pos);
 Node *tmp=nthFrmLast(head,pos);
 if(tmp)
  printf("%dth element from last is %d\n",pos,tmp->info);
 else
  printf("enter the pos less the list size\n");
}

Reverse linked list!!

Reverse linked list is the one of the most common question in C/C++ interview question. Generally we can do this in two ways.

• Recursive
• Non-Recursive

Here we will see the non-recursive method. In general for reversing, we need to go the end(in case of string) and do the process. But in Linked list, no need of going to the end of the list. See below for details.

• Separate the first node from the list and make a new list with firs node. Now we have new lists. one list with out the first node and new list with first node.
• add each node from the old list to the new list, repeat this until first list reaches null. Now we will have new list with reverse order.

Lets see this with example. Below is the input list, we will do the reverse of this list.

Input List

Splitting list into two lists: First we need to split the list into two lists in such a way that, new list is having only one node which is head node of the given input and another list is given input list with out first node.  To point head node of the new list we need to take the new pointer newHead which points to head node.  and then do below steps as shown in the figure.




Before

Step1 : Move the head pointer to the next node
Step2 : Assign newHead  next pointer to NULL.

After



 head = head ->next;
 newHead->next = NULL:

Inserting node at starting of the new list: To append each node from given list to new list we need to follow the below steps in order. Should not change the order. And take one new pointer temp which points to the head node.


Before

Step1: Move the temp node pointer to the next node.
Step2: Change the head next pointer to the newHead node.
Step3: Move newHead to the head position
Step4: Move head to the temp node.


After



temp=head->next;
head->next = newHead;
newHead = head;
head = temp;

Repeat above steps 1-4 till temp reaches NULL. And the result list is given below.

reverse list

Here is the C program to delete the node from a linked list.

deleting a node from linked list!!

Deleting a node in a linked list is little bit complex. There are three three cases we need to handle while doing delete operation.

• Empty list
• Deleting node is first node in the list (this is similar to deleting current node in the list)
• Deleting other than first node

The basic concept we need to understand while doing delete operation in single linked list that, there is no backward traversing in single linked list. We cant access the previous node. So we need to maintain current and next node and need to check the next node info field for matching. Lets see three cases one by one.

Empty List:  If we are trying to do deleting a node in the empty list. This will find out by check the head node NULL or not. If head node is NULL, it is an empty list so just return.
Deleting node is first node: If the deleting node is first node, there will be two cases. One is list contains only one node and another case is list contains more than one node. In first case we need to delete the node and make it that node as NULL, in another case where a list has more than single node, for this we need to follow the idea of deleting the current node in the list. sample code is given below.

head->info = head->next->info;
temp = head->next;
head->next = head->next->next;
free(temp);

Actually, here no node time temp, but to free the deleted memory, we need to use temp.
Deleting other than first node: Deleting a node is not a first node in the list. This is the general case. As mentioned above, need to maintain current and  next pointers. and check for the next pointer info field and find out the deleted node. see the C code snippet below.

while(h->next!=NULL)
 {
     if((h->next->info == info))
     {
             temp = h->next;
             h->next=h->next->next;
             free(temp);
   return;
     }
     h=h->next;
 }

Here is the complete working C code for deleting a node form linked list.

Deleting a node from linked list C program !!

Below is the complete working  C code for deleting a node from a linked list.

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

//linked list structure
struct node
{
 int info;
 struct node *next;
};

//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;

//inserting node or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}

//deleting a node from list. It has three cases
//1. empty list
//2. deleting first node in the list (this is similar to deleting current node in the list)
//3. other than first node 
void deleteNode(Node *head, int info)
{
 Node *h = head;
 Node *temp=NULL;
 // empty list
 if(h==NULL)
 {
  printf("Linked list is empty\n");
  return ;
 }
 // deleting node is first node in the list
 if(head->info == info)
 {
  // if list contains only single node
  if(head->next == NULL)
  {
   free(head);
   head = NULL;
  }
  else // list contains multiple nodes
  {
   head->info = head->next->info;
   temp = head->next;
   head->next = head->next->next; 
   free(temp);
   h = head->next;
  }
  printf("----------------- given %d element is deleted from the list----------------- \n",info);
  return ;
 }
 while(h->next!=NULL)
 {
  if((h->next->info == info))
  {
    temp = h->next;
    h->next=h->next->next;
    free(temp);
    printf("----------------- given %d element is deleted from the list----------------- \n",info);
   return;
  }
  h=h->next;
 }
 printf("-------------- %d is not in the list ------------\n",info);
 return ;
}

//deleting current node
void deleteCurrent(Node *current)
{
 current->info = current->next->info;
 current->next = current->next->next;
}

/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}

int main()
{
 Node *head = NULL;
 int i,n,element,choice,pos,size;
 for (i=1;i<7;i++)
 {
  head = insert(head,i*2);
 }
 display(head);
 printf("Enter the element to delete from the list\n");
 scanf("%d",&element);
 deleteNode(head,element);
 display(head);
}

strcmp implementation in C !!!

strcmp is another string library function which is used to compare two strings and returns zero if both strings are same , returns +ve value if first string is greater than second string and returns -ve value if second string is greater than first string.
How it works: Basically strcmp works in such a way that, it compares each character by character. i.e first character of the string with first character of the second string and second character of the string with second character of the second string etc. Like nth character of the first string with the nth character in the second string until it reaches end of any string. Here comparing character means comparing the ascii value of the character. When operators (+,-,<,>) applied to the characters, they will do operations on the ascii values.

strcmp implementation using arrays:

int strcmp_arry(char *src1, char *src2)
{
    int i=0;
    while((src1[i]!='\0') || (src2[i]!='\0'))
    {
        if(src1[i] > src2[i])
            return 1;
        if(src1[i] < src2[i])
            return -1;
        i++;
    }

    return 0;
}

strcmp implementation using pointers:

int strcmp_ptr(char *src1, char *src2)
{
    int i=0;
    while((*src1!='\0') || (*src2!='\0'))
    {
        if(*src1 > *src2)
            return 1;
        if(*src1 < *src2)
            return -1;
        src1++;
        src2++;
    }
    return 0;
}

Below is the complete working C code implementation for the strcmp string function.

#include<stdio.h>
#include<string.h>

//using arrays , need to move the string using index
int strcmp_arry(char *src1, char *src2)
{
    int i=0;
    while((src1[i]!='\0') || (src2[i]!='\0'))
    {
        if(src1[i] > src2[i])
            return 1;
        if(src1[i] < src2[i])
            return -1;
        i++;
    }

    return 0;
}
//using pointers, need to move the position of the pointer
int strcmp_ptr(char *src1, char *src2)
{
    int i=0;
    while((*src1!='\0') || (*src2!='\0'))
    {
        if(*src1 > *src2)
            return 1;
        if(*src1 < *src2)
            return -1;
        src1++;
        src2++;
    }
    return 0;
}

main()
{
    char amessage[] = "string";
    char bmessage[] = "string1";
    printf(" value is %d\n",strcmp_arry(amessage,bmessage));
    printf(" value is %d\n",strcmp_ptr(amessage,bmessage));
}

reverse linked list C Code!!

Below is the complete working C code for reverse linked list. Here is the detailed explaination of how to reverse the list.

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int info;
 struct node *next;
};

typedef struct node Node;

/*****************************************************************************
This function is used to create the new linked list or 
adding he new node at the end of the list.
*************************************************************************/

Node* append(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}


/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}

/*****************************************************************************
This function is used to reverse the given linked list. e.g
Input:  1->2->3->4->5->6->7
Output: 7->6->5->4->3->2->1
*****************************************************************************/
Node *reverseList(Node *head)
{
 Node *newHead,*temp;
 temp = head;
 newHead = head;
 if(newHead == temp)
 {
  temp=head->next;
  head = head->next;
  newHead->next = NULL;
 }
 while(head!=NULL)
 {
  temp=head->next;
  head->next = newHead;
  newHead = head;
  head = temp;
 }
 return newHead;
}


main()
{
 Node *head = NULL;
 int i;
 for (i=1;i<=10;i++)
 {
  head = append(head,i*10);
 }
 display(head);
 head =  reverseList(head);
 display(head);

}

delete singleton object in C++ !!

Singleton pattern is used to create only one instance of the class for the application. It will be usefull when you need global resource like Server. Creating the singleton is easy and there wont be any problem. But the problem is when to delete the singleton. It depends on the lifetime of the Singleton.

Method to create the Singleton:

single* single::getInstance()
{
    if(ptr==NULL)
    {
        ptr = new single();
    }
    else
    {
        return ptr;
    }
}

If you want to delete the singleton pointer, dont call the delete on the singleton pointer. Better use some static function like deleteInstance similar to getInstance which used to creat the singleton.

Method to delete the Singleton:

single* single::deleteInstance()
{
    delete ptr;
    ptr = NULL;
}

For single threaded environments it is advised to use a local static varible. So there is no need to use the delete operation. It wont be good for multi threaded environments.
Method to create the Singleton:

single* single::getInstance()
{
    static single sObj;
    return &sObj;
}

P.S:  Try to avoid the use of the Singleton as it is a global resource.

linked list intersection!!

Here we will see how to find the intersection or merge point of two linked lists. Assume that there are two linked lists List1 and List2. and List2 last node is pointing to the node some where in the List1 as shown below.

Here List2 last node with 35 is pointing to the node with value 50 in List1. This kind of problem may occur, when the programmer by mistake points end of the node in the list points to some other node instead of NULL. To solve this there are different ways. Given below are some of the solutions.

Basic method: This is brute force method.  Start from the List1 compare each node with each node in the List2. whenever a node in the List1 matches a node in the List2 . That is the merge or intersection node. here we are checking for node address and not the value.  Problem with this method is efficiency. It will take the time complexity O(n*m)  where n is the no.of nodes in List1 and m is the no.of nodes in List2. Below is the C code for this code.

Node* merge_point_basic_method(Node* h1, Node* h2)
{
    while(h1)
    {
        Node *tmp = h2;
        while(tmp)
        {
            if(h1 == tmp)
                return h1;
            tmp=tmp->next;
        }
        h1=h1->next;
    }
    return NULL;
}

Click here for the complete working C code for this method.

Using Node count: This method is the best method for this problem. Time complexity of this method is O(n+m).

• Get the no. of nodes in the List1
• Get the no. of nodes in the List2
• Take the difference between List1 count and List2 count as 'diff'
• traverse 'diff' nodes in the bigger List. Now the bigger list from this node and List2 are having the same no.of nodes.
• traverse both the lists parallelly and compare the nodes, if both nodes are equal that node is the merge node.

 Click here for the complete working C code for this method.

Using List Traversal: This is the another method for solving this poblem. First start traversing the List1 and make the visited flag each node to true. And then start traversing List2 and check for the visited flag in the each node, if visited flage is true, that node is the merge node in the list. Only problem with this method is need to change the structure of the node in the list. And time complexity of this method is O(n*m). Below is the structure and function.

struct node
{
 int info;
 int visited;
 struct node *next;
};

Node* get_merge_node(Node *h1, Node* h2)
{
 traverse(h1); 
 while(h2!=NULL)
 {
  if(h2->visited)
   return h2;
  h2=h2->next;
 }
 return NULL;
}

Click here for the complete working C code for this method

finding merge point in linked list using traversal !!

Below is the C code for finding the merge point in two linked lists. Click here for explanation.

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int info;
 int visited;
 struct node *next;
};

typedef struct node Node;

Node* append(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->visited = 0;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}


/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}

/*****************************************************************************
this method visits/traverse each node from head and makes the visited flag true.
*****************************************************************************/

void traverse(Node *head)
{
 Node *tmp = head;
 while(tmp)
 {
  //making the visited flag true
  tmp->visited = 1;  
  tmp=tmp->next;
 }
}

/*****************************************************************************
first traverse List one and make each node visited flag as true. Then start 
traversing the second list, and check visited flag in each node, if flage is true
that node is the merge node.
*****************************************************************************/
Node* get_merge_node(Node *h1, Node* h2)
{
 traverse(h1); // traversing first list and making the visit flag true.
 while(h2!=NULL)
 {
  if(h2->visited)
   return h2;
  h2=h2->next;
 }
 return NULL;
}


main()
{
 Node *head1 = NULL;
 Node *head2 = NULL;
 Node *merge_node = NULL;
 int i;
 for (i=1;i<=10;i++)
 {
  head1 = append(head1,i*10);
 }
 for (i=1;i<=5;i++)
 {
  head2 = append(head2,i*2);
 }
 Node *temp1 = head1;
 for (i=1;i<=8;i++)
 {
  temp1 = temp1->next;
 }
 printf("List one elements ....\n");
 display(head1);
 printf("List two elements ....\n");
 display(head2);
 
 Node *temp2 = head2;
 while(temp2->next!=NULL)
  temp2=temp2->next;
 //making merge point for two linked lists, commet below line for remvoing the merge point
 temp2->next = temp1; 
 printf("List two elements after making merge point ....\n");
 display(head2);
 merge_node = get_merge_node(head1,head2);
 if(merge_node)
  printf("merge point data is %d\n",merge_node->info);
 else
  printf("two lists are different\n");
}

P.S: Click here for other methods C code for finding merge point in linked list.

finding intersection point in two linked lists program

Here is C code for finding merge point in two linked lists using different methods.  Click here for explanation.

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int info;
 struct node *next;
};

typedef struct node Node;

Node* append(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 return h;
}


/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}



/*****************************************************************************
 this function returns the no. of nodes in the linked list
*****************************************************************************/
int get_count(Node *h)
{
 int count=0;
 if(h == NULL)
  return count;
 while(h!=NULL)
 {
  count++;
  h=h->next;
 }
 return count;
 
}

/*****************************************************************************
This method is more efficient and simple to implement. Get the count of nodes 
in L1 and L2. take the difference as 'diff' and traverse 'diff' nodes in the 
bigger list and then traverse parallelly both L1 and L2 and check each node 
in L1 n L2. If matches that is the merge point.
*****************************************************************************/
Node* get_merge_node(Node *h1, Node* h2, int diff)
{
 int i;
 for(i=0;i<diff;i++)
 {
  h1 = h1->next;
 }
 while(h1!=NULL || h2!=NULL)
 {
  if(h1 == h2)
   return h1;
  h1=h1->next;
  h2=h2->next;
 }
 return NULL;
}

/*****************************************************************************
 This is basic method. using two loops we can compare each node in the L1 with each node in L2
It will take O(n *m ) where n is length of L1 and m is length of L2
*****************************************************************************/
Node* merge_point_basic_method(Node* h1, Node* h2)
{
    while(h1)
    {
        Node *tmp = h2;
        while(tmp)
        {
            if(h1 == tmp)
                return h1;
            tmp=tmp->next;
        }
        h1=h1->next;
    }
    return NULL;
}

main()
{
 Node *head1 = NULL;
 Node *head2 = NULL;
 Node *merge_node = NULL;
 int i,count1,count2,merge_info,method;
 for (i=1;i<=10;i++)
 {
  head1 = append(head1,i*10);
 }
 for (i=1;i<=5;i++)
 {
  head2 = append(head2,i*2);
 }
 Node *temp1 = head1;
 for (i=1;i<=3;i++)
 {
  temp1 = temp1->next;
 }
 printf("List one elements ....\n");
 display(head1);
 printf("List two elements ....\n");
 display(head2);
 
 Node *temp2 = head2;
 while(temp2->next!=NULL)
  temp2=temp2->next;
 //making merge point for two linked lists, comment below line for removing merge point
 temp2->next = temp1; //making merge point for two linked lists
 printf("List two elements after making merge point ....\n");
 display(head2);
 printf("Enter the method in which you need to find the merge point\n");
 printf("1. Basic method\n2. Using difference of nodes\n3. Exit\n");
 scanf("%d",&method);
 switch(method)
 {
  case 1:
    merge_node = merge_point_basic_method(head1, head2);
    break;
  case 2:
    count1 = get_count(head1);
    printf("list one length is %d\n",count1);
    count2 = get_count(head2);
    printf("list two length is %d\n",count2);
    if(count1 > count2)
    {
     //head1 list is bigger so passing head1 first
     merge_node = get_merge_node(head1,head2, count1-count2);
    }
    else
    {
     //head2 list is bigger so passing head2 first 
     merge_node = get_merge_node(head2,head1, count2-count1);
    }
    break;
  default: exit(0);
 }

 if(merge_node)
  printf("merge point data is %d\n",merge_node->info);
 else
  printf("two lists are different\n");
}

P.S: Here is the C code finding intersection point in linked list using traversal method.