Javascript Data Structure Implementation : Singly LinkedList

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

Find the Javascript Code below :

// Class representing the node
function Node(data) {
this.data = data;
this.next = null;
}

// Class representing the SinglyLinkedList
function SinglyList() {
this._length = 0;
this.head = null;
}

// Function to add the new node into the list
SinglyList.prototype.add = function(value) {
var node = new Node(value),
currentNode = this.head;

// 1st use-case: an empty list
if (!currentNode) {
this.head = node;
this._length++;

return node;
}

// 2nd use-case: a non-empty list
while (currentNode.next) {
currentNode = currentNode.next;
}

currentNode.next = node;

this._length++;

return node;
};

// Function to search the node in list
SinglyList.prototype.searchNodeAt = function(position) {
var currentNode = this.head,
length = this._length,
count = 1,
message = {failure: 'Failure: non-existent node in this list.'};

// 1st use-case: an invalid position
if (length === 0 || position length) {
throw new Error(message.failure);
}

// 2nd use-case: a valid position
while (count < position) {
currentNode = currentNode.next;
count++;
}

return currentNode;
};

// Function to remove element from the list
SinglyList.prototype.remove = function(position) {
var currentNode = this.head,
length = this._length,
count = 0,
message = {failure: 'Failure: non-existent node in this list.'},
beforeNodeToDelete = null,
nodeToDelete = null,
deletedNode = null;

// 1st use-case: an invalid position
if (position length) {
throw new Error(message.failure);
}

// 2nd use-case: the first node is removed
if (position === 1) {
this.head = currentNode.next;
deletedNode = currentNode;
currentNode = null;
this._length--;

return deletedNode;
}

// 3rd use-case: any other node is removed
while (count < position) {
beforeNodeToDelete = currentNode;
nodeToDelete = currentNode.next;
count++;
}

beforeNodeToDelete.next = nodeToDelete.next;
deletedNode = nodeToDelete;
nodeToDelete = null;
this._length--;

return deletedNode;
};

Any suggestion is invited if any.

Advertisements

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.

LargeInt Abstract Data Type Implementation : Using Link List

This program demonstrates the Large Integer Abstract Data Type implementation using link list in Java.

The Operation implemented :
1. Declaring Large Integer Data Type
2. Addition of two Large Non negative Integers

The Operation which are under implementation
3. Addition of two Large negative Integers
4. Subtraction of two Large Integers
5. Multiplication of two Large Integers
6. Divide of two Large Integers

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

LargeInt Abstract Data Type

LargeInt Abstract Data Type

Find the Java Code below :

This Class shows the showcase/usecase (How to use LargeInt Class) of the LargeInt Class

