What is a pure virtual function in C++ and abstract methods in JAVA?

A pure virtual function contains only method signature without any body( i.e., no implementation)

Example of pure virtual function in C++

class AbstractClass {
public:
   virtual void pure_virtualfunction() = 0;  // a pure virtual function - no body
   

};
Here "=0" may seems like 0 is assigned to the function, that is not true. It only indicates that the virtual function is pure virtual function and it has no body

Any base class that contains pure virtual function is abstract and cannot have an instance itself created and it also means that any class derived from the base class must override the definition of pure virtual function in the base classm if it doesn't, then derived class becomes abstract class as well.

In Java, pure virtual methods are declared using the abstract keyword. Such a method cannot have a body. A class containing abstract methods must itself be declared abstract. But, an abstract class is not necessarilly required to have any abstract methods. An abstract class cannot be instantiated.

In java we declare the class as abstract under two cenarios:

1) when the class contains abstract methods whose implementation will be provided later by its sub-  class.

2) whenever we don't want the object of a class to be created as sub-most object then we declare the class as abstract even if it doesn't contains any abstract methods.

EX: javax.servlet.http.HttpServlet class is declared as abstract even it doesn't contain any abstract methods.

In C++, a regular, "non-pure" virtual function provides a definition, so it doesn’t mean that the class that contains it becomes abstract. You would want to create a pure virtual function when it doesn’t make sense to provide a definition for a virtual function in the base class itself. Use a regular virtual function when it makes sense to provide a definition in the base class.

this link helped me  http://www.programmerinterview.com/index.php/c-cplusplus/pure-virtual-function/

Does C support function overloading like C++?

Look at the printf() function in C, that may lead one to think that C supports function overloading. Because, in C you can have printf("%d", DecimalValue) and printf("%f", FloatValue). This looks a lot like function overloading, because we are using the same function name to handle different arguments differently.

Actually, this is not a case of function overloading – the printf function is just using a feature of C known as variable argument lists. This should not be confused with function overloading. So, to answer the question, Standard C does not support function overloading.

As an interesting side note, C++ doesn’t really have function overloading. What it does have is a means of faking it: the C++ compiler actually ‘mangles’ (or changes) function names according to the function’s parameters. So, functions that share the same name but have different numbers or types of parameters can be differentiated when invoked. Also, since the ‘mangling’ of function names is not standardized, it’s usually difficult to link object files compiled by different C++ compilers.

implementation of single linked list in c language

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *link;
}NODE;
NODE *first=NULL,*last,*temp,*newnode;
void creation()
{
int ch;
do
{
newnode=(NODE*)malloc(sizeof(NODE));
newnode->link=NULL;
printf("\n enter the data of the node : ");
scanf("%d",&newnode->data);
if(first==NULL)
{
first=newnode;
}
else
{
last->link=newnode;
}
last=newnode;
printf("\n do u want to add one more node [1/0] : ");
scanf("%d",&ch);
}
while(ch==1);
}
void insertion()
{
int ch,data;
printf("\n 1.at first \n 2.at middle \n 3.at end ");
printf("\n enter your choice :");
scanf("%d",&ch);
newnode=(NODE *)malloc(sizeof(NODE));
newnode->link=NULL;
printf("\n enter the data for the new node :");
scanf("%d",&newnode->data);
switch(ch)
{
case 1:
newnode->link=first;
first=newnode;
break;
case 2:
printf("\n enter the data of the node after which you want to insert :");
scanf("%d",&data);
temp=first;
while(temp->data==data)
temp=temp->link;
newnode->link=temp->link;
temp->link=newnode;
break;
case 3:
temp=first;
while(temp->link!=NULL)
temp=temp->link;
temp->link=newnode;
last=newnode;
break;
default:
printf("\n invalid  choice ");
free(newnode);
}
}
void deletion()
{
int ch,data;
NODE *temp1;
if(first==NULL)
printf("\n list is empty ");
else
{
printf("\n1.first node \n2.middle node \n3.ending node ");
printf("\n enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
temp=first;
printf("\n deleted element is : %d ",first->data);
first=first->link;
free(temp);
break;
case 2:
printf("\n enter the data of the node that you want to delete : ");
scanf("%d",&data);
temp=first;
while(temp->link->data!=data)
temp=temp->link;
temp1=temp->link;
temp->link=temp->link->link;
free(temp1);
break;
case 3:
temp=first;
while(temp->link->link!=NULL)
temp=temp->link;
printf("\n deleted element is : %d ",temp->link->data);
temp1=temp->link;
temp->link=NULL;
free(temp1);
break;
default:
printf("\ninvalid choice");
}
}
}
void length()
{
int l=0;
temp=first;
while(temp!=NULL)
{
temp=temp->link;
l++;
}
printf("\n length of the list is : %d",l);
}
void display()
{
temp=first;
if(temp==NULL)
printf("\n list is empty...nothing to display ");
else
{
printf("\n");
while(temp!=NULL)
{
printf("%d-->",temp->data);
temp=temp->link;
}
}
}
void main()
{
int ch;
clrscr();
while(1)
{
printf("\n 1.creation \n 2.insertion \n 3.deletion \n 4.display \n 5.length");
printf("\n 6.exit \n Enter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1:
creation();
break;
case 2:
insertion();
break;
case 3:
deletion();
break;
case 4:
display();
break;
case 5:
length();
break;
case 6:
exit(0);
default:
printf("\ninvalid choice\n");
}
}
}

