Hash Tables example in core java

What is Hash Tables?

A Hash Table is a data-structure that offers very fast insertion and searching. It takes close to constant time O(1) in big O notation.
Hash Tables do have several disadvantages. They are based on arrays and arrays are difficult to expand after they have been created.Also,there is no convenient way to visit the items in a hash table in any kind of order.

Introduction to Hashing

One important concept is how a range of key values is transformed into a range of array index values.In a hash table this is accomplished using hash function.
What we need is a way to compress the huge range of numbers we obtain from the numbers-multiplied-by-powers system into a range that matches a reasonably sized array.
So an array into which data is inserted using a hash function is called hash table.

Tree continue example in core-java

Complete Tree program:

import java.util.Stack;
/**
 * 
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
class Node
{
 public int iData;
 public double dData;
 public Node leftChild;
 public Node rightChild;

 public void displayNode()
 {
System.out.println('{');
System.out.println(iData);
System.out.println(",  ");
System.out.println(dData);
System.out.println("}  ");
 }

 class Tree
 {
private Node root;
public Tree()
{
root=null;
}

public Node find(int key)
{
Node current=root;
while(current.iData!=key)
{
if(key < current.iData)
current=current.leftChild;
else
current=current.rightChild;
if(current==null)
return null ;
}
return current;
}

public void insert(int id,int dd)
{
 Node newNode=new Node();

 newNode.iData=id;
 newNode.dData=dd;

 if(root == null)
  root=newNode;

 else
 {
  Node current=root;
  Node parent;
  while(true)
  {
   parent=current;
   if(id< current.iData)
   {
    current=current.leftChild;
    if(current == null)
    {
     parent.leftChild=newNode;
     return;
    }
   }
   else
   {
    current= current.rightChild;
    if(current ==null)
    {
     parent.rightChild=newNode;
     return;
    }
   }
  }
 }
}

public boolean delete(int key)
{
Node current=root;
Node parent=root;
boolean isLeftChild=true;

while(current.iData !=key)
{
parent=current;
if(key<current.iData)
{
isLeftChild=true;
current=current.leftChild;
}
else
{
isLeftChild=false;
current=current.rightChild;
}

if(current==null)
return false;
}

if(current.leftChild ==null && current.rightChild==null)
{
if(current==root)
root=null;
else if(isLeftChild)
parent.leftChild=null;
else
parent.rightChild=null;
}
else if(current.rightChild==null)
if(current==root)
root=current.leftChild;
else if(isLeftChild)
parent.leftChild=current.leftChild;
else
parent.rightChild=current.leftChild;
else if(current.leftChild==null)
if(current==root)
root=current.leftChild;
else if(isLeftChild)
parent.leftChild=current.leftChild;
else
parent.rightChild=current.leftChild;
else if(current.leftChild ==null)
if(current==root)
root=current.rightChild;
else if(isLeftChild)
parent.leftChild=current.rightChild;
else
parent.rightChild=current.rightChild;
else
{
Node successor=getSuccessor(current);
if(current==root)
root=successor;
else if(isLeftChild)
parent.leftChild=successor;
else
parent.rightChild=successor;

successor.leftChild=current.leftChild;

}
return true;


}

private Node getSuccessor(Node delNode)
{
 Node successorParent=delNode;
 Node successor =delNode;
 Node current=delNode.rightChild;
 while(current!=null)
 {
  successorParent=successor;
  successor=current;
  current=current.leftChild;
 }

 if(successor!=delNode.rightChild)
 {
  successorParent.leftChild=successor.rightChild;
  successor.rightChild=delNode.rightChild;
 }
 return successor;
}

public void traverse(int traverseType)
{
switch (traverseType)
{
   case 1:System.out.println("\n Preorer traversal: ");
       preOder(root);
break;

   case 2:System.out.println("\n InOrder traversal: ");
       inOrder(root);
   break;

   case 3:System.out.println("\n PostOrder traversal: ");
       postOrder(root);
    break;


default:
break;
}
}

private void postOrder(Node localRoot)
{
if(localRoot!=null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.println(localRoot.iData + " ");
}

}

private void inOrder(Node localRoot)
{
if(localRoot!=null)
{
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}

private void preOder(Node localRoot)
{
if(localRoot!=null)
{
System.out.println(localRoot.iData + " ");
preOder(localRoot.leftChild);
preOder(localRoot.rightChild);
}
}


public void displayTree()
{
Stack globalStack=new Stack();
globalStack.push(root);
int nBlank=32;
boolean isRowEmpty=false;
System.out.println("....................................................");
while(isRowEmpty==true)
{
Stack localStack=new Stack();
isRowEmpty=false;
for(int i=0;i<nBlank;i++)
System.out.println(' ');
while(globalStack.isEmpty()==false)
{
Node temp=(Node)globalStack.pop();
if(temp!=null)
{
System.out.println(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);

if(temp.leftChild!=null || temp.rightChild!=null)
isRowEmpty=false;

}
else
{
System.out.println("----");
localStack.push(null);
localStack.push(null);
}
for(int i=0;i<nBlank*2*2;i++)
System.out.println(' ');
}
System.out.println(" ");
nBlank/=2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println(" ");
}

 }

}

public class BinaryTreeApp {

/**
* @param args
*/
public static void main(String[] args) {

         Tree theTree=new Tree();
         theTree.insert(50,1.5);
         theTree.insert(25,1.2);
         theTree.insert(75,1.7);

         theTree.displayTree();
       
         // do somthing like this
}


}