/*
* This class demonstrates use of Large Int Class in Java.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 14th April, 2014
*/
public class UseLargeIntDemo{
/**
* The main method
* @param void
* @return Sting[].
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String snumberOne="",snumberTwo="";
LargeInt numberOne = null, numberTwo = null, sum = null;
System.out.println("Please Enter Large Integer Number 1 : ");
snumberOne = sc.next();
System.out.println("Please Enter Large Integer Number 2 : ");
snumberTwo = sc.next();
numberOne = new LargeInt(snumberOne); // Creating Object of LargeInt for number 1
numberTwo = new LargeInt(snumberTwo); // Creating Object of LargeInt for number 2
sum = numberOne.add(numberTwo); // Performing Addition Operation
System.out.println(sum); // Printing Data
}
}

This is the actual implementation of LargeInt Class


/*
* This class represents the LargeInt Abstract Data Type in java. It have Add Method Implemented.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 14th April, 2014
*/
class LargeInt {
private List L;
private LargeInt(){
L = new List();
}

public LargeInt(String str){
L = new List();
populate(str);
}
/**
* This method populates the string into the list.
* @param String
* @return void.
*/
void populate(String str){
int i=0;
int length = str.length();
while(i<length){
this.prepend(str.charAt(i)-'0');
i++;
}
while(i<100){
this.append('0'-'0');
i++;
}
}

/**
* This method appends single digit in beguning of the list.
* @param int
* @return void.
*/
public void append(int num){
this.L.append(num);
}
/**
* This method appends single digit at last of the list.
* @param int
* @return void.
*/
public void prepend(int num){
this.L.prepend(num);
}
/**
* This method adds the number digit by digit from two lists.
* @param LargeInt
* @return LargeInt.
*/
public LargeInt add(LargeInt B){
LargeInt c = new LargeInt();
int carry = 0,sum = 0;
ListNode temp1=this.L.getHead();
ListNode temp2=B.L.getHead();
while(temp1!=null){
sum = temp1.getData()+temp2.getData()+carry;
if(sum%10!=0){
carry = sum/10;
sum = sum%10;
}else{
if(sum==10){
carry = sum/10;
sum = sum%10;
}else{
carry = 0;
}
}
c.prepend(sum);
temp1=temp1.getNext();
temp2=temp2.getNext();
}
if(carry!=0)
c.prepend(carry);
return c;
}
/**
* This method prints the number represented by the list.
* @param int
* @return void.
*/
public void print(){
this.removeZeroes();
this.L.print();
}

@Override
public String toString() {
this.removeZeroes();
return L.toString();
}
/**
* This method remove the unneccessary zeros from the list.
* @param void
* @return void.
*/
public void removeZeroes(){
ListNode temp=this.L.getHead();
while(temp!=null){
if(temp.getData()==0){
this.L.popFront();
}else{
return;
}
temp=temp.getNext();
}
}
}

This is the List used for implementation


/*
* This class demonstrates Link List Node Representation in java.
* @author : Madan Gopal Singh
* @version : 3.0
* @date : 14th April, 2014
*/
class ListNode{

private int data;
private ListNode next;

public ListNode(){}

public ListNode(int num){
data=num;
next = null;
}

public int getData(){
return data;
}

public void setData(int x){
data = x;
}

public void setNext(ListNode p){
next = p;
}
public ListNode getNext(){
return next;
}
}
/*
* This class demonstrates Link List Representation in java.
* @author : Madan Gopal Singh
* @version : 3.0
* @date : 14th April, 2014
*/
class List{
private ListNode Head;
public List(){
Head=null;
}
public ListNode getHead(){
return Head;
}
public void setHead(ListNode p){
Head = p;
}
/**
* This method returns last node of the list.
* @return ListNode.
*/
public ListNode last(){
ListNode temp=Head;
if(Head==null) return null;
while(temp.getNext()!=null){
temp=temp.getNext();
}
return temp;
}
/**
* This method appends the node at last in the list.
* @param int
* @return void.
*/
public void append(int num){
ListNode new_node = new ListNode(num);
ListNode temp=Head;
if(temp==null){
Head = new_node;
return;
}
while(temp.getNext()!=null) temp=temp.getNext();
temp.setNext(new_node);
}
/**
* This method appends the node at beguning of the list.
* @param int
* @return void.
*/
public void prepend(int num){
ListNode new_node = new ListNode(num);
new_node.setNext(Head);
Head = new_node;
}
/**
* This method delete the last node of the list.
* @param void
* @return void.
*/
public void popBack(){
ListNode temp=Head,prev=null;
//NULL list
if(Head==null){System.out.println("List is Empty");}
//single element
if(Head.getNext()==null){
//delete Head;
Head=null;
return;
}
while(temp.getNext()!=null){
prev = temp;
temp=temp.getNext();
}
temp=null;
prev.setNext(null);
}
/**
* This method prints the list data.
* @param void
* @return void.
*/
public void print(){
ListNode temp=Head;
while(temp!=null){
System.out.print(temp.getData());
temp=temp.getNext();
}
}

@Override
public String toString() {
ListNode temp=Head;
String listData="";
while(temp!=null){
listData += temp.getData();
temp=temp.getNext();
}
return listData;
}
/**
* This method append the pased list to last of the current list.
* @param List
* @return void.
*/
public void copy(List L){
Head = null;
ListNode temp = L.Head;
while(temp!=null){
this.append(temp.getData());
temp=temp.getNext();
}
}
/**
* This method prints the list data in reverse order.
* @param void
* @return void.
*/
public void printReverse(){
ListNode curr=Head;
ListNode prev_last=null;

while(Head!=null && prev_last!=Head){
curr = Head;
while(curr.getNext()!=prev_last){
curr = curr.getNext();
}
System.out.println(curr.getData());
prev_last = curr;
}
}

/**
* This method deletes the node from bugining of the lise.
* @param void
* @return void.
*/
public void popFront(){
ListNode temp=Head,next=null;
//NULL list
if(Head==null){System.out.println("List is Empty");}
//single element
if(Head.getNext()==null){
//delete Head;
Head=null;
return;
}else{
next = temp.getNext();
Head = next;
}
}

}

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.