implementation of circular queue using arrays in c language

#include<stdio.h>
#include<conio.h>
#include<process.h>
#define MAX 5
int queue[MAX],front=0,rear=0;
void insertion()
{
if(front==(rear+1)%MAX)
printf("\n queue is full..cannot insert ");
else
{
rear=(rear+1)%MAX;
printf("\n Enter the element to insert in the queue : ");
scanf("%d",&queue[rear]);
}
}
void deletion()
{
if(front==0&&rear==0)
printf("\n queue is empty...nothing to delete ");
else
{
printf("\n deleted element is : %d ",queue[front]);
front=(front+1)%MAX;
}
if(front==rear)
{
front=0;
rear=0;
}
}
void display()
{
int i;
if(front==0&&rear==0)
printf("\n queue is empty...nothing to display ");
else
{
if(front==0)
front++;
for(i=front;i!=rear;i=(i+1)%MAX)
{
printf("%d ",queue[i]);
}
printf("%d ",queue[i]);
}
}
void length()
{
int length=0,i;
if(front==0&&rear==0)
length=0;
else
{
for(i=front;i!=rear;i=(i+1)%MAX)
length++;
}
printf("\n length of the queue is : %d",length);
}
void main()
{
int ch;
clrscr();
while(1)
{
printf("\n 1.insertion\n 2.deletion\n 3.display\n 4.length\n 5.exit");
printf("\n Enter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertion();
break;
case 2:
deletion();
break;
case 3:
display();
break;
case 4:
length();
break;
case 5:
exit(0);
default:
printf("\n invalid choice...try again");
}
}
}

implementation of stack using arrays in c language

#include<stdio.h>
#include<conio.h>
#define max 5
int stack[max],ele,top;
void push();
void pop();
void display();
void topelement();
int main()
{
    char ch;
    top=-1;
    printf("1.push\n2.pop\n3.display\n4.topelement\n5.end\nenter your choice:");
    scanf("%d",&ele);
    do
    {
                    switch(ele)
                    {
                              case 1:
                                   push();
                                   break;
                              case 2:
                                   pop();
                                   break;
                              case 3:
                                   display();
                                   break;
                              case 4:
                                   topelement();
                                   break;
                              case 5:
                                   exit(0);
                                   break;
                    }
             printf("\ndo u want to perform more stack operations[y/n]:");
             ch=_getch();
             if(ch=='y')
             {
                        printf("\n1.push\n2.pop\n3.display\n4.topelement\n5.end\nenter your choice:");
                        scanf("%d",&ele);
             }
    }
    while(ch=='y');
    _getch();
    return 0;
}
void push()
{
     if(top==max-1)
     {
                   printf("stack is full cannot insert anymore\n");
                   return;
     }
     else
     {
                 printf("enter the element do u want to insert:");
                 scanf("%d",&ele);
                 top++;
                 stack[top]=ele;
     }
}
void pop()
{
     if(top==-1)
     {
                printf("stack is empty..no elements to delete\n");
                return;
     }
     else
     {
                top--;
                printf("deleted element from the stack is : %d",stack[top+1]);
     }
}
void display()
{
     int i;
     if(top==-1)
     {
                printf("stack is empty..no elements to display\n");
                return;
     }
     else
     {
         printf("the elememts of the stack are : ");
         for(i=0;i<=top;i++)
                            printf("%d\t",stack[i]);
     }
}
void topelement()
{
     if(top==-1)
     {
                printf("stack is empty\n");
                return;
     }
     else
                printf("the top most element of the stack is : %d",stack[top]);
}

