new instead of malloc

While searching I found a very naive, but useful thing about new/malloc.

Why should we use new instead of malloc ?

1. New and Delete makes sure that constructors and sestructors are called but not the case with malloc and free functions of C. 
2. Pointer conversion safety: malloc() returns a void* which isn't safe. new returns a pointer of the right type. 
3. new is a Operator: new is an operator that can be overloaded for better memory management by a class, while malloc() is not an operaotor. 
4. new operator computes the size of object automatically whereas malloc cannot.
5. It is possible to initialize the object while allocating memory with new. 
6. Its possible to construct an object over an already allocated memory using another version of 'new' operator known as 'placement new' operator. While with malloc() it is not possible.

Nth last element in Linked List (C++)

The following code shows how to get nth last element in a linked list. It uses a queue to hold the temporary elements.

Algorithm:-
1>Make a queue of length N
2>Traverse the linked list from root
3>While traversing, en-queue first N elements
4>After this for en-queuing every element, de-queue another element.
5>When we reach the end of linked list, the last de-queued element will be the Nth last element.

/* 
 * File:   main.cpp
 * Author: Asit
 *
 * Created on 16 September, 2011, 12:25 AM
 */

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

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

class LinkedList
{
    node *root;
public:
    LinkedList():root(NULL){}
    void add(int x)
    {
        node *temp = NULL;
                
        if(root==NULL)
        {
            root = new node;
            root->data = x;
            root->next = NULL;
        }
        else
        {
            temp = root;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = new node;
            temp = temp->next;
            temp->data = x;
            temp->next = NULL;
        }
    }
    
    void show()
    {
        node *temp = root;
        
        while(temp != NULL)
        {
            cout<<temp->data<<"  ";
            temp = temp->next;
        }
        cout<<endl;
    }
    
    int nthLast(int n)
    {
        queue<node*> t_queue;
        int i=1, t_data = -1;
        node *temp = root;
        
        while(temp != NULL)
        {
            t_queue.push(temp);
            if(i>=n)
            {
                t_data = (t_queue.front())->data; 
                t_queue.pop();
            }
            i++;
            temp = temp->next;
        }
        
        i--;
        if(i<n)
            cout<<"Linked list contains less than "<<n<<" elements"<<endl;
        
        return t_data;
    }
};

int main(int argc, char** argv) 
{
    LinkedList list;
    
    for(int i=0; i<20; i++)
        list.add(i*7+90);
    
    cout<<"Created linked list is .. "<<endl;
    list.show();
    
    cout<<"3rd last element : ";
    
    cout<<list.nthLast(3)<<endl;
    
    return 0;
}

Output:-

Created linked list is .. 
90  97  104  111  118  125  132  139  146  153  160  167  174  181  188  195  202  209  216  223  
3rd last element : 209

CountDown Latch to measure sorting time (java)

The following code uses CountDown Latch to measure the performance of sorting example. The sorting method sorts n array of random numbers in separate threads.

import java.util.*;
import java.util.concurrent.*;

public class SortRace {

 /**
  * @param args
         * @developer lipun4u
  */
 public static void main(String[] args) throws Exception{
  // TODO Auto-generated method stub
  int max = 10000;
  int array[] = new int[max];
  Random randomGenerator = new Random();
  
  for(int i=0; i<max; i++)
   array[i] = randomGenerator.nextInt(max*10);
  
  List<String> sortList = Collections.synchronizedList(new ArrayList<String>());
  CountDownLatch startLatch = new CountDownLatch(1);
  CountDownLatch prepareLatch = new CountDownLatch(3);
  CountDownLatch endLatch = new CountDownLatch(3);
  
  new SortThread("BubbleSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  new SortThread("InsertionSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  new SortThread("SelectionSort", startLatch, prepareLatch, endLatch, array, sortList).start();
  
  startLatch.countDown();
  endLatch.await();
  
  System.out.println("Fisrt Position : " + sortList.get(0));
  System.out.println("Second Position : " + sortList.get(1));
  System.out.println("Third Position : " + sortList.get(2));

 }

}

class SortThread extends Thread {
 
 private String sortName;
 private CountDownLatch startLatch, prepareLatch, endLatch;
 private int[] pArray;
 private int[] array;
 
 List<String> list;
 
 public SortThread(String sortName, 
   CountDownLatch startLatch,
   CountDownLatch prepareLatch,
   CountDownLatch endLatch,
   int[] pArray,
   List<String> list) {
  this.sortName = sortName;
  this.startLatch = startLatch;
  this.prepareLatch = prepareLatch;
  this.endLatch = endLatch;
  this.list = list;
  this.pArray = pArray;
  System.out.println(sortName + " Started..");
 }
 
 public void run() {
  try {
   startLatch.await();
   prepareArray();
   prepareLatch.countDown();
   prepareLatch.await();
   if(sortName == "BubbleSort") {
    bubble_sort(array);
   }
   else if(sortName == "InsertionSort") {
    insertion_sort(array);
   }
   else if(sortName == "SelectionSort") {
    selection_sort(array);
   }
   list.add(sortName);
   endLatch.countDown();
  }
  catch(Exception e) {
   e.printStackTrace();
  }
 }
 
 public void prepareArray() {
  array = new int[pArray.length];
  System.arraycopy(array,0, pArray, 0, pArray.length);
 }
 
 public void insertion_sort(int array[]) {
  for(int i=1; i<array.length; i++) {
   int j=i;
   int b = array[i];
   while((j>0) && (array[j-1]>b)) {
    array[j] = array[j-1];
    j--;
   }
   array[j] = b;
  }
   
 }
 
 public void bubble_sort(int array[]) {
  for(int i=0; i<array.length; i++) {
   for(int j=1; j<(array.length-i); j++) {
    if(array[j-1]>array[j]) {
     int t = array[j-1];
     array[j-1]=array[j];
     array[j]=t;
    }
   }
  }
 }
 
 public void selection_sort(int array[]) {
  for(int i=0; i<array.length; i++) {
   for(int j=i+1; j<array.length;j++) {
    if(array[i]>array[j]) {
     int t = array[i];
     array[i]=array[j];
     array[j]=t;
    }
   }
  }
 }
}