Hashing Using Linear Probing : Java Program

Algorithm to insert a value in linear probing

 

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted, x

Step 2:  let i = 0

Step 3 :compute the index at which the x has to be inserted in hash table

                index = (x+ i) % TABLE_SIZE

Step 4: if there is no element at that index then  insert the value at index and STOP

Step 5: If there is already an element at that index

                step 4.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

Algorithm to search a value in linear probing

 

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, x

Step 2:  let i = 0

Step 3: compute the index at which the x can be found
               index = (x+ i) % TABLE_SIZE

Step 4: if the element at that index is same as the search value then print element found and  STOP

Step 5: else

                step 5.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

 

Linear Probing program

import java.util.Scanner;

 

public class LinearProbing

{

      int htable[],tableSize;

      public void insert(int x)

      {

            int i;

            for(i=0;i<tableSize;i++)

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == -1)

                  {

                        htable[index]=x;

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("cannot insert as table is full");

      }

      public void display()

      {

            System.out.println("hash table entries are");

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

            {

               System.out.println("element at index "+i+" is " +htable[i]);

            }

      }

      public void search(int x)

      {

            int i;

            for(i=0;i<tableSize;i++)

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == x)

                  {

                        System.out.println("Search found at index "+index);

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("Search element not found");

      }

      public static void main(String[] args)

      {

            LinearProbing ob =new LinearProbing();

            Scanner sc = new Scanner(System.in);

            System.out.println("enter size of the table");

            ob.tableSize=sc.nextInt();

            ob.htable=new int[ob.tableSize];

            for(int i=0;i<ob.tableSize;i++)

                        ob.htable[i]=-1;

            while(true)

            {

              System.out.println("1. insert 2. display 3. search 4. exit");

                  int choice=sc.nextInt();

                  switch(choice)

                  {

                  case 1:

                        System.out.println("enter key to be inserted");

                        x=sc.nextInt();

                        ob.insert(x);

                        break;

                  case 2:

                        ob.display();

                        break;

                  case 3:

                        System.out.println("enter key to be searched");

                        x=sc.nextInt();

                        ob.search(x);

                        break;

                  case 4: return;

                  default:

                       System.out.println("invalid");

                  }

            }

 

      }

 

}

Output:
enter size of the table
10
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
12
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
13
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
14
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
22
press 1. insert 2. display 3. search 4. exit
2
hash table entries are
element at index 0 is -1
element at index 1 is -1
element at index 2 is 12
element at index 3 is 13
element at index 4 is 14
element at index 5 is 22
element at index 6 is -1
element at index 7 is -1
element at index 8 is -1
element at index 9 is -1
press 1. insert 2. display 3. search 4. exit
3
enter key to be searched
22
Search element found at index 5
press 1. insert 2. display 3. search 4. exit

4

General Algorithm to insert a node into B tree

General Algorithm to insert a node into B tree

1.      Find the node into which new key should be inserted by doing search using binary search logic

2.      if the node is not full, insert the key into the node using an appropriate sorting algorithm

3.      if the node is full, split the node into two and push the key upward into the parent node

4.      if the parent node is also full, follow the same procedure until either some space is found in a previously existing node or a new root node is created

Infix to Postfix Conversion in java

Step 1: Start

Step 2: Read the infix expression

Step 3: Scan every character of infix expression,

IF scanned character is

3.1 ( , then  push it on the stack

3.2 operand (whether a digit or a character) , add it to postfix expression

3.3  ) , then