implementation of linearsearch using arrays in c language

#include<stdio.h>
#include<conio.h>
int main()
{
    int key,i,a[]={11,3,56,78,93,45,26,28,6,71};
    printf("enter a values to search:");
    scanf("%d",&key);
    for(i=0;i<=9;i++)
    {
                     if(a[i]==key)
                     break;
    }
    if(i==10)
    printf("search element is not found");
    else
    printf("search element is found at %d location",i+1);
    getch();
    return 0;
}

binary search implementation in c language using arrays

#include<stdio.h>
#include<conio.h>
int main()
{
    int i,key,a[]={1,5,9,11,23,43,56,59,78,99},l=0,h=9,mid;
    printf("enter a values to search:");
    scanf("%d",&key);
    while(l<=h)
    {
               mid=(l+h)/2;
               if(a[mid]==key)
               {
                              printf("search element is found at %d location",mid);
                              getch();
                              //exit(0);
                              return;
               }
               a[mid]>key?(h=mid-1):(l=h+1);
    }
    printf("search element is not found");
   getch();
   return 0;
}

implementation of insertion sorting through single linked list in c

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *link;
};
struct node *first=NULL,*new,*temp;
void creation()
{
int data;
do
{
printf("enter the data of node which you want to sort :");
scanf("%d",&data);
new=(struct node*)malloc(sizeof(struct node));
new->data=data;
new->link=NULL;
if(first==NULL || new->data < first->data)
{
new->link=first;
first=new;
}
else
{
temp=first;
while(temp->link!=NULL&&new->data>=temp->link->data)
temp=temp->link;
new->link=temp->link;
temp->link=new;
}
printf("\n do u want to add one more node[1/0] : ");
scanf("%d",&data);
}while(data);
}

void display()
{
if(first==NULL)
{
printf("\n list is empty... nothing to display");
}
else
{
temp=first;
printf("\n sorted list is :\n");
while(temp!=NULL)
{
printf("%d-->",temp->data);
temp=temp->link;
}
}
}
int main()
{
creation();
display();
getch();
return 0;
}

Ascending Priority Queue implementation in java

import java.io.*;
class Node
{
 int data;
 int priority;
 Node link;
  Node(int priority,int data)
  {
   this.data=data;
   this.priority=priority;
  }
}
class PriorityQueue
{
 Node front;
        
  BufferedReader br;

  void creation()
  {
   int a,b;
   boolean ch=true;
   Node newnode;
                   do
            {  
    try
    {

     System.out.print("enter the data for newnode : ");
     a=Integer.parseInt(br.readLine());
     System.out.println();
     System.out.print("enter the priority for new node : ");
     b= Integer.parseInt(br.readLine());
     System.out.println();
     newnode=new Node(b,a);
    if(front==null||newnode.priority<front.priority)
    {
     newnode.link=front;
     front=newnode;
    }
    else
    {
     Node temp=front;
     while(temp.link!=null&&newnode.priority>=temp.link.priority)
      temp=temp.link;
     newnode.link=temp.link;
     temp.link=newnode;
    }
     System.out.println("do u want to add one mode node [true/false] : ");

                          ch=Boolean.parseBoolean(br.readLine());
    }
               
    catch(Exception e)
    {
     System.out.println(e);
    }
  }
                    while(ch);
  }
             
   void display()
   {
   Node temp=front;
   if(temp==null)
    System.out.println("list is empty");
   else
   {

    while(temp!=null)
    {
     System.out.println(temp.priority+"--->"+temp.data);
     temp=temp.link;
    }
   }
  }

