Category Archives: Java Data Structure Implementation

Multiplication in less time and space : using Karatsuba

This program demonstrates the multiplication of two numbers in less time and space : using Karatsuba in Java.
The Operation implemented :
1. Multiplication

Idea :

Karatsuba Multiplication

Karatsuba Multiplication

Implementation :


import java.util.Scanner;

/*
* This class demonstrates multiplication in less no. of CPU cycles.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 6th December, 2014
*/
class KaratsubaMultiplier{

/**
* The karatsubaMultiply method
* @param long n1
* @param long n2
* @return long.
*/
private long karatsubaMultiply(long n1, long n2){
int len1 = length(n1);
int len2 = length(n2);

int N = maximum(len1, len2);

if (N < 2)
return n1 * n2;

N = (N / 2) + (N % 2);

long m = (long)Math.pow(10, N);

long b = n1 / m;
long a = n1 - (b * m);
long d = n2 / m;
long c = n2 - (d * m);
long z1 = karatsubaMultiply(a, c);
long z2 = karatsubaMultiply(a + b, c + d);
long z3 = karatsubaMultiply(b, d);

return z1 + ((z2 - z1 - z3) * m) + (z3 * (long)(Math.pow(10, 2 * N)));
}

/**
* The maximum method
* @param int len1
* @param int len2
* @return int.
*/
private int maximum(int len1, int len2){
return Math.max(len1, len2);
}

/**
* The length method
* @param long number
* @return int.
*/
private int length(long number){
int count = 0;
while (number != 0){
count++;
number = number / 10;
}
return count;
}

/**
* The multiply method
* @param long x
* @param long y
* @return long.
*/
public long multiply(long x,long y) throws InvalidMethodArgumentException{
if(x<0 || y<0)
throw new InvalidMethodArgumentException("Invalid Argument");
return karatsubaMultiply(x, y);
}
}

class InvalidMethodArgumentException extends Exception{
private static final long serialVersionUID = 1L;

public InvalidMethodArgumentException(String message) {
super(message);
}
}

public class KaratsubaMultiplicationApp {

/**
* The main method
* @param void
* @return Sting[].
*/
public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter integer number one");
long num1 = sc.nextLong();
System.out.println("Enter integer number two");
long num2 = sc.nextLong();
try {
System.out.println("\nMuliplication is : "+ new KaratsubaMultiplier().multiply(num1, num2));
} catch (InvalidMethodArgumentException e) {
System.out.println(e.getMessage());
}
sc.close();
}

}

I appreciate all your feed backs.

Java Data Structure Implementation : Undirected Simple Graph (BFS/DFS)

This program demonstrates the Undirected Simple Graph implementation using link list, Queue & Stack in Java.
The Operation implemented :
1. Insert Vertex/Edge,
2. Delete Vertex/Edge,
3. Breadth First Traversal (Used my Stack Program)
4. Depth First Traversal (Used my Queue Program)
5. Print Adjancy List (Used my List Program)
6. Print Vertices Data

The implementation logic and memory representation is shown in the below picture.

Undirected Simple Graph Impl

Undirected Simple Graph Implementations

Two Major Implementations Breadth First Traversal and Depth First Traversal are implemented using Queue and Stack respectively. This shows the best use/application of the Stack and Queue.

This implementation is implemented using the Link List, Stack and Queue so you need to download my Doubly link list, Stack and Queue code into your package before running this code. You can download the Doubly link list, Stack and Queue code from my previous blogs

Find the Java Code below :


import hclinfosys.ds.linklist.DoublyLinkList;
import hclinfosys.ds.queue.Queue;
import hclinfosys.ds.stack.StackUsingArray;

import java.util.Scanner;

/*
* This class represent the Graph Vertex.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 09th April, 2014
*/
class GraphVertex{
int id;
DoublyLinkList connectedEdges = null;
boolean isVisited = false;

public GraphVertex() {}

public GraphVertex(int id){
this.id=id;
}
}