Binary Tree continues example in java

Finding a Node

Finding a node  with a specified key is the simplest of the major tree operations.

Code example:

public Node find(int key)
{
 Node current =root;
 while(current.iData!key)
 {
if(key < current.iData)
current =current.leftChild;
else
current =current.rightChild;
if(current == null)
return null;
 }
}

• Can not find the node
• Found the node

Tree Efficiency:

The time required to find a node depends on how many levels down it is situated.

So it is O(log N) .

Inserting a Node:

To insert a node,we must first find the place to insert it.This is much the same process as trying to find that a node that turns out not to exist.

Sample Code:

public void insert(int id,int dd)

{

Node newNode=new Node();

newNode.iData=id;

newNode.dData=dd;

if(root == null)

root=newNode;

else

{

Node current=root;

Node parent;

while(true)

{

parent=current;

if(id< current.leftChild)

{

currentcurrent.leftChild;

if(current == null)

{

parent.leftChild=newNode;

return;

}

}

else

{

current= current.rightChild;

if(current ==null)

{

parent.rightChild=newNode;

return;

}

}

}

}

}

Traversing the Tree:

Traversing a tree means visiting each node in a specified order.There are three simple ways to traverse a tree.they are called preorder,inorder and postorder.

Inorder Traversal:

An inorder traversal of a binary search  tree will cause all the nodes to be visited in ascending order,based in their key values.

• Call itself to traverse the nodes left sub-tree.
• visit the node.
• call itself to traverse the nodes right sub-tree.

Code example:

private void inOrder(Node localRoot)

{

if(localRoot !=null)

{

inOrder(localRoot.leftChild);

System.out.println(localRoot.iData + " ");

inOrder(localRoot.rightChild);

}

}

PreOrder Traversal:

• Visit the node
• Call itself to traverse the nodes left sub-tree.
• Call itself to traverse the nodes right sub-tree.

Post Order Traversal:

• Call itself to traverse the nodes left sub-tree;
• Call itself to traverse the nodes right sub-tree.
• Visit the node.

Finding Maximum and Minimum Values:

public Node minimum()

{

Node current,last;

current=root;

while(current!=null)

{

last=current;

current=current.leftChild;

}

 

return last;

}

if you want to find the maximum value in the tree then go right sucha as

  current=current.rightChild;

Deleting a Node:

Deleting a node is bit complicated.you start by finding the node you want to delete ,using the same approach we saw in find() and insert() .When you found the node ,there are three cases to consider.

1. The node to be deleted is a leaf(has no children).
2. The node to be deleted has one child;
3. The node to be deleted has two children.

Java code to Delete a Node with no children:

public boolean delete(int key)

{

Node current=root;

Node parent=root;

boolean isLeftChild=true;

while(current.iData ! =key)

{

parent=current;

if(key<current.iData)

{

isLeftChild=true;

current=current.leftChild;

}

else

{

isLeftChild=false;

current=cureent.rightChild;

}

if(current==null)

return false;

}

}

The Node to be Deleted has one Child :

// delete() continued....