  void delete()
  {
   Node temp=front;

   if(temp==null)
    System.out.println("list is empty");
   else
   {
    System.out.println("deleted element is:" + front.data+" having a priority:"+front.priority);
    front=front.link;
    temp=null; /*whenever you are assining null to a reference of a class ,then the object associated  with  that reference is immediately deleted by the garbage collector due to automatic memory management */
    display();
   }
  }
  public static void main(String [] args)
  {
   int ch;
   PriorityQueue pq=new PriorityQueue();
   pq.br=new BufferedReader(new InputStreamReader(System.in));
  try
  {
   while(true)
   {
    System.out.println("1.creation");
    System.out.println("2.display");
    System.out.println("3.delete");
    System.out.println("4.exit");
    System.out.print("Enter your choice : ");
    ch=Integer.parseInt(pq.br.readLine());
    System.out.println();
    switch(ch)
    {
     case 1:
      pq.creation();
       break;
     case 2:
      pq.display();
       break;
     case 3:
      pq.delete();
       break;
     case 4:
      return;
     default:
      System.out.println("invalid choice...try again ");
    }
   }
  }
   catch(Exception e)
   {
    System.out.println(e);
   }
  }
}


2.Stack implementation using single linked list in c language

program:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void display();
typedef struct stack
{
int ele;
stack *link;
} node;
node *top=NULL;
void push(int x)
{
node *current=NULL;
current=(node *)malloc(sizeof(node));
if(current==NULL)
{
printf("\nmemory is not allocated properly");
return;
}
current->ele=x;
current->link=top;
top=current;
}
void length()
{
node *temp;
int len=0;
temp=top;
while(temp!=NULL)
{
++len;
temp=temp->link;
}
printf("\n the length of the stack is : %d",len);
}
void pop()
{
node *temp;
if(top==NULL)
printf("\n stack is empty ");
else
{
temp=top;
top=top->link;
printf("\n the deleted element is :%d\n",temp->ele);
free(temp);
}
}
void topmost()
{
if(top==NULL)
printf("\nstack is empty");
else
printf("top most element is : %d",top->ele);
}
void display()
{
if(top==NULL)
printf("\n stack is empty ");
else
{
node *temp;
temp=top;
printf("\n the stack elements are:");
while(temp!=NULL)
{
printf("%d<---",temp->ele);
temp=temp->link;
}
}
}
void main()
{
int i,ch;
clrscr();
ab:
printf("\n1.push\n2.pop\n3.topmost\n4.display\n5.length of stack\n6.exit\nenter your choice:");
scanf("%d",&i);
switch(i)
{
case 1:
printf("\n enter the element that you want to insert into d stack :");
scanf("%d",&ch);
push(ch);
break;
case 2:
pop();
break;
case 3:
topmost();
break;
case 4:
display();
break;
case 5:
length();
break;
case 6:
return;
default:
printf("\n invalid choice...try again..");
}
goto ab;
}

What is the significance of equals() and hashCode() methods of Object class in JAVA?

public boolean equals(Object obj)

This method checks if some other object passed to it as an argument is equal to the object on which this method is invoked. The default implementation of this method in Object class simply checks if two object references x and y refer to the same object. i.e. It checks if x == y. This particular comparison is also known as "shallow comparison". However, the classes providing their own implementations of the equals method are supposed to perform a "deep comparison"; by actually comparing the relevant data members. Since Object class has no data members that define its state, it simply performs shallow comparison.

The equals method for class Object implements the most discriminating possible equivalence relation on objects i.e., for any reference values x and y, this method returns true if and only if x and y refer to the same object (x==y has the value true).

Note that it is generally necessary to override the hashCode method(of Object class) whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

public int hashCode()

This method returns the hash code value for the object on which this method is invoked. This method returns the hash code value as an integer and is supported for the benefit of hashing based collection classes such as Hashtable, HashMap, HashSet etc. This method must be overridden in every class that overrides the equals method.

The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.

What is HashMap and Map?

Map is an Interface which is part of Java collections framework. This is used to store Key-Value pairs, and HashMap is the class that implements Map Interface.

EX:
package com.ks.j2se;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
 