/*
* This class demonstrates Graph Implementation in java with Insert/Delete/Traversal/Find Operations.
* @author : Madan Gopal Singh
* @version : 2.0
* @date : 11th April, 2014
*/
public class Graph {

public static int NO_OF_VERTICES = 7;
public static int TOP = -1;

public static GraphVertex[] vertices;

public Graph() {}

/**
* This method add new vertex in graph.
* @param vertexToBeInserted.
* @return void.
*/
public static void addNewVertex(GraphVertex vertexToBeInserted){
if(TOP==NO_OF_VERTICES-1){
System.out.println("Graph Size Exceeded");
}else{
TOP=TOP+1;
vertices[TOP] = vertexToBeInserted;
System.out.println("Vertex Inserted at "+TOP+" with value : "+vertices[TOP].id);
}
}

/**
* This method remove vertex from graph.
* @param vertexToBeRemoved.
* @return void.
*/
public static void removeVertex(GraphVertex vertexToBeRemoved){
if(TOP==-1){
System.out.println("No Vertex in Graph");
}else{
//Removing Edges connected to vertex
DoublyLinkList startNode = vertexToBeRemoved.connectedEdges;
while(startNode!=null){
System.out.println("Node Info : "+startNode.id+" Index of Vertex : "+Graph.getVertexIndex(startNode.id));
GraphVertex destinationVertex = vertices[Graph.getVertexIndex(startNode.id)];
Graph.removeEdge(vertexToBeRemoved, destinationVertex);
startNode = startNode.next;
}
//Removing Vertex
int indexOfVertex = Graph.getVertexIndex(vertexToBeRemoved.id);
for(int i = indexOfVertex;i=0){
if(String.valueOf(vertices[i].id).equalsIgnoreCase((String)obj.toString())){
return i;
}
i = i-1;
}
return -1;
}
}

/**
* This method print all vertices of the Graph.
* @param void.
* @return void.
*/
public static void printAllVertices(){
if(TOP == -1){
System.out.println("Graph has no vertices");
}else{
int i = TOP;
while(i>=0){
System.out.println("Element at position "+ i + " is :- "+vertices[i].id);
i = i-1;
}
}
}

/**
* This method print the Adjancy list of the Graph
* @return void
*/
public static void printAdjancyList(){
for(int i = 0; i=0){
vertices[i].isVisited = false;
System.out.println("Vertex "+ vertices[i].id + " is marked un visited.");
i = i-1;
}
}
}

/**
* This method prints the depth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void depthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String depthFirstTraversalSequence = "";
StackUsingArray.STACK_SIZE = NO_OF_VERTICES;
StackUsingArray.stackElements = new Object[StackUsingArray.STACK_SIZE];
StackUsingArray.push(vertices[0].id);
while(!StackUsingArray.isEmpty()){
Object removed = StackUsingArray.pop();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
depthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && StackUsingArray.isElementExists(edges.id)==false){
StackUsingArray.push(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Depth First Traversal Sequence : "+depthFirstTraversalSequence);
}

/**
* This method prints the breadth first traversal of the Graph from starting vertex.
* @param void.
* @return void.
*/
public static void breadthFirstTraversal(GraphVertex startingVertex){
markAllVerticesNotVisted();//Marking all vertices not visited
int removedVertexId,removedVertexIndex;
String breadthFirstTraversalSequence = "";
Queue.QUEUE_SIZE = NO_OF_VERTICES;
Queue.queueList = new Object[Queue.QUEUE_SIZE];
Queue.insertIntoQueue(vertices[0].id);
while(!Queue.isEmpty()){
Object removed = Queue.removeFromQueue();
if(removed!=null){
removedVertexId = Integer.parseInt(removed.toString());
breadthFirstTraversalSequence += removedVertexId+" ";
removedVertexIndex = Graph.getVertexIndex(removedVertexId);
vertices[removedVertexIndex].isVisited = true;
DoublyLinkList edges = vertices[removedVertexIndex].connectedEdges;
while(edges!=null){
if(vertices[Graph.getVertexIndex(edges.id)].isVisited==false && Queue.isElementExists(edges.id)==false){
Queue.insertIntoQueue(edges.id);
}
edges = edges.next;
}
}
}
System.out.println("Breadth First Traversal Sequence : "+breadthFirstTraversalSequence);
}

/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
int userOperation = 0, vertexId=-1,fromVertexId=-1,toVertexId=-1,fromVertexIndex=-1,toVertexIndex=-1;