// if no right child replace with left sub-tree

else if(current.rightChild==null)

if(current==root)

root=current.leftChild;

else if(isLeftChild)

parent.leftChild=current.leftChild;

else

parent.rightChild=current.leftChild;

else if(current.leftChild==null)

if(current==root)

root=current.rightChild;

else if(isLeftChild)

parent.leftChild=current.rightChild;

else

parent.rightChild=current.rightChild;

The Node to be Deleted has two children:

if  the deleted node has two children ,you can not just replace it with one of these children,at least if the child has its own children.

Here,s the trick, To delete a node with two children,replace the node with its in-order successor.

Finding the Successor:

private Node getSuccessor(Node delNode)

{

Node successorParent=delNode;

Node successor =delNode;

Node current=delNode.rightChild;

while(current!=null)

{

successorParent=sucessor;

successor=current;

current=current.leftChild;

}

if(successor!=delNode.rightChild)

{

successorParent.leftChild=successor.rightChild;

successor.rightChild=delNode.rightChild;

}

return successor;

}

Binary Trees example in java

Why use Binary Trees?

Because,it combines the advantage  of two other structures: an ordered array and linked list.you can search a tree quickly,as you can ordered array and you can also insert , delete items quickly as you can with linked list.Lets explore why?.

1. Slow Insertion in an Ordered Array 
2. Slow Searching in a Linked List

It would be nice if there were a data structure with the quick insertion and deletion of a linked list and also the quick searching of an ordered array.

Tree Terminology:

1. Path-Thinking of someone walking from node to node along the edges that connect them.
2. Root-The node at the top of the tree is called Root.
3. Parent-Any node except the root has exactly one edge running upward to another node.
4. Child-Any node may have one or more lines running downward to other nodes.
5. Leaf-A node that has no children is called Leaf.
6. Sub Tree-Any node may be considered to be the root of a subtree,which cinsists of its children and its childrens children.
7. Visiting-A node is visited when program control arrives at the node.
8. Traversing-To visit all the nodes in some specified order.
9. Levels-The level of a particular node refers to how many generations the node is from the root.
10. Keys-One data field in an object is usually designated a key value.This value is used to search for the item.

Binary Trees

If every node in a tree can have at most two children,the tree is called a binary tree.

Representing the tree in java code:

The Node class

First we need a class of node objects.these objects contain the data representing the objects being stored and also references to each of the nodes two children.

class Node

{

  int iData;

  double fData;

  Node leftChild;

  Node rightChild;

 public void displayNode()

 {

    // display node

 }

}

The Tree Class

class Tree

{

  private Node root;

  

  public void find(int key)

  {

  }

  public void insert(int id,double dd)

  {

  }

  public void delete(int id)

  {  

  }

  // various other methods

}

Quick Sort example in core-java

Quick Sort:

Quick Sort is the most popular sorting algorithm.In the majority of situations ,it is fastest,operating in O(N*logN) time . This is only true for internal or int-memory sorting;for sorting data in disk files.to understanding you should be familiar with the partitioning algorithm.Basically the quick-sort algorithm operates by partitioning an array in two two sub-arrays and then calling itself recursively to quick-sort each of these sub-arrays

Quick Algorithm:
There are 3 basic steps.

1. Partitioning the array or sub-array into left(smaller keys) and right(larger keys) groups.
2. Call ourselves to sort the left group
3. Call ourselves again to sort the right groups.

Choosing a Pivot Value:

• The pivot value should be the key value of an actual data items;this item is called the pivot.
• you can pick a data item to be the pivot more or less at random.for simplicity,lets say we always pick the item on the right end of the sub-array being partitioned.
• After the partition,if the pivot is inserted at the boundary between the left and right sub arrays ,it will be in its final sorted position.

Code Example:

/**

 * 

 */

/**

 * @author Abhinaw.Tripathi

 *

 */

class ArraysIns

