HashProbing

public class LinearProbHashing {
int[] table;
int size;

LinearProbHashing(int s){
size = s;
table = new int[size];
}

int rehash(int key){
return ((key+1)%size);
}

public void insert(int key){
int hash = key%size;
int RH = 0;
if(table[hash] == 0){
table[hash] = key;
}else{
RH = rehash(key);
while(RH != 0){
RH = rehash(RH++);
table[RH] = key;
}
}
}

public void printhashtable(){
for(int i=0; i<size; i++){
System.out.print(" "+table[i]);
}
}
}

=============================================

public class HashDemo {
public static void main(String[] args) {
// HashTable table1 = new HashTable(10);
LinearProbHashing table1 = new LinearProbHashing(10);
table1.insert(345);
table1.insert(245);
table1.insert(344);
table1.insert(312);
table1.insert(335); 
table1.printhashtable();
}
}

Hashing

class Node{
int data;
Node next;

Node(int d){
data=d;

}

}
public class HTable {
Node [] Table;
int size;
HTable(int s){
size=s;
Table =new Node[size];

}
public void insert(int key){
Node newNode= new Node(key);
int hash =key%size;

if(Table[hash]==null)
Table[hash] = newNode;
else{
Node HashRef=Table[hash];
newNode.next =HashRef;
Table[hash] =newNode;


}
}
public void printhashtable(){
Node href = null;
for(int i=0; i<size; i++){
href = Table[i];
System.out.print("  " + href.data);
href = href.next;

}
System.out.println(" ");

}

}

==================================================



public class HDemo {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
         HTable table1= new HTable(15);
         table1.insert(345);
         table1.insert(445);
         table1.insert(245);
         table1.insert(045);
         table1.insert(145);
         table1.printhashtable();
       
}

}

BubbleSort

public class bsorting {
public static void main(String a[]){
 int i;
 int array[] = {10,20,9,12,13,11,15,30,25};
 System.out.print("Before Sorting:");
 for(i = 0; i < array.length; i++)
 System.out.print( array[i]+"  ");
 System.out.println();
 bsort(array, array.length);
 System.out.print("After Sorting:");
 for(i = 0; i <array.length; i++)
 System.out.print(array[i]+"  ");
 System.out.println();

 }

 public static void bsort( int a[], int n ){
 int i, j,temp=0;
 for(i = 0; i < n; i++){
 for(j = 1; j < (n-i); j++){
 if(a[j-1] > a[j])
 {
 temp = a[j-1];
 a[j-1]=a[j];
 a[j]=temp;
 }
 }
 }
 }
}

Binary Tree