public class HashMapDemo {
public static void main(String[] args) {
try {
Map<String,String> hMap = new HashMap<String,String>();
hMap.put("Db2" ,"Expensive Enterprise database from IBM");
hMap.put("Oracle" , "Expensive Enterprise Database from Oracle");
hMap.put("MySQL" , "Free Open Source Database from Sun Microsystems");


Iterator itr = hMap.entrySet().iterator(); 
//getting the keys of hashmap in the form of set, so that we can iterate over keys in loop and in each iteration we can get the corresponding value associated with the key
while (itr.hasNext()) {
Map.Entry mEntry = (Map.Entry) itr.next();
System.out.println(mEntry.getKey() + " : " + mEntry.getValue());
}
} catch (Exception e) {
System.out.println(e.toString());
}
}
}

What is the difference between java.util.Iterator and java.util.ListIterator?

Iterator : Enables you to traverse through a collection in the forward direction only, for obtaining or removing elements.

ListIterator : extends Iterator, and allows bidirectional traversal of list and also allows the modification of elements.

Example:


import java.util.*;


public class Demo {


   public static void main(String args[]) {
      ArrayList al = new ArrayList();
      al.add("A");
      al.add("B");
      al.add("C");
      al.add("D");
      al.add("E");
      al.add("F");


      //iterator 
      System.out.print("Original contents of al: ");
      Iterator itr = al.iterator();
      while(itr.hasNext()) {
         Object element = itr.next();
         System.out.print(element + " ");
      }
      System.out.println();
      
 // listIterator modifying objects
      ListIterator litr = al.listIterator();
      while(litr.hasNext()) {
         Object element = litr.next();
         litr.set(element + "-");
      }


      System.out.print("Modified contents of al: ");


      itr = al.iterator();
      while(itr.hasNext()) {
         Object element = itr.next();
         System.out.print(element + " ");
      }
      System.out.println();


      // Now, display the list backwards
      System.out.print("Modified list backwards: ");
      while(litr.hasPrevious()) {
         Object element = litr.previous();
         System.out.print(element + " ");
       }
       System.out.println();
    }
}


output :


Original contents of al: A B C D E F
Modified contents of al: A- B- C- D- E- F-
Modified list backwards: F- E- D- C- B- A-

What is an Iterator interface in java?

Some of the collection classes provide traversal of their contents via a java.util.Iterator interface. This interface allows you to walk through a collection of objects, operating on each object in turn. Remember when using Iterators that they contain a snapshot of the collection at the time the Iterator was obtained; generally it is not advisable to modify the collection itself while traversing an Iterator.




Method Summary
 boolean  hasNext() :
                                      Returns true if the iteration has more elements.
                   E   next() :
                                       Returns the next element in the iteration.
         void   remove() :
                                       Removes from the underlying collection the last element returned by the iterator (optional operation).
 

How would you find the size of structure without using sizeof()?

struct MyStruct
{
int i;
int j;
};

int main()
{
struct MyStruct *p=0;
int size = ((char*)(p+1))-((char*)p);
printf("\nSIZE : [%d]\nSIZE : [%d]\n", size);
return 0;
}

Is there something we can do in C but not in C++?

The answer is Yes and its seems to be funny but the interviewer may trouble you on this..

Declare variable names which are keywords in C++ but not C.


#include < stdio.h >
int main(void)
{
int  new=3,delete=4;
return 0;
}

this above code will compile in c compiler but not in c++ compiler because new,delete are keywords specific to c++ and they are not in c.

How to swap the two nibbles in a byte ?

unsigned char swapNibbles(unsigned char c)
{
unsigned char temp1, temp2;
temp1 = c & 0x0F;
temp2 = c & 0xF0;
temp1=temp1 << 4;
temp2=temp2 >> 4; 

return(temp2|temp1); //adding the bits
}

int main(void)
{
char ch=0x34;
printf("\nThe exchanged value is %x",swapNibbles(ch));
return 0;
}

How to fast multiply a number by 7?

(num << 3)- num

This is same as

num*8 - num = num * (8-1) = num * 7

How can we sum the digits of a given number in single statement?

void main()
{
int num=123456; 
int sum=0;

for(;num > 0;sum+=num%10,num/=10); // This is the "single line".

printf("\nsum = [%d]\n", sum);
}

Given two strings A and B, how would you find out whether the characters in B were a subset of the characters in A?