{

private long[] theArray;

private int nElems;

public ArraysIns(int max) 

{

theArray =new long[max];

nElems=0;

}

 

public void insert(long values)

{

theArray[nElems] =values;

nElems++;

}

 

public void display()

{

System.out.println("A=");

for(int j=0;j<nElems; j++)

System.out.println(theArray[j]+ " ");

System.out.println(" ");

}

 

public void swap(int dex1,int dex2)

{

long temp;

temp=theArray[dex1];

theArray[dex1]=theArray[dex2];

theArray[dex2]=temp;

}

 

public int partitionIt(int left,int right,long pivot)

{

int leftptr=left-1;

int rightPtr=right+1;

while(true)

{

while(leftptr <right && theArray[++leftptr] <pivot);

while(rightPtr>left && theArray[--rightPtr] > pivot);

if(leftptr >=rightPtr)

break;

else

swap(leftptr, rightPtr);

}

return leftptr;

}

 

public void recursiveSort(int left,int right)

{

if(right-left <=0)

return;

else

{

long pivoit=theArray[right];

int partition=partitionIt(left, right, pivoit);

recursiveSort(left, partition-1);

recursiveSort(partition+1, right);

}

}

 

public void quickSort()

{

recursiveSort(0, nElems-1);

}

 

}

public class QuickSortApp {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

ArraysIns arr =new ArraysIns(16);

for(int j=0;j<10;j++)

{

long n=(int)(java.lang.Math.random()*99);

arr.insert(n);

}

arr.display();

arr.quickSort();

arr.display();

}

}

Efficiency of Quick Sort: O(N*logN)

Partitioning example in core java

Partitioning: 

Partitioning is the underlying mechanism of quick sort.It is also useful operation on its own.To partitioning data is to divide it into two  groups so that the items with a key value higher than a specified amount are in one group and all the items with a lower key value are in another.

Code Example:

/**
 * @author Abhinaw.Tripathi
 *
 */

class ArrayPar
{
private long[] theArray;
private int nElems;
public ArrayPar(int max)
{
theArray =new long[max];
nElems=0;
}

public void insert(long values)
{
theArray[nElems] =values;
nElems++;
}

public int size()
{
return nElems;
}

public void display()
{
System.out.println("A=");
for(int j=0;j<nElems; j++)
System.out.println(theArray[j]+ " ");
System.out.println(" ");
}

public void swap(int dex1,int dex2)
{
long temp;
temp=theArray[dex1];
theArray[dex1]=theArray[dex2];
theArray[dex2]=temp;
}

public int partitionIt(int left,int right,long pivot)
{
int leftptr=left-1;
int rightPtr=right+1;
while(true)
{
while(leftptr <right && theArray[++leftptr] <pivot);
while(rightPtr>left && theArray[--rightPtr] > pivot);
if(leftptr >=rightPtr)
break;
else
swap(leftptr, rightPtr);
}
return leftptr;
}

}

public class PartitionApp {

public static void main(String[] args)
{
ArrayPar arr=new ArrayPar(16);
for(int j=0;j<10;j++)
{
long n=(int)(java.lang.Math.random()*99);
arr.insert(n);

}
arr.display();
long pivot=71;
System.out.println("Pivot is :"+pivot);
int size=arr.size();

int partDex=arr.partitionIt(0, size-1, pivot);

System.out.println("partition is at the index"+partDex);
arr.display();

}


}

Efficiency of the Partition Algorithm:

It runs in O(N) time

Shell Sort example in java

Shell sort is a sorting algorithm that requires asymptotically fewer than O(n²) comparisons and exchanges in the worst case. Although it is easy to develop an intuitive sense of how this algorithm works, it is very difficult to analyze its execution time, but estimates range from O(nlog2 n) to O(n1.5) depending on implementation details.

Shell sort is a generalization of insertion sort, with two observations in mind:

Insertion sort is efficient if the input is "almost sorted".
Insertion sort is inefficient, on average, because it moves values just one position at a time.
Shell sort improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.

Consider a small value that is initially stored in the wrong end of the array. Using an O(n²) sort such as bubble sort or insertion sort, it will take roughly n comparisons and exchanges to move this value all the way to the other end of the array. Shell sort first moves values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.

Code example:

/**
 * 
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

class ArraySh
{
 private long[] theArray;
 private int nElems;

 public ArraySh(int max)
 {
theArray =new long[max];
nElems=0;
 }

 public void insert(long values)
 {
theArray[nElems] =values;
nElems++;
 }

 public void display()
 {
System.out.println("A=");
for(int j=0;j<nElems; j++)
System.out.println(theArray[j]+ " ");
System.out.println(" ");
 }

 public void shellSort()
 {
int inner,outer;
long temp;
int h=1;

while(h<=nElems/3)
h=h*3 +1;
while(h>0)
{
for(outer =h;outer<nElems;outer++)
{
temp=theArray[outer];
inner=outer;

while (inner > h-1 && theArray[inner-h] >=temp)
{
theArray[inner] =theArray[inner -h];
inner-=h;
}
theArray[inner]=temp;
}
h=(h-1)/3;

}
 }

}
public class ShellSortApp
{


public static void main(String[] args)
{
ArraySh arr=new ArraySh(10);
for(int j=0;j<10;j++)
{
long n=(int)(java.lang.Math.random()*99);
arr.insert(n);

}
arr.display();
arr.shellSort();
arr.display();
}


}

Merge sort example in core java recursion

Merge Sort:

our final example of recursion is the merge-sort.This is more sorting technique.While the bubble,insertion and selection sort take O(N^2) time.The merge sort is O(N*log N).

Sample Code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MergeApp
{
public static void main(String[] args)
{
int[] arrayA={23,47,81,95};
int[] arrayB={7,14,39,55,62,74};
int[] arrayC=new int[10];

merge(arrayA,4,arrayB,6,arrayC);
display(arrayC,10);

}

private static void display(int[] arrayC, int size)
{
for(int j=0;j<size;j++)
System.out.println(arrayC[j] + "  ");
System.out.println(" ");
}

private static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB,int[] arrayC)
{
int aDex=0,bDex=0,cDex=0;

while (aDex <sizeA && bDex < sizeB)
if(arrayA[aDex] < arrayA[bDex])
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] =arrayB[bDex++];

while(aDex < sizeA)
arrayC[cDex++] =arrayA[aDex++];

while(bDex < sizeB)
arrayC[cDex++] = arrayB[bDex++];
}

}

Divide-and-Conquer Algorithms and Tower of Hanoi Puzzle in core-java

What is Divide-and-Conquer Algorithms?

Divide-and-Conquer Algorithms:

The Divide-and-Conquer approach is commonly used with recursion.The recursive binary search is an example of the divide-and-conquer . actually you divide big problem into small problem and solve them separately.A divide and conquer approach usually involves a method that contains two recursive calls to itself,one for each half of the problem.

The Tower of Hanoi:

The Towers of hanoi is an ancient puzzle consisting of a number of disks placed on three columns.Three disks all have different diameters and holes in the middle so they will fir over the columns.

The Recursive Algorithm to solve this problem:

The solution to the Towers of Hanoi puzzle can be expressed recursively using the notion of sub trees.Suppose you want to move all the disks from a source tower to a destination tower .you have an intermediate tower available .

1. Move the sub tree consisting of the top n-1 disks from S to I.
2. Move the remaining disk from S to D.
3. Move the sub tree from I to D.

Code Sample:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

public class TowerofHanoiApp
{
   static int nDisks=3;
 
public static void main(String[] args)
{
doTowerofHanoi(nDisks,'A','B','C');
}

private static void doTowerofHanoi(int topN, char from, char inter, char to)
{

if(topN == 1)
System.out.println("Disk 1 from "+from + " to "+to);
else
{
doTowerofHanoi(topN-1, from, to, inter);
System.out.println("Disk" + topN + "from" + from +" to" + to);
doTowerofHanoi(topN-1, inter, from, to);
}
}


}

Recursion Anagrams example in core-java

Anagrams:
Some times anagrams suits in a situation in which recursion provides a neat solution to a problem.A permutation is an arrangement of things in a definite order.Suppose you want to list all the anagrams of a specified words.

For example: Anagram of Cat:

• cat
• cta
• atc
• act
• tca
• tac

So Algorithm to write a program to anagram a word:

1. Anagram the rightmost n-1 letters .
2. Rotate all n letters.
3. Repeat these steps n times.

Example Code:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

/**

 * 

 */

/**

 * @author Abhinaw.Tripathi

 *

 */

public class AnagramApp 

{

   static int size;

   static int count;