public void delete (int d){

TNode Temp = Root;
TNode Parent = Root;

while (Temp!=null) {
if (d<Temp.data && Temp.data!=d){
Today's DSA Code:

Parent = Temp;
Temp=Temp.L;
}
else
{
Temp= Temp.R;
}
}

if (Temp==null){
System.out.println ("Not Found");
}

else {
if (Temp.R == null && Temp.L == null){ //no child

if (Temp.data < Parent.data){
Parent.L = null;
}
else
{
Parent.R = null;

}
}
}

else
if ((Temp.R == null && Temp.L != null) || (Temp.R!=null && Temp.L == null)){
if(Temp.R == null) {
if(d<Parent.data)
Parent.L=Temp.L;

}

else {
Parent.R = Temp.L;

}
if (Temp.L == null){

}

}

PriortyQueue

public class Queue {

int [] Q;
int F;
int R;

Queue (int Qsize){
Q= new int[Qsize];
F=0;
R=-1;

}
public void insert (int v){
if (R==-1){
R++;
Q[R]=v;

}
else{
for (int i=F; i<=R&& Q[i]<=v; i++){

}
if(i==R){
R++;
Q[R]=v;

}
else if (i==F){
for(j=R;j>0;j--){
Q[j+1]= Q[j];

}
R++;
Q[i]=v;

}
}
}
}

CircularQueue

public class CircularQueue {

int[] Q;
int R,F;

CircularQueue(int size)
{
Q=new int[size];
R=size-1;
F=size-1;
}

public boolean isFull(){
if (F==R)
return true;
else
return false;
}
 public boolean isEmpty()
 {
if (R==F)
return true;
else
return false;
 }


public void insertion(int item)
{
if(R==Q.length-1)
R=0;
else
{
R++;
if (isFull())
{
System.out.println("Queue overflow");
R--;
return;
}
}

Q[R]=item;

}

public int Delete()
{
if(isEmpty()){
System.out.println("Queue underflow");
return -1;
}
else{
if(F==Q.length-1)
F=0;
else
F++;
}
    return Q[F];

}

public void display(){
for(int i=0; i<Q.length; i++)
System.out.println(Q[i]);
}



}

////////////////////////////////////////////////////////////////////////



public class Queuedemo {

/**
* @param args
*/
public static void main(String[] args) {
CircularQueue q= new CircularQueue(10);
q.insertion(10);
q.insertion(11);
q.insertion(12);
q.insertion(13);
q.insertion(14);
q.insertion(15);
q.insertion(16);
q.Delete();

q.display();




}

}

///////////////////////////////////////////////////

Application Of Stack

LineStack
public class LineStack<T> {
StackNode <T> Top;

public Boolean isEmpty(){
if (Top==null)
return true;
else
return false;


}

public void push (T data) {
StackNode<T> newNode = new StackNode<T> (data);
if (isEmpty()){
Top=newNode;
else
newNode.next=Top;
Top=newNode;

}


}
}

////////////////////////////////


StackNode:

public class StackNode<T>  {

T data;
StackNode<T>next;

StackNode(T d){
data=d;

}

}

/////////////////////////////////////////

public class StackAppDemo {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

LineStack<Character> MyStk= new LineStack<Character>()

}

}

//////////////////////////////////////////////////

public class ArithematicExp {

public void infixToPostfix(String Exp){

String Postfix;

LinkStack<T> ExpStk=new LinkStack<Character>;

int i=0;

while (i<Exp.length()){

char ch=Exp.charAt(i);

switch(ch){

case ch='('||'{'||'['

{

}

}

}

i++;

}

}

Stack Class OverFlow

• public class ParenthesisValidation {
  public Boolean paranthesisCheck(String exp) {
  MyStack Mystk = new MyStack(exp.length());
  char ch;
  Boolean Valid = true;
  for (int i = 0; i < exp.length(); i++) {
  ch = exp.charAt(i);
  if (ch == '[' || ch == '{' || ch == '(') {
  Mystk.PUSH(ch);
  } else {
  if (ch == ']' || ch == '}' || ch == ')') {
  if (Mystk.isEmpty()) {
  Valid = false;
  }
  char c = Mystk.POP();
  if(c == '[' && ch == ']' || c == '{' && ch == '}' || c == '(' && ch == ')'){
  
  }
  }
  }
  }
  return true;
  }
  }
• 

  1:15pm

  Shiraz Sohail

  
  public class MyStackDemo {
  

  public static void main(String[] args) {
  MyStack MYstk = new MyStack(10);
  ParenthesisValidation Par = new ParenthesisValidation();
  Par.paranthesisCheck("{(2+3)*3}");
  
  /* MYstk.PUSH(23);
  MYstk.PUSH(34);
  MYstk.PUSH(66);

  System.out.println(MYstk.POP());
  System.out.println(MYstk.POP());
  System.out.println(MYstk.POP());
  System.out.println(MYstk.POP()); */
  }

  }
• 

  1:15pm

  Shiraz Sohail

  
  public class MyStack {
  char[] Stack;
  int top;
  
  MyStack(int s){
  Stack = new char[s];
  top = -1;
  }
  
  public Boolean isFull(){
  if(top == Stack.length-1)
  return true;
  else
  return false;
  }
  
  public Boolean isEmpty(){
  if(top == -1)
  return true;
  else
  return false;
  }
  

  public void PUSH(char d){
  if(isFull()){
  System.out.println("Stack Overflow");
  }
  else{
  Stack[++top] = d;
  }
  }
  
  public char POP(){
  if(isEmpty()){
  System.out.println("Stack Underflow");
  return ' ';
  }
  else{
  char T=Stack[top];
  top--;
  return T;
  }
  }
  
  }

CircularLinkList