a. Repeatedly pop from stack and add it to the postfix expression until  ( .

b. Discard the ( . That is, remove the ( from stack and do not add it to the postfix

3.4 operator, then

a. Repeatedly pop from stack and add each operator (popped from the stack) to the postfix expression which has the same precedence or a higher precedence

b. Push the operator to the stack

Step 4: Repeatedly pop from the stack and add it to the postfix expression until the stack is empty

Step 5: Stop


import java.util.Scanner;

class SNode
{
    char data;
    SNode next;
}
class Stack
{
    SNode top=null;
   public void push(char val)
    {
        SNode newnode = new SNode();
        newnode.data=val;
        if(top == null)
            top=newnode;
        else
        {
            newnode.next=top;
            top=newnode;
        }   
    }
    public char pop()
    {
            char temp=top.data;
            top=top.next;
            return temp;
    }
}

public class PostfixConversionDemo
{
    public static int getPriority(char ch)
    {
        if(ch == '*' || ch == '/' || ch == '%')
                return 2;
        if(ch == '-' || ch == '+')
            return 1;
        return 0;
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        Stack ob = new Stack();
        System.out.println("Enter infix experession");
        StringBuffer infix=new StringBuffer(sc.next());
        StringBuffer postfix=new StringBuffer();
        char temp;
        for(int i=0;i<infix.length();i++)
        {
            char ch=infix.charAt(i);
            if(ch == '(')
                ob.push(ch);
            else if(ch == ')')
            {
                while( ob.top.data != '(')
                {
                     postfix.append(ob.pop());
                }
           
                ob.pop();
            }
            else if(ch == '*' ||ch == '/' ||ch == '+' ||ch == '-'|| ch == '%' )
            {
                while(ob.top != null && getPriority(ob.top.data) >=  getPriority(ch))
                {
                    postfix.append(ob.pop());                   
                }
                ob.push(ch);
            }
            else
                postfix.append(ch);
        }
        while(ob.top != null)
            postfix.append(ob.pop());
        System.out.println(postfix);
    }
}

Single Linked List Program in Java

import java.util.Scanner;
class SLLNode
{
    int data;
    SLLNode next;
}
class SLL
{
    SLLNode head=null,tail=null;
    public void create(int val)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        if(head == null)
            head=tail=newnode;
        else
        {
            tail.next=newnode;
            tail=newnode;
        }
    }
    public void display()
    {
        if(head == null)
             System.out.println("no SLL");
        else
        {
            SLLNode c=head;
            while(c != null)
            {
                System.out.print(c.data+"->");
                c=c.next;
            }
        }
    }
    public void insertBeg(int val)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        if(head == null)
            head=tail=newnode;
        else
        {
            newnode.next=head;
            head=newnode;
        }
       
    }
    public void insertMiddle(int val,int pos)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        SLLNode c = head;
        for(int i=1;i<pos-1;i++)
            c=c.next;
        newnode.next=c.next;
        c.next=newnode;
       
    }
    public void delEnd()
    {
        SLLNode c = head;
        while(c.next != null)
            c=c.next;
        System.out.println("deleted element = "+c.data);
        c.next=null;
    }
    public void delMiddle(int pos)
    {
        SLLNode c = head;
        for(int i=1;i<pos-1;i++)
            c=c.next;
        System.out.println("deleted element = "+c.next.data);
        c.next=c.next.next;
    }
    public void delBeg()
    {
        if(head != null)
        {
            System.out.println("deleted element = "+head.data);
            head=head.next;
        }
    }
}

public class SLLDemo
{
    public static void main(String args[])
    {
      SLL ob = new SLL();
      Scanner sc = new Scanner(System.in);
        while(true)
        {
            System.out.println("1. InsertEnd/Create 2.InserBeg 3. InsertMiddle");
            System.out.println("4. DeleteEnd  5.DeleteBeg   6. DeleteMiddle");
            System.out.println("7. Display 8.Exit");
            int choice=sc.nextInt();
            switch(choice)
            {
                case 1:
                case 2:
                case 3:
                    System.out.println("");
                    int choice1=sc.nextInt();
                    System.out.println("Enter data to be inserted");
                    int val = sc.nextInt();
                    if(choice == 1)
                        ob.create(val);
                    else if(choice == 2)
                        ob.insertBeg(val);
                    else
                    {
                        System.out.println("Enter position");
                        int pos=sc.nextInt();
                        ob.insertMiddle(val,pos);
                    }
                    break;
                case 4:   ob.delEnd();
                            break;
                case 5:   ob.delBeg();
                            break;
                case 6: 
                        System.out.println("Enter position");
                        int pos=sc.nextInt();
                        ob.delMiddle(pos);
                        break;
                case 7:
                        ob.display();
                        break;
                default:
                        System.exit(0);
            }
        }
    }
}

===========================================
import java.util.Scanner;
class SLLNode
{
    int data;
    SLLNode next;
}
class SLL
{
    SLLNode head=null,tail=null;
    public void create(int val)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        if(head == null)
            head=tail=newnode;
        else
        {
            tail.next=newnode;
            tail=newnode;
        }
    }
    public void display()
    {
        if(head == null)
             System.out.println("no SLL");
        else
        {
            SLLNode c=head;
            while(c != null)
            {
                System.out.print(c.data+"->");
                c=c.next;
            }
        }
    }
    public void insertBeg(int val)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        if(head == null)
            head=tail=newnode;
        else
        {
            newnode.next=head;
            head=newnode;
        }
     
    }
    public void insertMiddle(int val,int pos)
    {
        SLLNode newnode = new SLLNode();
        newnode.data=val;
        newnode.next=null;
        SLLNode c = head;
        for(int i=1;i<pos-1;i++)
            c=c.next;
        newnode.next=c.next;
        c.next=newnode;
     
    }

}

public class SLLDemo
{
    public static void main(String args[])
    {
      SLL ob = new SLL();
      Scanner sc = new Scanner(System.in);
        while(true)
        {
            System.out.println("1. Insert 2. Display 3.Exit");
            int choice=sc.nextInt();
            switch(choice)
            {
                case 1:
                    System.out.println("1. InsertAtEnd 2.InsertAtBeg 3. InsertAtMiddle");
                    int choice1=sc.nextInt();
                    System.out.println("Enter data to be inserted");
                    int val = sc.nextInt();
                    switch(choice1)
                    {
                        case 1:   ob.create(val);
                                    break;
                        case 2:   ob.insertBeg(val);
                                    break;
                        case 3:   System.out.println("Enter position");
                                    int pos=sc.nextInt();
                                    ob.insertMiddle(val,pos);
                                    break;
                    }
                    break;
                case 2:   ob.display();
                            break;
                default:
                        System.exit(0);
            }
        }
    }
}