   static char[] arrChar =new char[100];

   

public static void main(String[] args) throws IOException 

{

System.out.println("Enter a word:  ");

        String input =getString();

        size=input.length();

        count=0;

        for(int j=0;j<size;j++)

        {

        arrChar[j] =input.charAt(j);

        doAnagram(size);

        }

}

private static void doAnagram(int newsize) 

{

      if(newsize == 1)

      {

     return;

      }

      for(int i=0;i<newsize;i++)

      {

     doAnagram(newsize-1);

     if(newsize==2)

     displayWord();

     rotate(newsize);

      }

}

private static void rotate(int size2)

{

int j;

int position =size- size2;

char temp=arrChar[position];

for(j=-position+1;j<size;j++)

  arrChar[j-1]=arrChar[j];

arrChar[j-1]=temp;

 

}

private static void displayWord() 

{

if(count < 99)

System.out.println(" ");

if(count < 9)

System.out.println(" ");

System.out.println(++count + " ");

for(int j=0;j<size;j++)

System.out.println(arrChar[j]);

System.out.println("  ");

System.out.flush();

if(count%6 == 0)

System.out.println(" ");

}

private static String getString() throws IOException 

{

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

String s=br.readLine();

return s;

}

}

Recursion in Java example

What is Recursion?

Recursion is a programming technique in which a method calls itself.This may sound like a strange thing to do or even a catastrophic mistakes.
Recursion is however, one of the most interesting and one of the most surprising effective techniques in programming.we will discuss the strength and weakness of recursion and show how a recursion approach can be transformed into a stack-based approach.

Triangular Numbers:

A band of mathematicians in ancient Greece who worked under Pythagoras and felt a connection with the series of numbers 1,3,6,10,15,21,........
Can you find the next member of this series?

The nth term in the series is obtained by adding n to the previous term.thus second term is found by adding 2 to the first term(which is 1),giving 3.The third term is 3 added to the second term(which is 3) giving 6, and so on.The numbers in the series are called Triangular Numbers.


Finding the nth Term Using a Loop:

int traingle(int n)
{
  int total=0;

while(n>0)
 {
    total=total+n;
    --n;
 }

  return total;
}

The method cycles around the loop n times,adding n to total the first time,n-1 the 2nd time and so on down to 1,quitting  the loop when n becomes 0 .


Finding the nth Term Using Recursion:

1. The first column,which has the value n.
2. The sum of all the remaining columns.

Code implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class TraingleApp
{
   static int theNumber;

public static void main(String[] args) throws IOException
{
System.out.println("Enter a number:");
        theNumber=getInt();    
        int answer=traingle(theNumber);
        System.out.println("Traingle=" +answer);
}

public static int traingle(int n)
{
if(n==1)
return 1;
else
return (n+traingle(n-1));
}

private static int getInt() throws IOException
{
String s=getString();
return Integer.parseInt(s);
}


private static String getString() throws IOException
{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}

}


Characteristics of Recursive Methods:

• It calls itself.
• When  it calls itself,it does so to solve a smaller problem.
• there is some version of the problem that is simple enough that the routine can solve it and return ,without calling itself.

Is Recursion Efficient:

Calling a method involves certain overhead such as Memory but it can be controlled control must be transferred from the location of the call to the beginning of the method.

In the case of traingle() method its probable that as a result of the overhead, the while loop approach executes  more quickly than the recursive approach.

Recursion is usually used because it simplifies a problem conceptually not because it is inherently more efficient.

Factorial Example in Recursion:

int factorial(int n)
{
  if(n==0)
   {
       return 1;
   }

   else
    {
      return (n * factorial(n-1));

    }
}

Doubly Linked Lists operation example in core java

Doubly Linked List basic operation example:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

class Link
{
 public long dData;
 public Link next;
 public Link previous;

 public Link(long d)
 {
this.dData=d;
 }

 public void displayLink()
 {
 System.out.println(dData+ " ");
 }

}

class DoublyLinkedList
{
  private Link first;
  private Link last;

  public DoublyLinkedList()
  {
first=null;
last=null;
  }
  public boolean isEmpty()
  {
return (first==null);
  }

  public void insertFirst(long dd)
  {
 Link newLink=new Link(dd);
 if(isEmpty())
 {
 last=newLink;

 }
 else
  first.previous=newLink;
 newLink.next=first;
 first=newLink;
  }

  public void insertLast(long dd)
  {
 Link newLink=new Link(dd);
 if(isEmpty())
 first=newLink;
 else
 {
 last.next=newLink;
    newLink.previous=last;
 }
 last=newLink;
  }