class Node<T>{
T data;
Node<T> next;

Node(T d)
{
data=d;

}
}
public class CircularList<T> {
Node<T> Head;
Node<T> Tail;
int TotalNodes;
public void insert(T d){
Node<T> newNode=new Node<T>(d);
TotalNodes++;
Node<T> T=Head;
if(Head==null){
Head=newNode;
Tail=newNode;
}
else{
newNode.next=T;
Tail.next=newNode;
Head=newNode;
}


}
/*
public int JosephusSolution(){
Node Temp=Head;
Node Prev=null;

int counter;

for(int i=1; i<TotalNodes;i++){

counter=(int)(Math.random()*(10)+1); // random counter to avoid baisness

for(int j=1;j<counter;j++){
Prev=Temp;
Temp=Temp.next;
}

Prev.next=Temp.next; // update reference for deletion

if(Temp==Head){ // if the deleted node is Head node
Tail.next=Head.next;
Head=Head.next;
}
if(Temp==Tail){ // if the deleted node is Tail node
Tail=Prev;
}
//Continue for next deletion
Temp=Prev.next;
}// end of outer loop

return Head.data; // return the Winner

}
*/
public void display(){
Node<T> T=Head;
System.out.println(T.data);
T=T.next;
while(T!=Head)
{
System.out.println(T.data);
T=T.next;
}
}

}

Stack

public class DNode()
{
DNode prev;
int data;
DNode next;

DNode(int d){
data=d;
}
}

//////////////////////////////////////////////////////////////////////////

public class DNode()
{
DNode prev;
int data;
DNode next;

DNode(int d){
data=d;
}
}


public class DoublyLinkList{
DNode Head;
public void insert(int d){
DNode newNode=new DNode(d);
DNode Temp=Head;

if (Temp==null)
{
Head=newNode;
}
else{
while(Temp.data<newNode.data && Temp.next!=null)\
{
Temp=Temp.next;
}
if(Temp.next==null) // last insertion
{
Temp.next=newNode;
newNode.prev=Temp;
}
else if(Temp==Head) // first insertion
{
newNode.next=Temp;
Temp.prev=newNode;
Head=newNode;
}
else{
newNode.next=Temp;
newNode.prev=Temp.prev;
Temp.prev.next=newNode;
Temp.prev=newNode;
}

}

}
public void display(){
DNode Temp=Head;
while(Temp != null)
{
System.out.print(" " +Temp.data)
Temp=Temp.next;
}
}
}
}

/////////////////////////////////////////////////////////////

Main Class

public class doublyLinkListdemo{

public static void main(string[] args ){
DoublyLinkList DList= new DoublyLinkList();
DList.insert(23);
DList.insert(26);
DList.insert(28);
DList.insert(29);


Dlist.display();

}

}

CircularLinkList, Demo

CircularLinkList:

class Node{
int data;
Node next;

Node(int d){
data = d;
}
}

public class CircularList {
Node Head;
Node Tail;

public void insert(int d){
Node newNode = new Node(d);
Node T =Head;
if(Head == null){
Head = newNode;
}
else{
newNode.next=T;
Tail.next=newNode;
Head=newNode;

}
}
public void display(){
    Node T=Head;
    System.out.println(T.data);
    T=T.next;
    while(T!=Head){
        System.out.println(T.data);
        T=T.next;
    }
}
}

////////////////////////////////////////

public class CircularListDemo {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        CircularList CL=new CircularList();
        for (int i=0; i<10; i++){
            CL.insert(i+1);
           
        }

    }

}

Node, Linklist, LinklistDemo

Node:

public class Node{
int data;
Node next;

Node (int d)
{

data = d ;
// next= null;


}

}

//////////////////

LinkList:

public class Linklist {

Node head;
public void insert(int d){
Node newNode= new Node(d);

if (head==null)
head=newNode;
else
{
Node Temp;
//Prev;
Temp=head;
//Prev=head;

while (Temp.next!=null && d>Temp.data){

Temp=Temp.next;
}
if (Temp.next==null){  //insert as last node

}
else if (Temp==head) // insert as first node
{
newNode.next=head;
head=newNode;
}
else{
newNode.next=Temp.next;
Temp.next=newNode;

}
}

}
public void display(){
Node Temp= head;
while(Temp != null){

}
}
}