#include < stdio.h >
#include < conio.h >

int isSubset(char *a, char *b);

int main()
{
char str1[]="defabc";
char str2[]="abcfed";

if(isSubset(str1, str2)==0)
{
printf("\nYes, characters in B=[%s] are a subset of characters in A=[%s]\n",str2,str1);
}
else
{
printf("\nNo, characters in B=[%s] are not a subset of characters in A=[%s]\n",str2,str1);
}

getch();
return(0);
}


// Function to check if characters in "b" are a subset
// of the characters in "a"

int isSubset(char *a, char *b)
{
int letterPresent[256];
int i;

for(i=0; i < 256; i++)
letterPresent[i]=0;

for(i=0; a[i]!='\0'; i++)
letterPresent[a[i]]++;

for(i=0; b[i]!='\0'; i++)
if(!letterPresent[b[i]])
return(1);

return(0);
}

program to check if the stack grows up or down

Try noting down the address of a local variable. Call another function with a local variable declared in it and check the address of that local variable and compare!.


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

void stack(int *local1);

int main()
{
int local1;
stack(&local1);
exit 0;
}

void stack(int *local1)
{
int local2;
printf("\nAddress of first local : [%u]", local1);
printf("\nAddress of second local : [%u]", &local2);
if(local1 > &local2)
{
printf("\nStack is growing downwards.\n");
printf " Stack is growing to Lower address" );
}
else
{
printf("\nStack is growing upwards.\n");
printf " Stack is growing to Higher address" );
}
printf("\n\n");
}

Write your own C program to implement the atoi() function

int myatoi(const char *string);

int main(int argc, char* argv[])
{
printf("\n%d\n", myatoi("1992")); 
getch();
return 0;
}

int myatoi(const char *string)
{
int i;
i=0;
while(*string)
{
i=i*10;
i=i + (*string - '0');
string++;

// Dont increment i!
}
return(i);
}

How do you reverse a single linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. (push the elements into the stack and copy the elements into the linked list in sequential order i.e., nothing but reversing a single linked list without using pointers)

The other way is to create a new list from the existing list in the reverse order.

to implement the heterogeneous linked list in C language, what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

C program to free the memory allocated to the nodes of a linked list

This is the wrong way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
nextptr = listptr->next;
free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Is Binary search possible on a linked list?

The answer is yes, you can write a C program to do this. But here the question is, do you really think it will be as efficient as a C program which does a binary search on an array? 

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loose the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

C program to return the nth node from the end of a linked list.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it along with the first pointer (ptr1) until first pointer(ptr1) reaches the end of the LL.


STEP 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have  the 6th node from the end pointed to by the ptr2



c code for the above algorithm:

struct node
{
int data;
struct node *next;
}mynode;


mynode * nthNode(mynode *head, int n /*pass 0 for last node*/)
{
mynode *ptr1,*ptr2;
int count;

if(!head)
{
return(NULL);
}

ptr1 = head;
ptr2 = head;
count = 0;

while(count < n)
{
count++;
if((ptr1=ptr1->next)==NULL)
{
//Length of the linked list less than n. Error.
return(NULL);
}
}

while((ptr1=ptr1->next)!=NULL)
{
ptr2=ptr2->next;
}

return(ptr2);
}

C program to remove duplicates from a linked list

First sort the linked list.

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.

// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head) 
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty

// Compare current node with next node
while(current->next!=NULL) 
{
if (current->data == current->next->data) 
{
       struct node* nextNext = current->next->next;
       free(current->next);
       current->next = nextNext;
}
else 
{
       current = current->next; // only advance if no deletion
}
}
}

How to read a singly linked list backwards (or) how to reverse a single linked list

solution1--reverse the list and read it..

struct node* reverseList(struct node* head)
{
struct node *ptr1,*ptr2,*first,*last;
if(head==NULL)
    return NULL:
first=head;
while(head!=NULL)
{
    ptr1=head;
    ptr2=head->link;
    if(first==head)
         ptr1->link=NULL;
  
    ptr2->link=ptr1;
    head=ptr2;
    if(head->link==NULL)
        first=head;
}
return first;
}


solution2 : push the elements into the stack and then read the elements