  public Link deleteFirst()
  {
 Link temp=first;
 if(first.next == null)
 last=null;
 else
 first.next.previous=null;
 first=first.next;
 return temp;
  }

  public Link deleteLast()
  {
 Link temp=last;
 if(first.next == null)
 first=null;
 else
 last.previous.next=null;
 last=last.previous;
 return temp;
  }


  public boolean insertAfter(long key,long dd)
  {
 Link current =first;
 while(current.dData!=key)
 {
 current=current.next;
 if(current == null)
 return false;
 }

 Link newLink=new Link(dd);

 if(current==last)
 {
 newLink.next=null;
     last=newLink;
 }
 else
 {
 newLink.next=current.next;
 current.next.previous=newLink;
 }

 newLink.previous=current;
 current.next=newLink;
 return true;
  }

  public Link deletekey(long key)
  {
 Link current=first;
 while(current.dData!=key)
 {
 current=current.next;
 if(current==null)
 return null;
 }
 if(current == first)
 first=current.next;
 else
 current.previous.next=current.next;

 if(current==last)
 last=current.previous;
 else
 current.next.previous=current.previous;
 return current;
  }

  public void displayForward()
  {

 System.out.println("List (first-----.last:)");
 Link current =first;
 while(current!=null)
 {
 current.displayLink();
 current=current.next;
 }
 System.out.println(" ");
  }

  public void displayBackward()
  {
 System.out.println("List (last---->first)");
 Link current=last;
 while(current!=null)
 {
 current.displayLink();
 current=current.previous;
 }
 System.out.println("  " );
  }

}


public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList=new DoublyLinkedList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);

theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);

theList.displayForward();
theList.displayBackward();

theList.deleteFirst();
theList.deleteLast();
theList.deletekey(11);

theList.displayForward();
theList.displayBackward();

theList.insertAfter(22, 77);
theList.insertAfter(33, 88);

theList.displayForward();

}

}


The desire output will be

List (first-----.last:)
66 
44 
22 
11 
33 
55 

List (last---->first)
55 
33 
11 
22 
44 
66 
  
List (first-----.last:)
44 
22 
33 

List (last---->first)
33 
22 
44 
  
List (first-----.last:)
44 
22 
77 
33 
88 

Queue implemented by a Linked List in core-java example

Queue implemented by a Linked List:

/**
 * @author Abhinaw.Tripathi
 *
 */

class Link
{

 public long dData;
 public Link next;

 public Link(long dd)
 {
dData=dd;
 }

 public void displayLink()
 {
 System.out.println(dData+ " ");
 }

}

class FirstLastList
{
  private Link first;
  private Link last;

  public FirstLastList()
  {
first=null;
last=null;
  }

  public boolean isEmpty()
  {
return (first==null);
  }

  public void insertLast(long dd)
  {
 Link newLink=new Link(dd);
 if(isEmpty())
 first=newLink;
 else
 last.next=newLink;
 last=newLink;
  }

  public long deleteFirst()
  {
 long temp=first.dData;
 if(first.next == null)
 last=null;
 first=first.next;
 return temp;
  }

  public void displayList()
  {
Link current=first;
while(current!=null)
{
current.displayLink();
current=current.next;
}

System.out.println(" ");
   }

}

class LinkQueue
{
private FirstLastList theList;

public LinkQueue()
{
theList=new FirstLastList();
}

public boolean isEmpty()
{
return (theList.isEmpty());
}

public void insert(long j)
{
theList.insertLast(j);

}

public long remove()
{
return theList.deleteFirst();
}

public void displayQueue()
{
System.out.println("Queue (front ---> rear:)");
theList.displayList();
}
}

public class LinkQueueApp {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
     LinkQueue theQueue=new LinkQueue();
     theQueue.insert(20);
     theQueue.insert(40);
   
     theQueue.displayQueue();
   
     theQueue.insert(60);
     theQueue.insert(80);
   
     theQueue.displayQueue();
   
     theQueue.remove();
     theQueue.remove();
   
     theQueue.displayQueue();
}


}

The desire output will be

Stack  (top---->bottom:)
40 
20 

Stack  (top---->bottom:)
80 
60 
40 
20 

Stack  (top---->bottom:)
40 
20