///////////////////

LinkListDemo:

public class LinkListDemo {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Linklist Mylist=new Linklist();

Mylist.insert(30);

Mylist.insert(50);

Mylist.insert(60);

Mylist.insert(70);

}

}

DSA Lab Work

// Class AlgorithmAnalysis
public class AlgorithmAnalysis {

public boolean LinearSearch(int [] array1,int key){
for(int k = 0 ;k <array1.length; k++){
if (key==array1[k]){
System.out.println("Linear Search :key is at  index :"+ k );
return true;
}
}
System.out.println(" Linear Seatch:key is not present");
return false;
}

public boolean BinarySearch(int [] array1, int key){

int low = 0;
        int high = array1.length - 1;
       
        while(high >= low) {
            int middle = (low + high) / 2;
           
            if(array1[middle] == key) {
System.out.println("Binary Search :key is at  index :"+ (middle-1) );
                return true;
            }
            if(array1[middle] < key) {
                low = middle + 1;
            }
            if(array1[middle] > key) {
                high = middle - 1;
            }
       }
System.out.println(" Binary Seatch:key is not present");
       return false;
}

public void display(int[] arr) {
// TODO Auto-generated method stub

}
}

Main Code


import java.util.Arrays;
public class AlgorithmAnalysisDemo{
public static void main(String[] args) {
AlgorithmAnalysis Algo = new AlgorithmAnalysis();
int n= 100;
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = (int)(Math.random()*1000)+1;
}
Algo.display(arr);

Arrays.sort(arr);
int StartTime = (int) System.nanoTime();
System.out.println(Algo.LinearSearch(arr, arr[n-1]));
int EndTime = (int) System.nanoTime();
System.out.println("Linear Search Run Time is "+ (EndTime-StartTime) + " nano seconds.");

int StartTime1 = (int) System.nanoTime();
System.out.println(Algo.BinarySearch(arr, arr[n-1]));
int EndTime1 = (int) System.nanoTime();
System.out.println("Binary Search Run Time is "+ (EndTime1-StartTime1) + " nano seconds.");

}
}

Class AlgorithmAnalysis With Main Class

// Class AlgorithmAnalysis
public class AlgorithmAnalysis {

public boolean LinearSearch(int[] arr, int key)
{
for (int i=0;i<arr.length;i++)
if(key==arr[i])
return true;
return false;
}
public boolean BinarySearch(int[] arr, int key)
{
int Low=0;
int Upper=arr.length-1;
int m=(Low+Upper)/2;

while(key!=arr[m] && Low>0 && Upper<arr.length)
{
if(key<arr[m])
Upper=m-1;
else
Low=m+1;
}
if (key==arr[m])
return true;
else
return false;
}

public void display(int[] arr) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i]+" , ");
System.out.println();

}

}


import java.util.Arrays;
public class AlgorithmAnalysisDemo{
public static void main(String[] args) {
AlgorithmAnalysis Algo = new AlgorithmAnalysis();
int n= 100;
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = (int)(Math.random()*1000)+1;
}
Algo.display(arr);

Arrays.sort(arr);
int StartTime = (int) System.nanoTime();
System.out.println(Algo.LinearSearch(arr, arr[n-1]));
int EndTime = (int) System.nanoTime();
System.out.println("Linear Search Run Time is "+ (EndTime-StartTime) + " nano seconds.");

int StartTime1 = (int) System.nanoTime();
System.out.println(Algo.BinarySearch(arr, arr[n-1]));
int EndTime1 = (int) System.nanoTime();
System.out.println("Binary Search Run Time is "+ (EndTime1-StartTime1) + " nano seconds.");

}
}

Insertion

public class ArrayList {

int [] arr;
int arrSize;
int currentIndex;


public void MyArrayList(int size) {
arr=new int[size];
arrSize=size;
currentIndex=-1;

}

public void insert (int value){
   if (currentIndex >= arr.length-1){
  int [] Temp =new int [arrSize*2];
  for (int i = 0; i<arr.length ; i++)
  {
  Temp[i] = arr[i];
  }
  currentIndex ++;
  arr = Temp;
  arr[currentIndex] = value;
 
 
   }
         
}