vertices = new GraphVertex[NO_OF_VERTICES];
GraphVertex vertexToBeInserted = null,sourceVertex = null,destinationVertex = null;
Scanner sc = new Scanner(System.in);
do{
String menuString = "\tSimple Undirected Graph \nWhat operation you want to perform?"+
"\n 1. Insert New Vertex"+
"\n 2. Insert New Edge"+
"\n 3. Remove Vertex"+
"\n 4. Remove Edge"+
"\n 5. Breadth First Traversal"+
"\n 6. Depth First Traversal"+
"\n 7. Print All Vertices"+
"\n 8. Print Adjancy List Representation"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();

switch(userOperation){
case 1:
System.out.println("Plese enter vertex Id to Insert: ");
vertexId = sc.nextInt();
vertexToBeInserted = new GraphVertex(vertexId);
System.out.println("Adding New Vertex");
Graph.addNewVertex(vertexToBeInserted);
break;
case 2:
System.out.println("Plese enter FROM vertex Id : ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id : ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
System.out.println("From Vertext Index : "+fromVertexIndex);
System.out.println("To Vertext Index : "+toVertexIndex);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Destination Vertex Id : "+destinationVertex.id);
System.out.println("Adding Edge");
if(!Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.addNewEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Simple Graph doesn't allow multiple Edges. Please try new pair");
}
}
break;
case 3:
System.out.println("Plese enter vertex Id to Remove: ");
vertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(vertexId);
if(fromVertexIndex!=-1){
vertexToBeInserted = vertices[fromVertexIndex];
System.out.println("Removing Vertex");
Graph.removeVertex(vertexToBeInserted);
}
break;
case 4:
System.out.println("Plese enter FROM vertex Id for Remove: ");
fromVertexId = sc.nextInt();
fromVertexIndex = Graph.getVertexIndex(fromVertexId);
System.out.println("Plese enter TO vertex Id for Remove: ");
toVertexId = sc.nextInt();
toVertexIndex = Graph.getVertexIndex(toVertexId);
if(fromVertexIndex!=-1&&toVertexIndex!=-1){
sourceVertex = vertices[fromVertexIndex];
destinationVertex = vertices[toVertexIndex];
System.out.println("Removing Edge");
if(Graph.isEdgeExists(sourceVertex, destinationVertex)){
Graph.removeEdge(sourceVertex, destinationVertex);
}else{
System.out.println("Edge doesnit exists between these pair of vertices. Please try new pair");
}
}
break;
case 5:
System.out.println("Breadth First Traversal from Starting Node");
Graph.breadthFirstTraversal(vertexToBeInserted);
break;
case 6:
System.out.println("Depth First Traversal from Starting Node");
Graph.depthFirstTraversal(vertexToBeInserted);
break;
case 7:
System.out.println("Printing All Elements");
Graph.printAllVertices();
break;
case 8:
System.out.println("Printing Adjancy List");
Graph.printAdjancyList();
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default : System.out.println("Exit from System");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited if any.

Java Data Structure Implementation : Hashtable using Link List

This program demonstrates the hash table implementation using link list in Java. The Insert, Delete, Find and Print all Bucket Data Operation has been implemented.

The Hashtable implementation looks like :

Hashtable

This implementation is implemented using the Link List so you need to download my Doubly link list code into your package before running this code. You can download the Doubly link list code from my previous blog

Find the Java Code below :

import hclinfosys.ds.linklist.DoublyLinkList;

import java.util.Scanner;

/*
* This class demonstrates Hashtable Implementation in java with Add/Delete/Search Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 31st March, 2013
*/
public class HashTable {
//Declaring Bucket Size
public static int HASH_TABLE_SIZE = 5;
//Declaring Buckets
public static HashTable[] buckets = new HashTable[HASH_TABLE_SIZE];

int id;
DoublyLinkList list;

/**
* This method getBucketHashFunction is used to return the position of element of which the element will be inserted into the bucket
* in hash table
* @param element
* @return int
*/
public static int getBucketHashFunction(int element){
return (element%HASH_TABLE_SIZE);
}

/**
* This method insertIntoBucket is used to insert element into the hashtable
* @param element
* @return void
*/
public static void insertIntoBucket(int element){
int bucket;
bucket = getBucketHashFunction(element);
if(buckets[bucket].list==null){
buckets[bucket].list = new DoublyLinkList(element);
}else{
DoublyLinkList.addNewNodeAtLast(buckets[bucket].list, new DoublyLinkList(element));
}
}

/**
* This method removeFromBucket is used to remove element from the hashtable
* @param element
* @return void
*/
public static void removeFromBucket(int element){
int bucket;
bucket = getBucketHashFunction(element);
if(buckets[bucket].list!=null){
if(((DoublyLinkList)buckets[bucket].list).next ==null){
buckets[bucket].list = null;
}else{
buckets[bucket].list = DoublyLinkList.removeNodeFromSpecificPosition(buckets[bucket].list, element);
}
}else{
System.out.println("Element is not found in Hashtable");
}
}

/**
* This method findInBuckets is used to find element in the hashtable
* @param element
* @return int
*/
public static int findInBuckets(int element){
int bucket;
bucket = getBucketHashFunction(element);
if(buckets[bucket].list!=null){
DoublyLinkList.traverseLinkListSpecificNode(buckets[bucket].list, element);
System.out.println("Found element in bucket "+bucket);
}else{
System.out.println("Element is not in Hashtable");
}
return 0;
}

/**
* This method findInBuckets is used to find element in the hashtable
* @param element
* @return int
*/
public static void printAllElements(){
for(int i = 0; i<buckets.length;i++){
if(buckets[i].list!=null){
System.out.println("Bucket "+ i + " elements : ");
DoublyLinkList.traverseLinkList(buckets[i].list);
}else{
System.out.println("Bucket "+ i + " has no element yet");
}
}
}
/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args){
int userOperation = 0, element=-1, elementPostion= -1;
DoublyLinkList startNode = null;
int elementToBeInserted;
Scanner sc = new Scanner(System.in);

//Creating Blank Buckets
for(int i = 0; i<buckets.length;i++){
buckets[i] = new HashTable();
}

do{
String menuString = "\tHash Table \nWhat operation you want to perform?"+
"\n 1. Insert Element into Bucket"+
"\n 2. Remove Element from Bucket"+
"\n 3. Find Element in Bucket"+
"\n 4. Print All Elements of Hashtable"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();

switch(userOperation){
case 1:
System.out.println("Plese enter Element to Insert: ");
elementToBeInserted = sc.nextInt();
HashTable.insertIntoBucket(elementToBeInserted);
break;
case 2:
System.out.println("Plese enter Element to Remove: ");
elementToBeInserted = sc.nextInt();
HashTable.removeFromBucket(elementToBeInserted);
break;
case 3:
System.out.println("Plese enter Element to Find: ");
elementToBeInserted = sc.nextInt();
HashTable.findInBuckets(elementToBeInserted);
break;
case 4:
HashTable.printAllElements();
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default : System.out.println("Exit from System");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited.

Java Data Structure Implementation : Doubly Link List

This program demonstrates the doubly link list implementation in Java. The Insert, Delete, Search Operation has been implemented.

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Doubly Link List Implementation in java with Add/Delete/Search Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 28th March, 2013
*/
public class DoublyLinkList {

public DoublyLinkList prev;
public int id;
public DoublyLinkList next;

public DoublyLinkList() {}

public DoublyLinkList(int id){
this.prev = null;
this.id = id;
this.next = null;
}

/**
* This method add a new node into the doubly link list at last.
* @param startNode The Starting node of link list.
* @param nodeToBeInserted The node which you want to insert
* @return void.
*/
public static void addNewNodeAtLast(DoublyLinkList startNode, DoublyLinkList nodeTobeInserted){
DoublyLinkList lastNodeOfList = getLastNode(startNode);
lastNodeOfList.next = nodeTobeInserted;
nodeTobeInserted.prev = lastNodeOfList;
}

/**
* This method add a new node into the doubly link list at start.
* @param startNode The Starting node of link list.
* @param nodeToBeInserted The node which you want to insert
* @return void.
*/
public static DoublyLinkList addNewNodeAtFirst(DoublyLinkList startNode, DoublyLinkList nodeTobeInserted){
nodeTobeInserted.prev = null;
nodeTobeInserted.next = startNode;
startNode.prev = nodeTobeInserted;
return nodeTobeInserted;
}

/**
* This method add a new node into the doubly link list at specific location.
* @param specificPositionedNode The Specific Node of which you want to insert.
* @param nodeToBeInserted The node which you want to insert
* @return void
*/
public static void addNewNodeAtSpecificPosition(DoublyLinkList specificNode, DoublyLinkList nodeTobeInserted){
if(specificNode.next == null){
addNewNodeAtLast(specificNode, nodeTobeInserted);
}else{
DoublyLinkList previousNode = specificNode.next.prev;
DoublyLinkList nextNode = specificNode.next;
nodeTobeInserted.prev = specificNode;
nodeTobeInserted.next = nextNode;
specificNode.next = nodeTobeInserted;
previousNode.prev = nodeTobeInserted;
}
}

/**
* This method search a specific node in the doubly link list.
* @param startNode start node of link list.
* @param searchNodeId search information of node which you want to search
* @return void.
*/
public static DoublyLinkList traverseLinkListSpecificNode(DoublyLinkList startNode, int searchNodeId){
DoublyLinkList specificLocationNode = null;
if(startNode.id == searchNodeId){
specificLocationNode = startNode;
}else{
while(startNode!=null){
if(startNode.id == searchNodeId){
specificLocationNode = startNode;
break;
}
startNode = startNode.next;
}
}
if(specificLocationNode!=null)
System.out.println("Specific Node Id is :"+specificLocationNode.id);
else
System.out.println("Not found");
return specificLocationNode;
}

/**
* This method removes the node from last of doubly link list.
* @param startNode Remove the last node of link list.
* @return void.
*/
public static void removeNodeFromLast(DoublyLinkList startNode){
DoublyLinkList lastNode = DoublyLinkList.getLastNode(startNode);
lastNode.prev.next = null;
}

/**
* This method removes a node from start of doubly link list.
* @param startNode Remove the start node of link list.
* @return LinkList.
*/
public static DoublyLinkList removeNodeFromFirst(DoublyLinkList startNode){
if(startNode.next==null){
startNode = null;
}else{
System.out.println("Just about to delete");
startNode = startNode.next;
startNode.prev = null;
}
return startNode;
}

/**
* This method removes a node from specific position of doubly link list.
* @param startNode start node of link list.
* @param nodeToBeRemovedId Node id of which you want to remove
* @return void.
*/
public static DoublyLinkList removeNodeFromSpecificPosition(DoublyLinkList startNode, int nodeTobeRemoved){
DoublyLinkList specificPositionedNode = DoublyLinkList.traverseLinkListSpecificNode(startNode, nodeTobeRemoved);
if(specificPositionedNode==null){
System.out.println("Node not found to delete");
return startNode;
}else{
if(specificPositionedNode.next==null){
DoublyLinkList.removeNodeFromLast(startNode);
return startNode;
}else{
if(specificPositionedNode.prev == null){
System.out.println("Removint First Node");
startNode = DoublyLinkList.removeNodeFromFirst(startNode);
return startNode;
}else{
DoublyLinkList nextNode = specificPositionedNode.next;
DoublyLinkList prevNode = specificPositionedNode.prev;
prevNode.next = nextNode;
nextNode.prev = prevNode;
return startNode;
}
}
}
}

/**
* This method traverse the whole doubly link list.
* @param startNode start node of link list.
* @return void.
*/
public static void traverseLinkList(DoublyLinkList startNode){
if(startNode == null){
System.out.println("No Element");
}else{
while(startNode!=null){
System.out.println("Node Id : "+ startNode.id);
startNode = startNode.next;
}
}

}

/**
* This method returns the last node of the doubly link list.
* @param startNode start node of link list.
* @return void.
*/
public static DoublyLinkList getLastNode(DoublyLinkList startNode){
DoublyLinkList lastNode=null;
if(startNode.next==null){
lastNode = startNode;
}else{
while(startNode.next!=null){
System.out.println("In while Loop");
lastNode = startNode.next;
startNode = startNode.next;
}
}
System.out.println("Last Node Id In Get Last Method is : "+lastNode.id);
return lastNode;
}

/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args){
int userOperation = 0,nodeId=-1, nodePostion= -1;
DoublyLinkList startNode = null;
DoublyLinkList nodeToBeInserted = null;
Scanner sc = new Scanner(System.in);
do{
String menuString = "\tDoubly Link List \nWhat operation you want to perform?"+
"\n 1. Insert New Node at Last"+
"\n 2. Insert New Node at Start"+
"\n 3. Insert New Node at Specific Position"+
"\n 4. Remove Node from Last"+
"\n 5. Remove Node from Start"+
"\n 6. Remove Node from Specific Position"+
"\n 7. Traverse Whole List"+
"\n 8. Traverse Specific Node in List"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();

switch(userOperation){
case 1:
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
if(startNode == null){
System.out.println("start Node is Null");
startNode = nodeToBeInserted;
}else{
System.out.println("Adding New Node At Last");
DoublyLinkList.addNewNodeAtLast(startNode, nodeToBeInserted);
}
break;
case 2:
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
if(startNode == null){
System.out.println("start Node is Null");
startNode = nodeToBeInserted;
}else{
System.out.println("Adding New Node At First");
startNode = DoublyLinkList.addNewNodeAtFirst(startNode, nodeToBeInserted);
}
break;
case 3:
System.out.println("Node Id after which you want to insert new node. Enter Node Id?");
nodePostion = sc.nextInt();
DoublyLinkList specificPositionedNode = DoublyLinkList.traverseLinkListSpecificNode(startNode, nodePostion);
if(specificPositionedNode==null){
System.out.println("Entered Id not found in list");
}else{
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
DoublyLinkList.addNewNodeAtSpecificPosition(specificPositionedNode,nodeToBeInserted);
}
break;
case 4:
if(startNode.next == null){
startNode = null;
}else{
DoublyLinkList.removeNodeFromLast(startNode);
}
System.out.println("Last Node has been removed");
break;
case 5:
startNode = DoublyLinkList.removeNodeFromFirst(startNode);
System.out.println("Starting Node has been removed");
break;
case 6:
System.out.println("At which position you want to delete node. Enter Position?");
nodePostion = sc.nextInt();
startNode = DoublyLinkList.removeNodeFromSpecificPosition(startNode, nodePostion);
break;
case 7:
DoublyLinkList.traverseLinkList(startNode);
break;
case 8:
System.out.println("Please enter node Id to Search : ");
nodePostion = sc.nextInt();
DoublyLinkList.traverseLinkListSpecificNode(startNode,nodePostion);
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default : System.out.println("Exit from System");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited if any.

Java Data Structure Implementation : Queue (Circular) using Array

This program demonstrates the Queue (Circular in nature) implementation using Array in Java. The Insert(Enqueue), Remove(Dequeue), Print Elements Operation has been implemented.

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Queue (Circular in nature) Implementation using Array in java with Insert/Delete/Print Operations.
* @author : Madan Gopal Singh
* @version : 3.0
* @date : 11th April, 2014
*/

public class Queue {
public static int front = -1;
public static int rear = -1;
public static int QUEUE_SIZE = 5;
public static Object[] queueList;
public Queue() {}

/**
* This method insert the element into the queue from rear end.
* @param object.
* @return void.
*/
public static void insertIntoQueue(Object obj){
System.out.println("rear value is : "+rear);
if(rear == QUEUE_SIZE-1){
System.out.println("Queue is overflow");
}else{
rear = rear+1;
if(rear == 0)
front =0;
queueList[rear] = obj;
System.out.println("Element Inserted : "+queueList[rear].toString());
}
}

/**
* This method remove the element from the queue from front end.
* @param void.
* @return Object.
*/

public static Object removeFromQueue(){
System.out.println("Rear Value at time of deletion is : "+rear);
if(rear == -1 || front == -1){
System.out.println("Queue is underflow");
return null;
}else{
Object deletedElement = queueList[front];
System.out.println("Element removed : "+queueList[front]);
if(front==rear){
front = -1;
rear = rear-1;
}else{
for(int i =front;i<=rear-1;i++){
System.out.println("Shifting element in "+i+"("+queueList[i]+") from "+(i+1)+"("+queueList[i+1]+")");
queueList[i]=queueList[i+1];
}
rear = rear-1;
}
return deletedElement;
}
}

/**
* This method print all elements of the queue.
* @param void.
* @return void.
*/
public static void printAllElements(){
if(rear==-1){
System.out.println("No Element in Queue to display");
}else{
for(int i=0;i<=rear;i++){
System.out.println("Element at position "+i+" is : "+queueList[i].toString());
}
}
}

/**
* This method to check whether element already exists or not.
* @param Object.
* @return boolean.
*/
public static boolean isElementExists(Object obj){
if(rear==-1){
return false;
}else{
for(int i=0;i<=rear;i++){
if(queueList[i].toString().equalsIgnoreCase((String)obj.toString())){
return true;
}
}
return false;
}
}

/**
* This method to check whether queue is empty or not.
* @return boolean.
*/
public static boolean isEmpty(){
if(rear==-1){
return true;
}else{
return false;
}
}

/**
* Main Method
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
queueList = new Object[QUEUE_SIZE];

int userOperation=0;
String mainMenuString = "";
Scanner sc = new Scanner(System.in);
do{
mainMenuString = "What operation you want to perform?"+
"\n 1. Insert Element "+
"\n 2. Delete Element "+
"\n 3. Print All Elements "+
"\n 4. Element Exists Or Not "+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number :";
System.out.println(mainMenuString);
userOperation = sc.nextInt();
switch (userOperation) {
case 1:
System.out.println("Please enter element to insert into queue?");
String insertElement = sc.next();
Queue.insertIntoQueue(insertElement);
break;
case 2:
Queue.removeFromQueue();
break;
case 3:
Queue.printAllElements();
break;
case 4:
System.out.println("Please enter element to check Existency?");
boolean isExists = Queue.isElementExists(sc.next());
if(isExists){
System.out.println("Exists");
}else{
System.out.println("Not Exists");
}
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default:
System.out.println("Please enter a valid operation number");
}
}while(userOperation!=-1);
}

}

Any suggestion is invited if any.

Java Data Structure Implementation : Balanced BST(AVL Tree)

This program demonstrates the Balanced Binary Tree implementation in Java. The Operation which has been implemented are –

1. Insert Into Binary Tree
2. Balance Tree Automatically After Insertion
3. LL, LR, RR, RL Rotations Implemented

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Balanced Binary Tree (AVL Tree) Implementation in java with Insert/Delete Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 22nd March, 2013
*/
public class AVLTree {
AVLTree left;
int id;
AVLTree right;
int height;
int balanceFactor;

public AVLTree() {
}

public AVLTree(int id){
left = null;
this.id = id;
right = null;
}

public AVLTree(AVLTree left,int id,AVLTree right){
this.left = left;
this.id =id;
this.right = right;
}

/**
* This method rotates the Left to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateLeftLeft(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.left;
rootNode.left = tempNode.right;
tempNode.right = rootNode;
return tempNode;
}

/**
* This method rotates the Right to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateRightRight(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.right;
rootNode.right = tempNode.left;
tempNode.left = rootNode;
return tempNode;
}

/**
* This method rotates the Left first the Right to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateLeftRight(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.left;
rootNode.left = AVLTree.rotateRightRight(tempNode);
return AVLTree.rotateLeftLeft(rootNode);
}

/**
* This method rotates the Right first then Left to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateRightLeft(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.right;
rootNode.right = AVLTree.rotateLeftLeft(tempNode);
return AVLTree.rotateRightRight(rootNode);
}

/**
* This method returns the height of the binary tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int getHeight(AVLTree rootNode){
if(rootNode == null){
return 0;
}
if(rootNode.left == null && rootNode.right == null){
return 1;
}else{
return 1+AVLTree.maximum(AVLTree.getHeight(rootNode.left),AVLTree.getHeight(rootNode.right));
}
}

/**
* This method maximum between two heights of the Binary Tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int maximum(int height1,int height2){
if(height1>=height2)
return height1;
else
return height2;
}

/**
* This method returns the balance factor of the node of binary tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int getBalanceFactor(AVLTree rootNode){
if(rootNode == null)
return 0;
else
return (AVLTree.getHeight(rootNode.left)-AVLTree.getHeight(rootNode.right));
}

/**
* This method balances the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree balanceTree(AVLTree rootNode){
int balanceFactor = AVLTree.getBalanceFactor(rootNode);
int balanceFactorSubNode;
AVLTree tempNode = null;
if(balanceFactor>1){
balanceFactorSubNode = AVLTree.getBalanceFactor(rootNode.left);
if(balanceFactorSubNode>0){
System.out.println("Rotating Left Left");
tempNode = AVLTree.rotateLeftLeft(rootNode);
}else{
System.out.println("Rotating left Right");
tempNode = AVLTree.rotateLeftRight(rootNode);
}
return tempNode;
}else{
if(balanceFactor0){
System.out.println("Rotating Right Left");
tempNode = AVLTree.rotateRightLeft(rootNode);
}else{
System.out.println("Rotating Right Right");
tempNode = AVLTree.rotateRightRight(rootNode);
}
return tempNode;
}
}
return rootNode;
}

/**
* This method add a new node into the balanced binary tree (AVL Tree).
* @param rootNode The Starting node of Tree.
* @param toBeInsertedNodeId The node which you want to insert
* @return AVLTree.
*/
public static AVLTree insertNewNodeInAVLTree(AVLTree rootNode,int toBeInsertedNodeId){
AVLTree tempRootNode = rootNode;
if(rootNode.left==null && rootNode.right==null){
if(toBeInsertedNodeId<=rootNode.id){
System.out.println("Inserting Left Branch");
rootNode.left = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Inserting Right Branch");
rootNode.right = new AVLTree(toBeInsertedNodeId);
}
}else{
if(toBeInsertedNodeId<=rootNode.id){
if(rootNode.left==null){
System.out.println("Inserting into Left Subtree");
rootNode.left = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Left Subtree");
rootNode = insertNewNodeInAVLTree(rootNode.left, toBeInsertedNodeId);
}
}else{
if(rootNode.right==null){
System.out.println("Inserting into Right Subtree");
rootNode.right = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Right Subtree");
rootNode = insertNewNodeInAVLTree(rootNode.right, toBeInsertedNodeId);
}
}
}
return tempRootNode;
}

/**
* This method performs preorder travarsal of the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static AVLTree treePreOrderTraversal(AVLTree root){
System.out.print(root.id+" ");
if(root.left==null&&root.right==null){
return root;
}else{
if(root.left!=null){
AVLTree.treePreOrderTraversal(root.left);
}
if(root.right!=null){
AVLTree.treePreOrderTraversal(root.right);
}
}
return root;
}

/**
* Main Method
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
AVLTree rootNode = null;
int nodeId = 0,userOperation=0;
String mainMenuString = "";
Scanner sc = new Scanner(System.in);
do{
mainMenuString = "What operation you want to perform on AVL Tree?"+
"\n 1. Insert New Node "+
"\n 2. Delete a Node"+
"\n 3. Preorder Traversal"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(mainMenuString);
userOperation = sc.nextInt();
switch(userOperation){
case 1:
System.out.println("Please enter the Node Id to which you want to insert : ");
nodeId = sc.nextInt();
if(rootNode==null){
rootNode = new AVLTree(nodeId);
}else{
AVLTree.insertNewNodeInAVLTree(rootNode, nodeId);
System.out.println("Height of Root Node after Insertion is :-"+AVLTree.getHeight(rootNode));
System.out.println("BalanceFactor of Root Node after Insertion is :-"+AVLTree.getBalanceFactor(rootNode));
rootNode = AVLTree.balanceTree(rootNode);
}
break;
case 2:
System.out.println("Please enter the Node Id of which you want to delete : ");
nodeId = sc.nextInt();
//AVLTree.deleteNodeFromAVLTree(rootNode,nodeId);
System.out.println("Similar to Tree Deletion. Kindly read my BST Post");
break;
case 3:
System.out.println("Preorder traversal sequence : ");
if(rootNode!=null){
AVLTree.treePreOrderTraversal(rootNode);
}else{
System.out.println("No node to traversal.");
}
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
break;
default:
System.out.println("Invalid Operation!! Please try again");
}
}while(userOperation!=-1);
}
}

Any Optimization/Suggestions are invited.

Java Data Structure Implementation : Stack using Array

This program demonstrates the Stack implementation using Array in Java. The Push, Pop, Print Elements Operation has been implemented.

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Stack Implementation using Array in java with Push/Pop/Print Operations.
* @author : Madan Gopal Singh
* @version : 2.0
* @date : 11th April, 2014
*/

public class StackUsingArray {

public static Object[] stackElements;
public static int top = -1;
public static int STACK_SIZE = 5;

/**
* This method push the element from the stack.
* @param void.
* @return void.
*/
public static void push(Object insertElement){
if(top==STACK_SIZE-1){
System.out.println("Stack Overflow");
}else{
top=top+1;
stackElements[top] = insertElement;
Object insertedElement = stackElements[top];
System.out.println("Top of Stack : "+top);
System.out.println(insertedElement.toString()+" inserted at top of stack");
}
}

/**
* This method pop the element from the stack.
* @param void.
* @return void.
*/
public static Object pop(){
if(top==-1){
System.out.println("Stack Underflow");
return null;
}else{
Object deletedElement = stackElements[top];
System.out.println(deletedElement.toString()+" deleted from top of stack");
top = top-1;
return deletedElement;
}
}

/**
* This method print all elements of the stack.
* @param void.
* @return void.
*/
public static void printAllElements(){
System.out.println("Printing element from top "+top);
if(top == -1){
System.out.println("Stack has no element");
}else{
int i = top;
while(i>=0){
System.out.println("Element at position "+ i + "is :- "+stackElements[i].toString());
i = i-1;
}
}
}

/**
* This method to check whether element already exists or not.
* @param Object.
* @return boolean.
*/
public static boolean isElementExists(Object obj){
if(top==-1){
return false;
}else{
int i = top;
while(i>=0){
if(stackElements[i].toString().equalsIgnoreCase((String)obj.toString())){
return true;
}
i = i-1;
}
return false;
}
}

/**
* This method to check whether stack is empty or not.
* @return boolean.
*/
public static boolean isEmpty(){
if(top==-1){
return true;
}else{
return false;
}
}

/**
* Main Method
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
stackElements = new Object[STACK_SIZE];
int userOperation=0;
String mainMenuString = "";
Scanner sc = new Scanner(System.in);
do{
mainMenuString = "What operation you want to perform?"+
"\n 1. Push Element "+
"\n 2. Pop Element "+
"\n 3. Print All Elements "+
"\n 4. Cheque Element Exists Or Not "+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number :";
System.out.println(mainMenuString);
userOperation = sc.nextInt();
switch (userOperation) {
case 1:
System.out.println("Please enter element to push into stack?");
String pushElement = sc.next();
StackUsingArray.push(pushElement);
break;
case 2:
StackUsingArray.pop();
break;
case 3:
StackUsingArray.printAllElements();
break;
case 4:
System.out.println("Please enter element to check Existency?");
boolean isExists = StackUsingArray.isElementExists(sc.next());
if(isExists){
System.out.println("Exists");
}else{
System.out.println("Not Exists");
}
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default:
System.out.println("Please enter a valid operation number");
}
}while(userOperation!=-1);

}

}

Any suggestion is invited if any.