ADVANCE JAVA

import java.sql.*;  
class MysqlCon
{  
     public static void main(String args[])
{  
     try
     {  
     Class.forName("com.mysql.jdbc.Driver");  
     Connection con=DriverManager.getConnection(  
     "jdbc:mysql://localhost:3306/Employees","root","root");       
      Statement stmt=con.createStatement();  
      ResultSet rs=stmt.executeQuery("select * from emp");  
      while(rs.next())  
      System.out.println(rs.getInt(1)+"  "+rs.getString(2)+"  "+rs.getString(3));  
      con.close();  
      }
     catch(Exception e)
      {
      System.out.println(e);
       }  
}  
} 

The getMetaData() method of ResultSet interface returns the object of ResultSetMetaData. Syntax:

        public ResultSetMetaData getMetaData()throws SQLException 

import java.sql.*;  
class Rsmd{  
public static void main(String args[]){  
try{  
Class.forName("oracle.jdbc.driver.OracleDriver");  
Connection con=DriverManager.getConnection(  
"jdbc:oracle:thin:@localhost:1521:xe","system","oracle");  
  
PreparedStatement ps=con.prepareStatement("select * from emp");  
ResultSet rs=ps.executeQuery();  
ResultSetMetaData rsmd=rs.getMetaData();  
  
System.out.println("Total columns: "+rsmd.getColumnCount());  
System.out.println("Column Name of 1st column: "+rsmd.getColumnName(1));  
System.out.println("Column Type Name of 1st column: "+rsmd.getColumnTypeName(1));  
  
con.close();  
}catch(Exception e){ System.out.println(e);}  
}  
}  
import java.sql.*;

public class JDBCExample
 {
   
   static final String JDBC_DRIVER = "com.mysql.jdbc.Driver";  
   static final String URL = "jdbc:mysql://localhost/STUDENTS";
   static final String USER = "username";
   static final String PASS = "password";
   
   public static void main(String[] args)
 {
   	Connection con = null;
  	 Statement stmt = null;
  	 Try
        {      
      Class.forName("com.mysql.jdbc.Driver");
      con = DriverManager.getConnection(URL, USER, PASS);
      stmt = con.createStatement();      
      String sql = "CREATE TABLE REGISTRATION " +
                   "(id INTEGER not NULL, " +
                   " first VARCHAR(255), " + 
                   " last VARCHAR(255), " + 
                   " age INTEGER, " + 
                   " PRIMARY KEY ( id ))"; 
      stmt.executeUpdate(sql);
      
      
   }
catch(Exception e)
   {
      e.printStackTrace();
   }
finally
{
   try
    {
        con.close();
      stmt.close();      

     }
     catch(Exception e)
   {
      e.printStackTrace();
   }
    
}
      
}
}
import java.sql.*;

public class JDBCExample {
      
   String URL = "jdbc:mysql://localhost:3306/STUDENTS";
   String USER = "username";
   String PASS = "password";   
   public static void main(String[] args) 
{
   Connection conn = null;
   Statement stmt = null;
   try
{
      Class.forName("com.mysql.jdbc.Driver");
      conn = DriverManager.getConnection(URL, USER, PASS);
      stmt = conn.createStatement();      
      String sql = "INSERT INTO Registration " +
                   "VALUES (100, 'Zara', 'Ali', 18)";
      stmt.executeUpdate(sql);
      sql = "INSERT INTO Registration " +
                   "VALUES (101, 'Mahnaz', 'Fatma', 25)";
      stmt.executeUpdate(sql);
      sql = "INSERT INTO Registration " +
                   "VALUES (102, 'Zaid', 'Khan', 30)";
      stmt.executeUpdate(sql);
      sql = "INSERT INTO Registration " +
                   "VALUES(103, 'Sumit', 'Mittal', 28)";
      stmt.executeUpdate(sql);
   }
catch(Exception e)
{
      e.printStackTrace();
 }
finally
{
   try
    {
        con.close();
        stmt.close();      

     }
     catch(Exception e)
   {
      e.printStackTrace();
   }
    
}
}
}
public class JDBCExample 
{
   
   String URL = "jdbc:mysql://localhost:3306/STUDENTS";
   String USER = "username";
   String PASS = "password";
   
   public static void main(String[] args) 
   {
   Connection conn = null;
   Statement stmt = null;
   try{
           Class.forName("com.mysql.jdbc.Driver");      
      conn = DriverManager.getConnection(URL, USER, PASS);     
      stmt = conn.createStatement();
      String sql = "DELETE FROM Registration " +
                   "WHERE id = 101";
      stmt.executeUpdate(sql);
      sql = "SELECT id, first, last, age FROM Registration";
      ResultSet rs = stmt.executeQuery(sql);

      while(rs.next())
      {
         int id  = rs.getInt("id");
         int age = rs.getInt("age");
         String first = rs.getString("first");
         String last = rs.getString("last");
         System.out.print(" ID:  " + id);
         System.out.print(" , Age: " + age);
         System.out.print(" , First: " + first);
         System.out.println(" , Last: " + last);
      }
   }
   catch(Exception e)
     {
            e.printStackTrace();
   }
  finally
{
   try
    {
        con.close();
      stmt.close();     
       rs.close(); 

     }
     catch(Exception e)
   {
      e.printStackTrace();
   }
    
}
}
}
import java.sql.*;

public class JDBCExample 
{  
   static final String DB_URL = "jdbc:mysql://localhost:3306/STUDENTS";
   static final String USER = "username";
   static final String PASS = "password";   
   public static void main(String[] args)
 {
   Connection conn = null;
   Statement stmt = null;
   try
{
      
      Class.forName("com.mysql.jdbc.Driver");
      conn = DriverManager.getConnection(DB_URL, USER, PASS);      
      stmt = conn.createStatement();
      String sql = "UPDATE Registration " +
                   "SET age = 30 WHERE id in (100, 101)";
      stmt.executeUpdate(sql);

      
      sql = "SELECT id, first, last, age FROM Registration";
      ResultSet rs = stmt.executeQuery(sql);

      while(rs.next())
     {
         int id  = rs.getInt("id");
         int age = rs.getInt("age");
         String first = rs.getString("first");
         String last = rs.getString("last");
         System.out.print("ID: " + id);
         System.out.print(", Age: " + age);
         System.out.print(", First: " + first);
         System.out.println(", Last: " + last);
      }
   }
   catch(Exception e)
     {      
      e.printStackTrace();
     }
    finally
{
   try
    {
        con.close();
      stmt.close();  
      rs.close();    

     }
     catch(Exception e)
   {
      e.printStackTrace();
   }
    
}
}
}
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
 
public class MyResultExample {
 
    public static void main(String a[]){
         
        try {
            Class.forName("oracle.jdbc.driver.OracleDriver");
            Connection con = DriverManager
                .getConnection("jdbc:oracle:thin:@::"
                    ,"user","password");
            Statement stmt = con.createStatement();
            System.out.println("Created DB Connection....");
            ResultSet rs = stmt.executeQuery("select name, salary from emp");
            while(rs.next()){
                System.out.println(rs.getString("name"));
                System.out.println(rs.getInt("salary"));
            }
            rs.close();
            con.close();
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (SQLException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.SQLException;
 
public class MyPreparedStatementExample {
 
    public static void main(String a[]){
         
        Connection con = null;
        PreparedStatement prSt = null;
        try {
            Class.forName("oracle.jdbc.driver.OracleDriver");
            con = DriverManager.
                getConnection("jdbc:oracle:thin:@::"
                    ,"user","password");
            String query = "insert into emp(name,salary) values(?,?)";
            prSt = con.prepareStatement(query);
            prSt.setString(1, "John");
            prSt.setInt(2, 10000);
            //count will give you how many records got updated
            int count = prSt.executeUpdate();
            //Run the same query with different values
            prSt.setString(1, "Cric");
            prSt.setInt(2, 5000);
            count = prSt.executeUpdate();
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (SQLException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } finally{
            try{
                if(prSt != null) prSt.close();
                if(con != null) con.close();
            } catch(Exception ex){}
        }
    }
}
class LinkList { 
  
    static Node head; 
  
    static class Node { 
  
        int data; 
        Node next; 
  
        Node(int d) { 
            data = d; 
            next = null; 
        } 
    } 
  
    /* Function to reverse the linked list */
    Node reverse(Node node) { 
        Node prev = null; 
        Node current = node; 
        Node next = null; 
        while (current != null) { 
            next = current.next; 
            current.next = prev; 
            prev = current; 
            current = next; 
        } 
        node = prev; 
        return node; 
    } 
  
    // prints content of double linked list 
    void printList(Node node) { 
        while (node != null) { 
            System.out.print(node.data + " "); 
            node = node.next; 
        } 
    } 
  
    public static void main(String[] args) { 
        LinkedList list = new LinkedList(); 
        list.head = new Node(65); 
        list.head.next = new Node(25); 
        list.head.next.next = new Node(14); 
        list.head.next.next.next = new Node(10); 
          
        System.out.println("Given Linked list"); 
        list.printList(head); 
        head = list.reverse(head); 
        System.out.println(""); 
        System.out.println("Reversed linked list "); 
        list.printList(head); 
    } 
} 
  

Output:
Given linked list
65 25 14 10
Reversed Linked list 
10 14 25 65
public class InsertNodeMiddle {  
  
    class Node{  
        int data;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    public int size;    
    public Node head = null;  
    public Node tail = null;  
  
    //addNode() this will add a new node to the list  
    public void addNode(int data) {  
         
        Node newNode = new Node(data);  
  
        //Checking if the list is empty  
        if(head == null) {  
           
            head = newNode;  
            tail = newNode;  
        }  
        else {  

            tail.next = newNode;  
            //newNode this will become new end of the list  
            tail = newNode;  
        }  
        //This will count the number of nodes present in the list  
        size++;  
    }  
  
    //This function will add the new node at the middle of the list.  
    public void addInMid(int data){  
        
        Node newNode = new Node(data);  
  
        //Checks if the list is empty  
        if(head == null) {  
            //If list is empty, both start and end would point to new node  
            head = newNode;  
            tail = newNode;  
        }  
        else {  
            Node temp, current;  
            //Store the mid position of the list  
            int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
            //Node temp will point to head  
            temp = head;  
            current = null;  
  
            //Traverse through the list till the middle of the list is reached  
            for(int i = 0; i < count; i++) {  
                //Node current will point to temp  
                current = temp;  
                //Node temp will point to node next to it.  
                temp = temp.next;  
            }  
  
            //current will point to new node  
            current.next = newNode;  
            //new node will point to temp  
            newNode.next = temp;  
        }  
        size++;  
    }  
  
    //display() will display all the nodes present in the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        InsertNodeMiddle inm = new InsertNodeMiddle();  
  
        //Adds data to the list  
        inm.addNode(10);  
        inm.addNode(20);  
  
        System.out.println("Initial list: ");  
        inm.display();  
  
        //Inserting node '30' in the middle  
        inm.addInMid(30);  
        System.out.println( "Updated List: ");  
        inm.display();  
  
        //Inserting node '4' in the middle  
        inm.addInMid(40);  
        System.out.println("Updated List: ");  
        inm.display();  
    }  
}  
Output:

Initial list: 
10 20 
Updated List: 
10 30 20 
Updated List: 
10 30 40 20 
public class InsertNodeStart {  
  
    class Node{  
        int data;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    //Represent the origin and destination of the singly linked list  
    public Node head = null;  
    public Node tail = null;  
  
    //addAtStart() will add a new node to the beginning of the list  
    public void addAtStart(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //Checks if the list is empty  
        if(head == null) {  
            //If list is empty, both origin and destination will point to new node  
            head = newNode;  
            tail = newNode;  
        }  
        else {  
            //Node temp will point to origin
            Node temp = head;  
            //newNode will become new origin of the list  
            head = newNode;  
            //Node temp(previous origin) will be added after new origin  
            head.next = temp;  
        }  
    }  
  
    //display() will display all the nodes present in the list  
    public void display() {  
        //Node current will point to origin  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Adding nodes at the beginning of the list: ");  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        InsertNodeStart ins = new InsertNodeStart();  
  
        //Adding 10 to the list  
        ins.addAtStart(10);  
        ins.display();  
  
        //Adding 20 to the list  
        ins.addAtStart(20);  
        ins.display();  
  
        //Adding 30 to the list  
        ins.addAtStart(30);  
        ins.display();  
  
        //Adding 40 to the list  
        ins.addAtStart(40);  
        ins.display();  
    }  
}  
Output:

Adding nodes at the beginning of the list: 
10 
Adding nodes at the beginning of the list: 
20 10
Adding nodes at the beginning of the list:
30 20 10
Adding nodes at the beginning of the list:
40 30 20 10 
public class InsertNodeEnd {  
  
  
    class Node{  
        int data;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    //Represent the origin and destination of the singly linked list  
    public Node head = null;  
    public Node tail = null;  
  
    //addAtEnd() will add a new node to the destination of the list  
    public void addAtEnd(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //Checks if the list is empty  
        if(head == null) {  
            //If list is empty, both origin and destionation will point to new node  
            head = newNode;  
            tail = newNode;  
        }  
        else {  
            //newNode will be added after end such that end's next will point to newNode  
            tail.next = newNode;  
            //newNode will become new destination of the list  
            tail = newNode;  
        }  
    }  
  
    //display() will display all the nodes present in the list  
    public void display() {  
        //Node current will point to origin  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Adding new node at the end of the list: ");  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        InsertNodeEnd ine = new InsertNodeEnd();  
  
        //Adding 10 to the list  
        ine.addAtEnd(10);  
        ine.display();  
  
        //Adding 20 to the list  
        ine.addAtEnd(20);  
        ine.display();  
  
        //Adding 30 to the list  
        ine.addAtEnd(30);  
        ine.display();  
  
        //Adding 40 to the list  
        ine.addAtEnd(40);  
        ine.display();  
    }  
}  
Output:

Adding new node at the end of the list:
10 
Adding new node at the end of the list:
10 20 
Adding new node at the end of the list:
10 20 30 
Adding new node at the end of the list:
10 20 30 40 
public class deleteNodeMiddle{  
  
class Node{  
int data;  
Node next;  

public Node(int data)  
{  
this.data = data;  
this.next = null;  
}  
}  
  
//Represent the origin and destination of the singly linked list  
public Node head = null;  
public Node tail = null;  
  
public int size;  
// New node will be added 
 public void addNode(int data) {  
//Create a new node  
 Node newNode = new Node(data);  
//Checking if the list is empty  
if(head == null) {  
 //If list is empty, both start and end will point to new node  
head = newNode;  
tail = newNode;  
}  
else {  
//newNode will be added after end such that end's next will point to newNode  
tail.next = newNode;  
//newNode will become new end of the list  
tail = newNode;  
}  
size++;  
}  
//deleteFromMid()  this will delete a node from the middle of the list  
void deleteFromMid() {  
Node temp, current;  
//Checking if the list is empty  
if(head == null) {  
System.out.println("List is empty");  
return;  
}  
else {  
//Store the mid position of the list  
 int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
//Checks whether the start is equal to the end or not, if yes then the list has only one node.  
if( head != tail ) {  
 //Initially, temp will point to start
temp = head;  
current = null;  
//Current will point to node previous to temp  
 //If temp is pointing to node 2 then current will point to node 1.  
for(int i = 0; i < count-1; i++){  
current = temp;  
temp = temp.next;  
}  
if(current != null) {  
 //temp is the middle that needs to be removed.  
 //So, current node will point to node next to temp by skipping temp.  
 current.next = temp.next;  
//Delete temp  
 temp = null;  
 }  
 //If current points to NULL then, origin and destination will point to node next to temp.  
 else {  
head = tail = temp.next;  
//Delete temp  
temp = null;  
}  
}  
//If the list contains only one element  
 //then it will remove it and both start and end will point to NULL  
else {  
head = tail = null;  
}  
}  
size--;  
}  
//display() will display all the nodes present in the list  
public void display() {  
//Node current will point to head  
Node current = head;  
if(head == null) {  
System.out.println("List is empty");  
 return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
public static void main(String[] args) {  
  
        deleteNodeMiddle dnm = new deleteNodeMiddle();  
  
        //Adds data to the list  
        dnm.addNode(10);  
        dnm.addNode(20);  
        dnm.addNode(30);  
        dnm.addNode(40);  
  
        //Printing original list  
        System.out.println("Initial List: ");  
        dnm.display();  
  
        while(dnm.head != null) {  
            dnm.deleteFromMid();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dnm.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 
Updated List: 
10 30 40 
Updated List: 
10 40 
Updated List: 
40 
Updated List: 
List is empty
public class DeleteNodeStart {  
  
    class Node{  
        int data;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    //Represent the start and end of the singly linked list  
    public Node head = null;  
    public Node tail = null;  
  
    //addNode() this will add a new node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //Checking if the list is empty  
        if(head == null) {  
            //If list is empty, both start and end will point to new node  
            head = newNode;  
            tail = newNode;  
        }  
        else {  
            //newNode will be added after end such that end's next will point to newNode  
            tail.next = newNode;  
            //newNode will become new end of the list  
            tail = newNode;  
        }  
    }  
  
    //deleteFromStart() this will delete a node from the start of the list  
    public void deleteFromStart() {  
  
        //Checking if the list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        else {  
            //Checking whether the list contains only one node  
            //If not, the start will point to next node in the list and end will point to the new head.  
            if(head != tail) {  
                head = head.next;  
            }  
            //If the list contains only one node  
            //then, it will remove it and both start and end will point to null  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //display() this will display all the nodes present in the list  
    public void display() {  
        //Node current will point to start  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Printing each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        DeleteNodeStart dns = new DeleteNodeStart();  
  
        //Adding data to the list  
        dns.addNode(10);  
        dns.addNode(20);  
        dns.addNode(30);  
        dns.addNode(40);  
  
        //Printing initial list  
        System.out.println("Initial List: ");  
        dns.display();  
  
        while(dns.head != null) {  
            dns.deleteFromStart();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dns.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 
Updated List: 
20 30 40 
Updated List: 
30 40 
Updated List: 
40 
Updated List: 
List is empty
public class DeleteNodeEnd {  
  
    class Node{  
        int data;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
            this.next = null;  
        }  
    }  
  
    //Represent the start and end of the singly linked list  
    public Node head = null;  
    public Node tail = null;  
  
    //addNode() this will add a new node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //Checking if the list is empty  
        if(head == null) {  
            //If list is empty, both start and end will point to new node  
            head = newNode;  
            tail = newNode;  
        }  
        else {  
            //newNode will be added after end such that end's next will point to newNode  
            tail.next = newNode;  
            //newNode will become new end of the list  
            tail = newNode;  
        }  
    }  
  
    //deleteFromEnd() thos will delete a node from end of the list  
    public void deleteFromEnd() {  
  
        //Checking if the list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        else {  
            //Checking whether the list contains only one element  
            if(head != tail ) {  
                Node current = head;  
                //Looping through the list till the second last element such that current.next is pointing to end  
                while(current.next != tail) {  
                    current = current.next;  
                }  
                //Second last element will become new end of the list  
                tail = current;  
                tail.next = null;  
            }  
            //If the list contains only one element  
            //Then it will remove it and both start and end will point to null  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //display() this will display all the nodes present in the list  
    public void display() {  
        //Node current will point to start  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing pointer  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        DeleteNodeEnd dne = new DeleteNodeEnd();  
  
        //Adding data to the list  
        dne.addNode(10);  
        dne.addNode(20);  
        dne.addNode(30);  
        dne.addNode(40);  
  
        //Printing initial list  
        System.out.println("Initial List: ");  
        dne.display();  
  
        while(dne.head != null) {  
            dne.deleteFromEnd();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dne.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 
Updated List: 
10 20 30 
Updated List: 
10 20 
Updated List: 
10 
Updated List: 
List is empty
public class CreateCircularLinkedList {  
    public class Node{  
        int data;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    public Node head = null;  
    public Node tail = null;  
  
    //This function will add the new node at the end of the list.  
    public void add(int data){  
        //Create new node  
        Node newNode = new Node(data);  
        //Checks if the list is empty.  
        if(head == null) {  
             //If list is empty, both head and tail would point to new node.  
            head = newNode;  
            tail = newNode;  
            newNode.next = head;  
        }  
        else {  
            //tail will point to new node.  
            tail.next = newNode;  
            //New node will become new tail.  
            tail = newNode;  
            //Since, it is circular linked list tail will point to head.  
            tail.next = head;  
        }  
    }  
  
    //Displays all the nodes in the list  
    public void display() {  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
            System.out.println("Circular linked list: ");  
             do{  
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.data);  
                current = current.next;  
            }while(current != head);  
            System.out.println();  
        }  
    }  
  
    public static void main(String[] args) {  
        CreateCircularLinkedList ccll = new CreateCircularLinkedList();  
        //Adds data to the list  
        ccll.add(10);  
        ccll.add(20);  
        ccll.add(30);  
        ccll.add(40);  
        //Displays all the nodes present in the list  
        ccll.display();  
    }  
}  
Output:

Circular linked list: 
10 20 30 40
public class CountCircularNodes {    
        public class Node{    
            int data;    
            Node next;    
            public Node(int data) {    
                this.data = data;    
            }    
        }    
            
        public int count;    
        //Declaring head and tail pointer as null.    
        public Node head = null;    
        public Node tail = null;    
            
        //This function will add the new node at the end of the list.    
        public void add(int data){    
            //Create new node    
            Node newNode = new Node(data);    
            //Checks if the list is empty.    
            if(head == null) {    
                 //If list is empty, both head and tail would point to new node.    
                head = newNode;    
                tail = newNode;    
                newNode.next = head;    
            }    
            else {    
                //tail will point to new node.    
                tail.next = newNode;    
                //New node will become new tail.    
                tail = newNode;    
                //Since, it is circular linked list tail will point to head.    
                tail.next = head;    
            }    
        }    
            
        //This function will count the nodes of circular linked list    
        public void countNodes() {    
            Node current = head;    
            do{    
                //Increment the count variable by 1 for each node    
                count++;    
                current = current.next;    
            }while(current != head);    
            System.out.println("Count of nodes present in circular linked list: "+count);    
        }    
            
        public static void main(String[] args) {    
            CountCircularNodes ccn = new CountCircularNodes();    
            ccn.add(10);    
            ccn.add(20);    
            ccn.add(40);    
            ccn.add(10);    
            ccn.add(20);    
            ccn.add(30);    
            //Counts the number of nodes present in the list    
            ccn.countNodes();    
        }    
}    
Output:

Count of nodes present in circular linked list: 6
public class MinMaxNode {  
    public class Node{  
        int data;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    public Node head = null;  
    public Node tail = null;  
  
    //This function will add the new node at the end of the list.  
    public void add(int data){  
        //Create new node  
        Node newNode = new Node(data);  
        //Checks if the list is empty.  
        if(head == null) {  
             //If list is empty, both head and tail would point to new node.  
            head = newNode;  
            tail = newNode;  
            newNode.next = head;  
        }  
        else {  
            //tail will point to new node.  
            tail.next = newNode;  
            //New node will become new tail.  
            tail = newNode;  
            //Since, it is circular linked list tail will points to head.  
            tail.next = head;  
        }  
    }  
  
    //Finds out the minimum value node in the list  
    public void minNode() {  
        Node current = head;  
        //Initializing min to initial node data  
        int min = head.data;  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
             do{  
                 //If current node's data is smaller than min  
                 //Then replace value of min with current node's data  
                 if(min > current.data) {  
                     min = current.data;  
                 }  
                 current= current.next;  
            }while(current != head);  
  
            System.out.println("Minimum value node in the list: "+ min);  
        }  
    }  
  
    //Finds out the maximum value node in the list  
    public void maxNode() {  
        Node current = head;  
        //Initializing max to initial node data  
        int max = head.data;  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
             do{  
                 //If current node's data is greater than max  
                 //Then replace value of max with current node's data  
                 if(max < current.data) {  
                     max = current.data;  
                 }  
                 current= current.next;  
                }while(current != head);  
  
            System.out.println("Maximum value node in the list: "+ max);  
        }  
    }  
  
    public static void main(String[] args) {  
        MinMaxNode mmn = new MinMaxNode();  
        //Adds data to the list  
        mmn.add(12);  
        mmn.add(24);  
        mmn.add(8);  
        mmn.add(16);  
        //Prints the minimum value node in the list  
        mmn.minNode();  
        //Prints the maximum value node in the list  
        mmn.maxNode();  
    }  
}  
Output:

Minimum value node in the list: 8
Maximum value node in the list: 24
public class InsertNodeStart {  
        public class Node{  
            int data;  
            Node next;  
            public Node(int data) {  
                this.data = data;  
            }  
        }  
  
        //Declaring start and end pointer as null.  
        public Node head = null;  
        public Node tail = null;  
  
        //This function will add the new node at the end of the list.  
        public void addAtStart(int data){  
            //Create new node  
            Node newNode = new Node(data);  
            //Checking if the list is empty.  
            if(head == null) {  
                 //If list is empty, both start and end would point to new node.  
                head = newNode;  
                tail = newNode;  
                newNode.next = head;  
            }  
            else {  
                //Store data into temporary node  
                Node temp = head;  
                //New node will point to temp as next node  
                newNode.next = temp;  
                //New node will be the start node  
                head = newNode;  
                //Since, it is circular linked list tail will point to head.  
                tail.next = head;  
            }  
        }  
  
        //Displays all the nodes in the list  
        public void display() {  
            Node current = head;  
            if(head == null) {  
                System.out.println("List is empty");  
            }  
            else {  
                System.out.println("Adding nodes at the beginning of the list: ");  
                 do{  
                    //Printing each node by incrementing pointer.  
                    System.out.print(" "+ current.data);  
                    current = current.next;  
                }while(current != head);  
                System.out.println();  
            }  
        }  
  
        public static void main(String[] args) {  
            InsertNodeStart ins = new InsertNodeStart();  
  
            //Adding 10 to the list  
            ins.addAtStart(10);  
            ins.display();  
            //Adding 20 to the list  
            ins.addAtStart(2);  
            ins.display();  
            //Adding 30 to the list  
            ins.addAtStart(3);  
            ins.display();  
            //Adding 40 to the list  
            ins.addAtStart(4);  
            ins.display();  
        }  
}  
Output:

Adding nodes at the beginning of the list: 
10
Adding nodes at the beginning of the list:
20 10
Adding nodes at the beginning of the list: 
30 20 10
Adding nodes at the beginning of the list: 
40 30 20 10
public class InsertNodeEnd {    
        public class Node{    
            int data;    
            Node next;    
            public Node(int data) {    
                this.data = data;    
            }    
        }    
            
        //Declaring start and end pointer as null.    
        public Node head = null;    
        public Node tail = null;    
            
        //This function will add the new node at the end of the list.    
        public void addAtEnd(int data){    
            //Create new node    
            Node newNode = new Node(data);    
            //Checking if the list is empty.    
            if(head == null) {    
                 //If list is empty, both start and end would point to new node.    
                head = newNode;    
                tail = newNode;    
                newNode.next = head;    
            }    
            else {    
                //end will point to new node.    
                tail.next = newNode;    
                //New node will become new end.    
                tail = newNode;    
                //Since, it is circular linked list end will points to start.    
                tail.next = head;    
            }    
        }    
            
        //Displays all the nodes in the list    
        public void display() {    
            Node current = head;    
            if(head == null) {    
                System.out.println("List is empty");    
            }    
            else {    
                System.out.println("Adding nodes at the end of the list: ");    
                 do{    
                    //Prints each node by incrementing pointer.    
                    System.out.print(" "+ current.data);    
                    current = current.next;    
                }while(current != head);    
                System.out.println();    
            }    
        }    
            
        public static void main(String[] args) {    
            InsertNodeEnd ine = new InsertNodeEnd();    
                
            //Adding 10 to the list    
            ine.addAtEnd(10);    
            ine.display();    
            //Adding 20 to the list    
            ine.addAtEnd(20);    
            ine.display();    
            //Adding 30 to the list    
            ine.addAtEnd(30);    
            ine.display();    
            //Adding 40 to the list    
            ine.addAtEnd(40);    
            ine.display();    
        }    
}    
Output:

Adding nodes at the end of the list: 
10
Adding nodes at the end of the list: 
10 20
Adding nodes at the end of the list: 
10 20 30
Adding nodes at the end of the list: 
10 20 30 40
public class InsertNodeMiddle {  
  
        public class Node{  
            int data;  
            Node next;  
            public Node(int data) {  
                this.data = data;  
            }  
        }  
  
        public int size;  
        //Declaring start and end pointer as null.  
        public Node head = null;  
        public Node tail = null;  
  
        //This function will add the new node to the list.  
        public void add(int data){  
            //Create new node  
            Node newNode = new Node(data);  
            //Checks if the list is empty.  
            if(head == null) {  
                 //If list is empty, both start and end would point to new node.  
                head = newNode;  
                tail = newNode;  
                newNode.next = head;  
            }  
            else {  
                //tail will point to new node.  
                tail.next = newNode;  
                //New node will become new tail.  
                tail = newNode;  
                //Since, it is circular linked list tail will points to head.  
                tail.next = head;  
            }  
            //Size will count the number of element in the list  
            size++;  
        }  
  
        //This function will add the new node at the middle of the list.  
        public void addInMid(int data){  
            Node newNode = new Node(data);  
            //Checks if the list is empty.  
            if(head == null){  
                //If list is empty, both head and tail would point to new node.  
                head = newNode;  
                tail = newNode;  
                newNode.next = head;  
            }  
            else{  
                Node temp,current;  
                //Store the mid-point of the list  
                int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
                //temp will point to head  
                temp = head;  
                current= null;  
                for(int i = 0; i < count; i++){  
                    //Current will point to node previous to temp.  
                    current = temp;  
                    //Traverse through the list till the middle of the list is reached  
                    temp = temp.next;  
                }  
  
                //current will point to new node  
                current.next = newNode;  
                //new node will point to temp  
                newNode.next = temp;  
            }  
            size++;  
        }  
  
        //Displays all the nodes in the list  
        public void display() {  
            Node current = head;  
            if(head == null) {  
                System.out.println("List is empty");  
            }  
            else {  
                 do{  
                    //Prints each node by incrementing pointer.  
                    System.out.print(" "+ current.data);  
                    current = current.next;  
                }while(current != head);  
                System.out.println();  
            }  
        }  
  
        public static void main(String[] args) {  
            InsertNodeMiddle inm = new InsertNodeMiddle();  
            //Adds data to the list  
            inm.add(10);  
            inm.add(20);  
            inm.add(30);  
            inm.add(40);  
  
            System.out.println("Initial  list: ");  
            inm.display();  
  
            //Inserting node '50' in the middle  
            inm.addInMid(50);  
            System.out.println( "Updated List: ");  
            inm.display();  
  
            //Inserting node '6' in the middle  
            inm.addInMid(60);  
            System.out.println("Updated List: ");  
            inm.display();  
        }  
}   
Output:

Initial list: 
10 20 30 40
Updated List: 
10 20 50 30 40
Updated List: 
10 20 50 60 30 40
public class DeleteNodeStart {  
    public class Node{  
        int data;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    //Declaring start and end pointer as null.  
    public Node head = null;  
    public Node tail = null;  
  
    public void add(int data){  
        
        Node newNode = new Node(data);  
         
        if(head == null) {  
        
            head = newNode;  
            tail = newNode;  
            newNode.next = head;  
        }  
        else {  
          
            tail.next = newNode;   
            tail = newNode;  
            tail.next = head;  
        }  
    }  
  
    //Deletes node from the start of the list  
    public void deleteStart() {  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            if(head != tail ) {  
                head = head.next;  
                tail.next = head;  
            }  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //Displays all the nodes in the list  
    public void display() {  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
             do{  
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.data);  
                current = current.next;  
            }while(current != head);  
            System.out.println();  
        }  
    }  
  
    public static void main(String[] args) {  
        DeleteNodeStart dns = new DeleteStart();  
        //Adds data to the list  
        dns.add(10);  
        dns.add(20);  
        dns.add(30);  
        dns.add(40);  
        //Printing initial  list  
        System.out.println("Initial List: ");  
        dns.display();  
        while(dns.head != null) {  
            dns.deleteStart();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dns.display();  
        }  
    }  
}  
Output:

Initial List: 
 10 20 30 40
Updated List: 
 20 30 40
Updated List: 
 30 40
Updated List: 
 40
Updated List: 
List is empty
public class DeleteNodeEnd {  
    public class Node{  
        int data;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    //Declaring start and end pointer as null.  
    public Node head = null;  
    public Node tail = null;  
  
    //This function will add the new node at the end of the list.  
    public void add(int data){  
        //Create new node  
        Node newNode = new Node(data);  
        //Checks if the list is empty.  
        if(head == null) {  
             //If list is empty, both head and tail would point to new node.  
            head = newNode;  
            tail = newNode;  
            newNode.next = head;  
        }  
        else {  
            //tail will point to new node.  
            tail.next = newNode;  
            //New node will become new tail.  
            tail = newNode;  
            //Since, it is circular linked list tail will point to head.  
            tail.next = head;  
        }  
    }  
  
    //Deletes node from end of the list  
    public void deleteEnd() {  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //Checks whether contain only one element  
            if(head != tail ) {  
                Node current = head;  
                //Loop will iterate till the second last element as current.next is pointing to tail  
                while(current.next != tail) {  
                    current = current.next;  
                }  
                //Second last element will be new tail  
                tail = current;  
                //Tail will point to head as it is a circular linked list  
                tail.next = head;  
            }  
            //If the list contains only one element  
            //Then it will remove it and both head and tail will point to null  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //Displays all the nodes in the list  
    public void display() {  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
        }  
        else {  
             do{  
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.data);  
                current = current.next;  
            }while(current != head);  
            System.out.println();  
        }  
    }  
  
    public static void main(String[] args) {  
        DeleteNodeEnd dne = new DeleteNodeEnd();  
        //Adds data to the list  
        dne.add(10);  
        dne.add(20);  
        dne.add(30);  
        dne.add(40);  
        //Printing Initial list  
        System.out.println("Initial List: ");  
        dne.display();  
        while(dne.head != null) {  
            dne.deleteEnd();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dne.display();  
        }  
    }  
}  
Output:

Initial List: 
 10 20 30 40
Updated List: 
 10 20 30
Updated List: 
 10 20
Updated List: 
 10
Updated List: 
List is empty
public class DeleteNodeMiddle {    
    public class Node{    
        int data;    
        Node next;    
        public Node(int data) {    
            this.data = data;    
        }    
    }    
public int size;    
    //Declaring start and end pointer as null.    
    public Node head = null;    
    public Node tail = null;    
        
    //This function will add the new node at the end of the list.    
    public void add(int data){    
        //Create new node    
        Node newNode = new Node(data);    
        //Checks if the list is empty.    
        if(head == null) {    
             //If list is empty, both head and tail would point to new node.    
            head = newNode;    
            tail = newNode;    
            newNode.next = head;    
        }    
        else {    
            //tail will point to new node.    
            tail.next = newNode;    
            //New node will become new tail.    
            tail = newNode;    
            //Since, it is circular linked list tail will point to head.    
            tail.next = head;    
        }    
        //Counts the number of nodes in list    
        size++;    
    }    
        
    //Deletes node from the middle of the list    
    public void deleteMid() {    
        Node current, temp;    
        //Checks whether list is empty    
        if(head == null) {    
            return;    
        }    
        else {    
            //Store the mid position of the list    
            int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);    
            //Checks whether head is equal to tail or not, if yes then list has only one node.    
            if( head != tail ) {    
                //Initially temp will point to head;    
                temp = head;    
                current = null;    
                //Current will point to node previous to temp    
                //If temp is pointing to node 2 then current will points to node 1.    
                for(int i = 0; i < count-1; i++){    
                    current = temp;    
                    temp = temp.next;    
                }    
                    
                if(current != null) {    
                    //temp is the middle that needs to be removed.    
                    //So, current node will point to node next to temp by skipping temp.    
                    current.next = temp.next;    
                    //Delete temp;    
                    temp = null;    
                }    
                //Current points to null then head and tail will point to node next to temp.    
                else {    
                    head = tail = temp.next;    
                    tail.next = head;    
                    //Delete temp;    
                    temp = null;    
                }    
                    
            }    
            //If the list contains only one element     
            //then it will remove it and both head and tail will point to null    
            else {    
                head = tail = null;    
            }    
        }    
        size--;    
    }    
        
    //Displays all the nodes in the list    
    public void display() {    
        Node current = head;    
        if(head == null) {    
            System.out.println("List is empty");    
        }    
        else {    
             do{    
                //Prints each node by incrementing pointer.    
                System.out.print(" "+ current.data);    
                current = current.next;    
            }while(current != head);    
            System.out.println();    
        }    
    }    
        
    public static void main(String[] args) {    
        DeleteNodeMiddle dnm = new DeleteNodeMiddle();    
        //Adds data to the list    
        dnm.add(10);    
        dnm.add(20);    
        dnm.add(30);    
        dnm.add(40);    
        //Printing Initial list    
        System.out.println("Initial List: ");    
        dnm.display();    
        while(dnm.head != null) {    
            dnm.deleteMid();    
            //Printing updated list    
            System.out.println("Updated List: ");    
            dnm.display();    
        }    
    }    
}   
Output:

Initial List: 
 10 20 30 40
Updated List: 
 10 30 40
Updated List: 
 10 40
Updated List: 
 40
Updated List: 
List is empty
public class LinkedListExamples
{
    public static void main(String[] args)
    {
        LinkedList que = new LinkedList();
 
        //adding the elements into the queue
 
        que.offer(100);
 
        que.offer(200);
 
        que.offer(300);
 
        que.offer(400);
 
        //Printing the elements of queue
 
        System.out.println(que);      //Output : [100, 200, 300, 400]
 
        //Removing the elements from the queue
 
        System.out.println(que.poll());    //Output : 100
 
        System.out.println(que.poll());    //Output : 200
    }
}
public class LinkedListReplace
{
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
 
        //Adding elements at the end of the list
 
        list.add("First");
 
        list.add("Second");
 
        list.add("Third");
 
        list.add("Fouth");
 
        //Printing the elements of list
 
        System.out.println(list);      //Output : [First, Second, Third, Fourth]
 
        //Replacing an element at index 2 with "ZERO"
 
        list.set(2, "ABC");
 
        System.out.println(list);     //Output : [First, Second, ABC, Fourth]
    }
}
public class LinkedListClone
{
    public static void main(String[] args)
    {
        LinkedList linkedList1 = new LinkedList();
 
        //adding the elements to linkedList1
 
        linkedList1.add(100);
 
        linkedList1.add(200);
 
        linkedList1.add(300);
 
        linkedList1.add(400);
 
        linkedList1.add(500);
 
        //Printing the elements of linkedList1
 
        System.out.println(linkedList1);       //Output : [100, 200, 300, 400, 500]
 
        //Creating another LinkedList
 
        LinkedList linkedList2 = new LinkedList();
 
        //Cloning the linkedList1 into linkedList2
 
        linkedList2 = (LinkedList) linkedList1.clone();
 
        //Printing the elements of linkedList2
 
        System.out.println(linkedList2);     //Output : [100, 200, 300, 400, 500]
    }
}
public class LinkedListClone
{
    public static void main(String[] args)
    {
        LinkedList linkedList1 = new LinkedList();
 
        //adding the elements to linkedList1
 
        linkedList1.add(100);
 
        linkedList1.add(200);
 
        linkedList1.add(300);
 
        linkedList1.add(400);
 
        linkedList1.add(500);
 
        //Printing the elements of linkedList1
 
        System.out.println(linkedList1);       //Output : [100, 200, 300, 400, 500]
 
        //Creating another LinkedList
 
        LinkedList linkedList2 = new LinkedList();
 
        //Cloning the linkedList1 into linkedList2
 
        linkedList2 = (LinkedList) linkedList1.clone();
 
        //Printing the elements of linkedList2
 
        System.out.println(linkedList2);     //Output : [100, 200, 300, 400, 500]
    }
}
public class BinaryTreeDoubly {    
    public static class Node{    
        int data;    
        Node left;    
        Node right;    
            
        public Node(int data) {    
            this.data = data;    
            this.left = null;    
            this.right = null;    
        }    
    }    
        
    //Represent the root of the binary tree    
    
    public Node root;    
          
    
    Node head, tail = null;    
        
    //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list    
    public void convertbtToDLL(Node node) {    
        //Checks whether node is null    
        if(node == null)    
            return;    
            
        //Convert left subtree to doubly linked list    
        convertbtToDLL(node.left);    
            
        //If list is empty, add node as head of the list    
        if(head == null) {    
            //Both head and tail will point to node    
            head = tail = node;    
        }    
        //Otherwise, add node to the end of the list    
        else {    
            //node will be added after tail such that tail's right will point to node    
            tail.right = node;    
            //node's left will point to tail    
            node.left = tail;    
            //node will become new tail    
            tail = node;    
        }    
            
        //Convert right subtree to doubly linked list    
        convertbtToDLL(node.right);    
    }    
        
    //display() will print out the nodes of the list    
    public void display() {    
        //Node current will point to head    
        Node current = head;    
        if(head == null) {    
            System.out.println("List is empty");    
            return;    
        }    
        System.out.println("Nodes of generated doubly linked list: ");    
        while(current != null) {    
            //Prints each node by incrementing the pointer.    
    
            System.out.print(current.data + " ");    
            current = current.right;    
        }    
        System.out.println();    
    }    
        
    public static void main(String[] args) {    
            
        BinaryTreeDoubly btd = new BinaryTreeToDLL();    
        //Add nodes to the binary tree    
        btd.root = new Node(10);    
        btd.root.left = new Node(20);    
        btd.root.right = new Node(30);    
        btd.root.left.left = new Node(40);    
        btd.root.left.right = new Node(50);    
        btd.root.right.left = new Node(60);    
        btd.root.right.right = new Node(70);    
            
        //Converts the given binary tree to doubly linked list    
        btd.convertbtToDLL(btd.root);    
            
        //Displays the nodes present in the list    
        btd.display();    
    }    
}    
Output:

Nodes of generated doubly linked list: 
40 20 50 10 60 30 70
public class CountNodes {  
  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    Node head, tail = null;  
  
    //addNode() this will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            head = tail = newNode;  
            head.previous = null;  
            tail.next = null;  
        }  
        else {  
            //newNode this will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            newNode.previous = tail;  
            tail = newNode;  
            tail.next = null;  
        }  
    }  
  
    //countNodes() this will count the nodes present in the list  
    public int countNodes() {  
        int counter = 0;  
        //Node current will point to start 
        Node current = head;  
  
        while(current != null) {  
            //Increment the counter by 1 for each node  
            counter++;  
            current = current.next;  
        }  
        return counter;  
    }  
  
    //display() this will print out the elements of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Elements of doubly linked list: ");  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
    }  
  
    public static void main(String[] args) {  
  
        CountNodes cn = new CountList();  
        //Add nodes to the list  
        cn.addNode(10);  
        cn.addNode(20);  
        cn.addNode(30);  
        cn.addNode(40);  
        cn.addNode(50);  
  
        //Displays the nodes present in the list  
        cn.display();  
  
        //Counts the nodes present in the given list  
        System.out.println("\nCount of nodes present in the list: " + cn.countNodes());  
    }  
}  
Output:

Elements of doubly linked list: 
10 20 30 40 50 
Count of nodes present in the list: 5
public class MinMaxNode {  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    Node head, tail = null;  
  
    //addNode() this will add a node to the list  
    public void addNode(int data) {  
           Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            
            head = tail = newNode;  
            head.previous = null;  
            tail.next = null;  
        }  
        else {  
            tail.next = newNode;  
            //newNode's previous will point to end  
            newNode.previous = tail;  
            //newNode will become new end  
            tail = newNode;    
            tail.next = null;  
        }  
    }  
  
    //MinimumNode() will find out minimum value node in the list  
    public int minimumNode() {  
        //Node current will point to head  
        Node current = head;  
        int min;  
  
        //Checks if list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return 0;  
        }  
        else {  
            //Initially, min will store the value of head's data  
            min = head.data;  
            while(current != null) {  
                //If the value of min is greater than the current's data  
  
                //Then, replace the value of min with current node's data  
  
                if(min > current.data)  
                    min = current.data;  
                current = current.next;  
            }  
        }  
        return min;  
    }  
  
    //MaximumNode() will find out maximum value node in the list  
    public int maximumNode() {  
        //Node current will point to head  
        Node current = head;  
        int max;  
  
        //Checks if list is empty  
        if(head == null) {  
            System.out.println("List is empty");  
            return 0;  
        }  
        else {  
            //Initially, max will store the value of head's data  
            max = head.data;  
            while(current != null) {  
                if(current.data > max)  
                    max = current.data;  
                current = current.next;  
            }  
        }  
        return max;  
    }  
  
    public static void main(String[] args) {  
  
        MinMaxNode mmn = new MinMaxNode();  
        //Add nodes to the list  
        mmn.addNode(15);  
        mmn.addNode(27);  
        mmn.addNode(49);  
        mmn.addNode(11);  
        mmn.addNode(21);  
  
        //Prints the minimum value node in the list  
        System.out.println("Minimum value node in the list: "+ dList.minimumNode());  
        //Prints the maximum value node in the list  
        System.out.println("Maximum value node in the list: "+ dList.maximumNode());  
    }  
}  
Output:

Minimum value node : 11
Maximum value node : 49
public class InsertNodeMiddle {  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    public int size = 0;  
    
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
        //Size will count the number of nodes present in the list  
        size++;  
    }  
  
    //addInMid() will add a node to the middle of the list  
    public void addInMid(int data) {  
       //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //current will point to head  
            Node current = head, temp = null;  
  
            //Store the mid position of the list  
            int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
  
            //Iterate through list till current points to mid position  
            for(int i = 1; i < mid; i++){  
                current = current.next;  
            }  
  
            //Node temp will point to node next to current  
            temp = current.next;  
            temp.previous = current;  
  
            //newNode will be added between current and temp  
            current.next = newNode;  
            newNode.previous = current;  
            newNode.next = temp;  
            temp.previous = newNode;  
        }  
        size++;  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        InsertNodeMiddle inm = new InsertNodeMiddle();  
        //Add nodes to the list  
        inm.addNode(10);  
        inm.addNode(20);  
  
        System.out.println("Initial list: ");  
        inm.display();  
  
        //Adding node '30' in the middle  
        inm.addInMid(30);  
        System.out.println( "Updated List: ");  
        inm.display();  
  
        //Adding node '40' in the middle  
        inm.addInMid(4);  
        System.out.println("Updated List: ");  
        inm.display();  
  
        //Adding node '50' in the middle  
        inm.addInMid(50);  
        System.out.println("Updated List: ");  
        inm.display();  
    }  
}  
Output:

Initial  list: 
10 20 
Updated List: 
10 30 20 
Updated List: 
10 30 40 20 
Updated List: 
10 30 50 40 20 
public class BinarySearchTreeImplementation {
 
    private BstNode root;
 
    public boolean isEmpty() {
 
        return (this.root == null);
    }
 
    public void insert(Integer data) {
 
        System.out.print("[input: "+data+"]");
        if(root == null) {
            this.root = new BstNode(data);
            System.out.println(" -> inserted: "+data);
            return;
        }
 
        insertNode(this.root, data);
        System.out.print(" -> inserted: "+data);
        System.out.println();
    }
 
    private BstNode insertNode(BstNode root, Integer data) {
 
        BstNode tmpNode = null;
        System.out.print(" ->"+root.getData());
        if(root.getData() >= data) {
            System.out.print(" [L]");
            if(root.getLeft() == null) {
                root.setLeft(new BstNode(data));
                return root.getLeft();
            } else {
                tmpNode = root.getLeft();
            }
        } else {
            System.out.print(" [R]");
            if(root.getRight() == null) {
                root.setRight(new BstNode(data));
                return root.getRight();
            } else {
                tmpNode = root.getRight();
            }
        }
 
        return insertNode(tmpNode, data);
    }
 
    public static void main(String a[]) {
 
        BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
        bst.insert(16);
        bst.insert(23);
        bst.insert(6);
        bst.insert(21);
        bst.insert(8);
        bst.insert(10);
        bst.insert(20);
    }
}
Class DeleteNodeMiddle {  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    public int size = 0;  
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
        //Size will count the number of nodes present in the list  
        size++;  
    }  
  
    //deleteFromMid() will delete a node from middle of the list  
    public void deleteFromMid() {  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //current will point to head  
            Node current = head;  
  
            //Store the mid position of the list  
            int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);  
  
            //Iterate through list till current points to mid position  
            for(int i = 1; i < mid; i++){  
                current = current.next;  
            }  
  
            //If middle node is head of the list  
            if(current == head) {  
                head = current.next;  
            }  
            //If middle node is tail of the list  
            else if(current == tail) {  
                tail = tail.previous;  
            }  
            else {  
                current.previous.next = current.next;  
                current.next.previous = current.previous;  
            }  
            //Delete the middle node  
            current = null;  
        }  
        size--;  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        DeleteNodeMiddle dnm = new DeleteNodeMiddle();  
        //Add nodes to the list  
        dnm.addNode(10);  
        dnm.addNode(20);  
        dnm.addNode(30);  
        dnm.addNode(40);  
        dnm.addNode(50);  
  
        //Printing original list  
        System.out.println("Initial List: ");  
        dnm.display();  
        while(dnm.head != null) {  
            dnm.deleteFromMid();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dnm.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 50
Updated List: 
10 20 40 50 
Updated List: 
10 40 50 
Updated List: 
10 50 
Updated List: 
50 
Updated List: 
List is empty
public class DeleteNodeStart  
{  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
}  
  
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }  
  
    //deleteFromStart() will delete a node from the beginning of the list  
    public void deleteFromStart() {  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //Checks whether the list contains only one element  
            if(head != tail) {  
                //head will point to next node in the list  
                head = head.next;  
                //Previous node to current head will be made null  
                head.previous = null;  
            }  
            //If the list contains only one element  
            //then, it will remove node and now both head and tail will point to null  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        DeleteNodeStart dns = new DeleteNodeStart();  
        //Add nodes to the list  
        dns.addNode(10);  
        dns.addNode(20);  
        dns.addNode(30);  
        dns.addNode(40);  
        dns.addNode(50);  
  
        //Printing original list  
        System.out.println("Initial  List: ");  
        dns.display();  
        while(dns.head != null) {  
            dns.deleteFromStart();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dns.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 50 
Updated List: 
20 30 40 50 
Updated List: 
30 40 50 
Updated List: 
40 50 
Updated List: 
50 
Updated List: 
List is empty
public class DeleteNodeEnd {  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }  
  
    //deleteFromEnd() will delete a node from the end of the list  
    public void deleteFromEnd() {  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //Checks whether the list contains only one node  
            if(head != tail) {  
                //Previous node to the tail will become new tail  
                tail = tail.previous;  
                //Node next to current tail will be made null  
                tail.next = null;  
            }  
            //If the list contains only one element  
            //Then it will remove node and now both head and tail will point to null  
            else {  
                head = tail = null;  
            }  
        }  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        DeleteNoteEnd dne = new DeleteEnd();  
        //Add nodes to the list  
        dne.addNode(10);  
        dne.addNode(20);  
        dne.addNode(30);  
        dne.addNode(40);  
        dne.addNode(50);  
  
        //Printing Initial list  
        System.out.println("Initial List: ");  
        dne.display();  
        while(dne.head != null) {  
            dne.deleteFromEnd();  
            //Printing updated list  
            System.out.println("Updated List: ");  
            dne.display();  
        }  
    }  
}  
Output:

Initial List: 
10 20 30 40 50 
Updated List: 
10 20 30 40 
Updated List: 
10 20 30 
Updated List: 
10 20 
Updated List: 
10 
Updated List: 
List is empty
public class RemoveDuplicateElemenstts {  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
        public Node(int data) {  
            this.data = data;  
        }  
    }   
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }  
    //removeDuplicateNode() will remove duplicate nodes from the list  
    public void removeDuplicateNode() {  
        //Node current will point to head  
        Node current, index, temp;  
  
        //Checks whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //Initially, current will point to head node  
            for(current = head; current != null; current = current.next) {  
                //index will point to node next to current  
                for(index = current.next; index != null; index = index.next) {  
                    if(current.data == index.data) {  
                        //Store the duplicate node in temp  
                        temp = index;  
                        //index's previous node will point to node next to index thus, removes the duplicate node  
                        index.previous.next = index.next;  
                        if(index.next != null)  
                            index.next.previous = index.previous;  
                        //Delete duplicate node by making temp to null  
                        temp = null;  
                    }  
                }  
            }  
        }  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        RemoveDuplicateElements rde = new RemoveDuplicateElements();  
        //Add nodes to the list  
        rde.addNode(10);  
        rde.addNode(20);  
        rde.addNode(30);  
        rde.addNode(20);  
        rde.addNode(20);  
        rde.addNode(40);  
        rde.addNode(50);  
        rde.addNode(30);  
  
        System.out.println("Initial list: ");  
        rde.display();  
  
        //Removes duplicate nodes  
        rde.removeDuplicateNode();  
  
        System.out.println("List after removing duplicates: ");  
        rde.display();  
    }  
}  
Output:

Initial list: 
10 20 30 20 20 40 50 30 
List after removing duplicates: 
10 20 30 40 50
public class RotatingList {  
  
    class Node{  
        int data;  
        Node previous;  
        Node next;  
  
        public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    int size = 0;  
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
        //Size will count the number of nodes present in the list  
        size++;  
    }  
  
    //rotateList() will rotate the list by given n nodes  
    public void rotateList(int n) {  
        //Initially, current will point to head  
        Node current = head;  
  
        //n should not be 0 or greater than or equal to number of nodes present in the list  
        if(n == 0 || n >= size)  
            return;  
        else {  
            //Traverse through the list till current point to nth node  
            //after this loop, current will point to nth node  
            for(int i = 1; i < n; i++)  
                current = current.next;  
  
            //Now to move entire list from head to nth node and add it after tail  
            tail.next = head;  
            //Node next to nth node will be new head  
            head = current.next;  
            //Previous node to head should be null  
            head.previous = null;  
            //nth node will become new tail of the list  
            tail = current;  
            //tail's next will point to null  
            tail.next = null;  
        }  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
        System.out.println();  
    }  
  
    public static void main(String[] args) {  
  
        RotatingList rl = new RotatingList();  
        //Add nodes to the list  
        rl.addNode(10);  
        rl.addNode(20);  
        rl.addNode(30);  
        rl.addNode(40);  
        rl.addNode(50);  
  
        System.out.println("Initial List: ");  
        rl.display();  
  
        //Rotates list by 3 nodes  
        rl.rotateList(3);  
  
        System.out.println("Updated List: ");  
        rl.display();  
    }  
}  
Output:

Initial List: 
10 20 30 40 50 
Updated List: 
40 50 10 20 30 
Public class BinarySearchTreeImplementation {
 
    private BstNode root;
 
    public boolean isEmpty() {
 
        return (this.root == null);
    }
 
    public void insert(Integer data) {
 
        System.out.print("[input: "+data+"]");
        if(root == null) {
            this.root = new BstNode(data);
            System.out.println(" -> inserted: "+data);
            return;
        }
 
        insertNode(this.root, data);
        System.out.print(" -> inserted: "+data);
        System.out.println();
    }
 
    private BstNode insertNode(BstNode root, Integer data) {
 
        BstNode tmpNode = null;
        System.out.print(" ->"+root.getData());
        if(root.getData() >= data) {
            System.out.print(" [L]");
            if(root.getLeft() == null) {
                root.setLeft(new BstNode(data));
                return root.getLeft();
            } else {
                tmpNode = root.getLeft();
            }
        } else {
            System.out.print(" [R]");
            if(root.getRight() == null) {
                root.setRight(new BstNode(data));
                return root.getRight();
            } else {
                tmpNode = root.getRight();
            }
        }
 
        return insertNode(tmpNode, data);
    }
 
    public static void main(String a[]) {
 
        BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
        bst.insert(16);
        bst.insert(23);
        bst.insert(6);
        bst.insert(21);
        bst.insert(8);
        bst.insert(10);
        bst.insert(20);
    }
}
import java.util.LinkedList;  
import java.util.Queue;  
  
public class BinaryTreeWidth {  
  
      public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
          //Assigning data to the new node, set left and right children to null  
          this.data = data;  
          this.left = null;  
          this.right = null;  
        }  
      }  
  
      //Representing the root of binary tree  
      public Node root;  
  
      public BinaryTree(){  
        root = null;  
      }  
  
      //findMaximumWidth() this will find out the maximum width of the given binary tree  
      public int findMaximumWidth() {  
          int maxWidth = 0;  
  
          //Variable nodesLevel keep tracks of number of nodes in each level  
          int nodesLevel = 0;  
          //queue will be used to keep track of nodes of tree level-wise  
          Queue queue = new LinkedList();  
  
          //Check if root is null, then width will be 0  
          if(root == null) {  
              System.out.println("Tree is empty");  
              return 0;  
          }  
          else {  
              //Add root node to queue as it represents the first level  
              queue.add(root);  
  
              while(queue.size() != 0) {  
  
                  //Variable nodesLevel will hold the size of queue i.e. number of elements in queue  
                  nodesLevel = queue.size();  
                  //maxWidth will hold maximum width.  
                  //If nodesLevel is greater than maxWidth then, maxWidth will hold the value of nodesLevel  
                  maxWidth = Math.max(maxWidth, nodesLevel);  
  
                  //If variable nodesLevel contains more than one node  
                  //then, for each node, we'll add left and right child of the node to the queue  
                  while(nodesLevel > 0) {  
                     Node current = queue.remove();  
                     if(current.left != null)  
                         queue.add(current.left);  
                     if(current.right != null)  
                         queue.add(current.right);  
                     nodesLevel--;  
                  }  
              }  
          }  
          return maxWidth;  
      }  
  
      public static void main(String[] args) {  
  
          BinaryTreeWidth bint = new BinaryTreeWidth();  
          //Adding nodes to the binary tree  
          bint.root = new Node(10);  
          bint.root.left = new Node(20);  
          bint.root.right = new Node(30);  
          bint.root.left.left = new Node(40);  
          bint.root.left.right = new Node(50);  
          bint.root.right.left = new Node(60);  
          bint.root.right.right = new Node(70);  
          bint.root.left.left.left = new Node(80);  
  
          //Display the maximum width of given tree  
          System.out.println("Width of the binary tree: " + bint.findMaximumWidth());  
      }  
}  
Output:
Width of the binary tree: 4
public class LargestNodeBST {    
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
     }  
  
      //Represent the root of binary tree  
      public Node root;  
  
      public LargestNode(){  
        root = null;  
      }  
  
      //largestElement() this will find out the largest node in the binary tree  
      public int largestElement(Node temp){  
          //Checking whether tree is empty  
           if(root == null) {  
               System.out.println("Tree is empty");  
               return 0;  
            }  
           else{  
               int leftMax, rightMax;  
               //Max will store temp's data  
               int max = temp.data;  
  
               //This will find largest element in left subtree  
               if(temp.left != null){  
                   leftMax = largestElement(temp.left);  
                   //Comparing max with leftMax and store greater value into max  
                   max = Math.max(max, leftMax);  
                }  
  
                //This will find largest element in right subtree  
                if(temp.right != null){  
                    rightMax = largestElement(temp.right);  
                    //Comparing max with rightMax and store greater value into max  
                    max = Math.max(max, rightMax);  
                }  
                return max;  
           }  
      }  
  
      public static void main(String[] args) {  
  
        LargestNodeBST bint = new LargestNodeBST();  
        //Adding nodes to the binary tree  
        bint.root = new Node(5);  
        bint.root.left = new Node(19);  
        bint.root.right = new Node(28);  
        bint.root.left.left = new Node(42);  
        bint.root.right.left = new Node(68);  
        bint.root.right.right = new Node(10);  
  
        //Display largest node in the binary tree  
        System.out.println("Largest Node in the binary tree: " + bintt.largestElement(bint.root));  
      }  
}  
Output:

Largest Node in the binary tree: 68
public class SmallestNodeBST {  
      public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assigning data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
      }  
  
      //Represents the root of binary tree  
      public Node root;  
  
      public SmallestNode(){  
          root = null;  
      }  
  
      //smallestElement() this will find out the smallest node in the binary tree  
      public int smallestElement(Node temp){  
          //Checking whether tree is empty  
          if(root == null) {  
              System.out.println("Tree is empty");  
              return 0;  
          }  
          else {  
                int leftMin, rightMin;  
                //Min will store temp's data  
                int min = temp.data;  
  
                //This will find smallest element in left subtree  
                if(temp.left != null){  
                  leftMin = smallestElement(temp.left);  
                  //If min is greater than leftMin then store the value of leftMin into min  
                  min = Math.min(min, leftMin);  
                }  
  
                //This will find smallest element in right subtree  
                if(temp.right != null){  
                  rightMin = smallestElement(temp.right);  
                  //If min is greater than rightMin then store the value of rightMin into min  
                  min = Math.min(min, rightMin);  
                }  
                return min;  
          }  
      }  
  
      public static void main(String[] args) {  
  
        SmallestNodeBST bint = new SmallestNodeBST();  
        //Adding nodes to the binary tree  
        bint.root = new Node(8);  
        bint.root.left = new Node(20);  
        bint.root.right = new Node(15);  
        bint.root.left.left = new Node(12);  
        bint.root.right.left = new Node(25);  
        bint.root.right.right = new Node(36);  
  
        //Displays smallest node in the binary tree  
        System.out.println("Smallest node in the binary tree: " + bint.smallestElement(bint.root));  
      }  
}  
Output:

Smallest node in the binary tree: 8
public class SumNodes {  
  
      public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assigning data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
      }  
  
      //Represent the root of binary tree  
      public Node root;  
  
      public SumOfNodes(){  
        root = null;  
      }  
  
      //calculateSum() this will calculate the sum of all the nodes present in the binary tree  
      public int calculateSum(Node temp){  
        int sum, sumLeft, sumRight;  
        sum = sumRight = sumLeft = 0;  
  
        //Check whether tree is empty  
        if(root == null) {  
            System.out.println("Tree is empty");  
            return 0;  
        }  
        else {  
            //Calculate the sum of nodes present in left subtree  
            if(temp.left != null)  
                sumLeft = calculateSum(temp.left);  
  
            //Calculate the sum of nodes present in right subtree  
            if(temp.right != null)  
                sumRight = calculateSum(temp.right);  
  
            //Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data  
            sum = temp.data + sumLeft + sumRight;  
            return sum;  
        }  
      }  
  
      public static void main(String[] args) {  
  
        SumNodes bint = new SumNodes();  
        //Add nodes to the binary tree  
        bint.root = new Node(8);  
        bint.root.left = new Node(6);  
        bint.root.right = new Node(4);  
        bint.root.left.left = new Node(10);  
        bint.root.right.left = new Node(15);  
  
        //Displays the sum of all the nodes in the given binary tree  
        System.out.println("Sum of all nodes of binary tree: " + bint.calculateSum(bint.root));  
      }  
    }  
Output:

Sum of all nodes of binary tree: 43
public class BinaryTreeDepth {  
  
    //Represent the node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assigning data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
    }  
  
    public Node root;  
    public BinaryTree(){  
        root = null;  
    }  
  
    //findHeight() this will determine the maximum height of the binary tree  
    public int findHeight(Node temp){  
        //Check whether tree is empty  
        if(root == null) {  
             System.out.println("Tree is empty");  
            return 0;  
        }  
        else {  
            int leftHeight = 0, rightHeight = 0;  
  
            //Calculate the height of left subtree  
            if(temp.left != null)  
                leftHeight = findHeight(temp.left);  
  
            //Calculate the height of right subtree  
            if(temp.right != null)  
                rightHeight = findHeight(temp.right);  
  
            //Compare height of left subtree and right subtree  
            //and store maximum of two in variable max  
            int max = (leftHeight > rightHeight) ? leftHeight : rightHeight;  
  
            //Calculate the total height of tree by adding height of root  
            return (max + 1);  
        }  
     }  
  
    public static void main(String[] args) {  
  
        BinaryTreeDepth bint = new BinaryTreeDepth();  
        //Adding nodes to the binary tree  
        bint.root = new Node(10);  
        bint.root.left = new Node(20);  
        bint.root.right = new Node(30);  
        bint.root.left.left = new Node(40);  
        bint.root.right.left = new Node(50);  
        bint.root.right.right = new Node(60);  
        bint.root.right.right.right= new Node(70);  
        bint.root.right.right.right.right = new Node(80);  
  
        //Displays the maximum height of the given binary tree  
        System.out.println("Height of given binary tree: " + bint.findHeight(bint.root));  
  }  
}  
Output:

Height of given binary tree: 5
public class JavaExceptionExample{  
  public static void main(String args[]){  
   try{  
      //code that may raise exception  
      int data=100/0;  
   }catch(ArithmeticException e){System.out.println(e);}  
   //rest code of the program   
   System.out.println("rest of the code...");  
  }  
}  
public class MultipleCatch {  
  
    public static void main(String[] args) {  
          
           try{    
                int a[]=new int[5];    
                
                System.out.println(a[8]);  
               }    
               catch(ArithmeticException e)  
                  {  
                   System.out.println("Arithmetic Exception occurs");  
                  }    
               catch(ArrayIndexOutOfBoundsException e)  
                  {  
                   System.out.println("ArrayIndexOutOfBounds Exception occurs");  
                  }    
               catch(Exception e)  
                  {  
                   System.out.println("Parent Exception occurs");  
                  }             
               System.out.println("remaining code");    
    }  
}  

Output:
ArrayIndexOutOfBounds Exception occurs
remaining code
class NestedExample{  
 public static void main(String args[]){  
  try{  
    try{  
     System.out.println("Division");  
     int b =32/0;  
    }catch(ArithmeticException e){System.out.println(e);}  
   
    try{  
    int a[]=new int[5];  
    a[5]=3;  
    }catch(ArrayIndexOutOfBoundsException e){System.out.println(e);}  
     
    System.out.println("other statement");  
  }catch(Exception e){System.out.println("handeled");}  
  
  System.out.println("normal flow.");  
 }  
}  
public class Finalblock{  
  public static void main(String args[]){  
  try{  
   int data=25/0;  
   System.out.println(data);  
  }  
  catch(ArithmeticException e){System.out.println(e);}  
  finally{System.out.println("finally block is always executed");}  
  System.out.println("remaining code.");  
  }  
}  

Output:
Exception in thread main java.lang.ArithmeticException:/ by zero
       finally block is always executed
       remaining code.
public class TestThrow{  
   static void validate(int age){  
     if(age<18)  
      throw new ArithmeticException("not valid");  
     else  
      System.out.println("welcome to vote");  
   }  
   public static void main(String args[]){  
      validate(13);  
      System.out.println("remaining code.");  
  }  
}  

Output:
Exception in thread main java.lang.ArithmeticException:not valid
class CustomException1{  
  
   static void validate(int age)throws InvalidAgeException{  
     if(age<18)  
      throw new InvalidAgeException("not valid");  
     else  
      System.out.println("welcome to vote");  
   }  
     
   public static void main(String args[]){  
      try{  
      validate(12);  
      }catch(Exception m){System.out.println("Exception occured: "+m);}  
  
      System.out.println("remaining code.");  
  }  
}  
Output:Exception occured: InvalidAgeException:not valid
       remaining code.
class TableSync{  
  
void printTable(int n){  
   synchronized(this){//synchronized block  
     for(int i=1;i<=5;i++){  
      System.out.println(n*i);  
      try{  
       Thread.sleep(300);  
      }catch(Exception e){System.out.println(e);}  
     }  
   }  
}//end of the method  
}  
  
public class TestSynchronized{  
public static void main(String args[]){  
final Table obj = new Table();//only one object  
  
Thread t1=new Thread(){  
public void run(){  
obj.printTable(4);  
}  
};  
Thread t2=new Thread(){  
public void run(){  
obj.printTable(100);  
}  
};  
  
t1.start();  
t2.start();  
}  
} 

hello.html


  
  
  

hello.jsp

  
  
<%  
String name=request.getParameter("uname");  
out.print("welcome "+name);  
%>  
  
  
  

index.jsp


  
  
  

hello.jsp

  
  
<%= "Welcome "+request.getParameter("uname") %>  
  
  

index.jsp

  
  
<%!   
int square(int n){  
return n*n;  
}  
%>  
<%= "Square of 2 is:"+square(4) %>  
  
  

Bubble sorting is one of the simplest sorts. The general idea is to swap small numbers to the front by comparing and exchanging with adjacent elements. This process is similar to the fact that the blisters rise, hence the name. Take a chestnut and sort the unordered sequences of 5, 3, 8, 6, and 4. First, bubbling from the back to the front, 4 and 6 comparison, swapping 4 to the front, and the sequence becomes 5, 3, 8, 4, 6. In the same way, 4 and 8 are exchanged, and 5, 3, 4, 8, 6, 3, and 4 are exchanged. 5 and 3 exchange, become 3,5,4,8,6,3. This time the bubbling is finished, the smallest number 3 is discharged to the front. Bubbling the remaining sequences in turn yields an ordered sequence. The time complexity of bubble sorting is O(n^2).

Public  class  BubbleSort {

    Public  static  void  bubbleSort ( int [] arr ) {
         if (arr ==  null  || arr . length ==  0 )
             return ;
         for ( int i = 0 ; i < arr . length - 1 ; i ++ ) {
             for ( Int j = arr . length - 1 ; j > i; j-- ) {
                 if (arr[j] < arr[j - 1 ]) {
                    Swap(arr, j - 1 , j);
                }
            }
        }
    }


    Public  static  void  swap ( int [] arr , int  i , int  j ) {
         int temp = arr[i];
        Arr[i] = arr[j];
        Arr[j] = temp;
    }
}

The idea of ​​choosing sorting is actually similar to bubble sorting, which puts the smallest element to the front after a sort. But the process is different, bubble sorting is through adjacent comparisons and exchanges. The choice of sorting is through the choice of the whole. For a chestnut, simple sorting of the unordered sequence of 5, 3, 8, 6, 4, first choose the smallest number other than 5 to exchange with 5, that is, select 3 and 5 exchanges, after a sorting becomes 3,5,8,6,4. Select and exchange the remaining sequences at once, and finally get an ordered sequence. In fact, the choice of sorting can be seen as the optimization of the bubble sorting, because the purpose is the same, but the sorting is only exchanged under the premise of determining the minimum number, which greatly reduces the number of exchanges. The time complexity of selecting sorting is O(n^2)

public class SelectSort {

    public static void selectSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        int minIndex = 0;
        for(int i=0; i<arr.length-1; i++) { 
            minIndex = i;
            for(int j=i+1; j<arr.length; j++) { 
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if(minIndex != i) { 
                swap(arr, i, minIndex);
            }
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

Insert sorting does not achieve sorting by swapping locations but by finding the appropriate location insert elements. I believe that everyone has had the experience of playing cards, especially the number of cards. You may have to sort out your cards when you split the cards. How do you sort them out when you have more cards? Just get a card and find a suitable place to insert. This principle is actually the same as insert sorting. For a chestnut, simply insert the 5, 3, 8, 6, 4 unordered sequence, first assume that the position of the first number is correct. Think about the first card when you get it. . Then 3 is to be inserted in front of 5, and 5 is moved back to 3, 5, 8, 6, and 4. It should be the same when thinking about finishing cards. Then 8 does not move, 6 is inserted in front of 8, 8 is shifted back by one, 4 is inserted in front of 5, and one is moved backward from 5 to one. Note that when inserting a number, make sure that the number before the number is already ordered. The time complexity of simple insert sorting is also O(n^2).

public class InsertSort {

    public static void insertSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;

        for(int i=1; i<arr.length; i++) { 

            int j = i;
            int target = arr[i]; 

            
            while(j > 0 && target < arr[j-1]) {
                arr[j] = arr[j-1];
                j --;
            }

            arr[j] = target;
        }

    }

}

Quick sorting is very high-end when listening to a name. Quick sorting is actually the best performing sorting algorithm in practical applications. Quick sorting is high-end, but in fact its idea is from bubble sorting. Bubble sorting is to minimize the bubbling to the top by comparing and swapping adjacent elements, while fast sorting is to compare and exchange decimals and large numbers. Not only will the decimals bubble up to the top but also the big numbers below.

Give a chestnut: Quickly sort the unordered sequence of 5, 3, 8, 6, 4. The idea is that the right pointer is smaller than the reference number, and the left pointer is larger than the reference number and exchanged.

5,3,8,6,4 Use 5 as the benchmark for comparison. Finally, move 5 small to the left of 5, and move to the right of 5 by 5.

5,3,8,6,4 First set i, j two pointers point to the two ends, j pointer scan first (think why?) 4 to 5 small stop. Then i scan, 8 to 5 stop. Exchange i, j position.

5,3,4,6,8 Then the j pointer is scanned again. At this time, when j scans 4, the two pointers meet. stop. Then exchange 4 and the reference number.

4,3,5,6,8 After one division, the goal of the left side is smaller than 5 and the right side is larger than 5. The left and right subsequences are then recursively sorted to finally obtain an ordered sequence.

There is a question left on it. Why do you have to move the pointer first? First of all, this is not absolute, depending on the position of the reference number, because when the last two pointers meet, the reference number is exchanged to the position of the encounter. Generally, the first number is selected as the reference number, then it is on the left side, so the number of the last encounters must be exchanged with the reference number, so the number of encounters must be smaller than the reference number. So the j pointer moves first to find a number smaller than the base number.

Quick sorting is unstable, and its time average time complexity is O(nlgn).

public class QuickSort {
    
    public static int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];
        int pivotPointer = left;

        while(left < right) {
            while(left < right && arr[right] >= pivotKey)
                right --;
            while(left < right && arr[left] <= pivotKey)
                left ++;
            swap(arr, left, right); 
        }
        swap(arr, pivotPointer, left); 
        return left;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int pivotPos = partition(arr, left, right);
        quickSort(arr, left, pivotPos-1);
        quickSort(arr, pivotPos+1, right);
    }

    public static void sort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        quickSort(arr, 0, arr.length-1);
    }

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}

Heap sorting is a sorting of choices implemented by means of heaps, and the idea is sorted with simple choices. The following is an example of a large top heap. Note: If you want to sort in ascending order, use the big top heap, and vice versa. The reason is that the top element of the heap needs to be swapped to the end of the sequence.

First, implementing heap sorting requires solving two problems:

How to make a heap from an unordered sequence key?

How do you adjust the remaining elements to a new heap after outputting the top element?

The first problem is that you can directly use a linear array to represent a heap. Building a heap from the initial unordered sequence requires a bottom-up adjustment from the first non-leaf element to a heap.

The second question, how to adjust to piles? The first is to exchange the top and bottom elements. Then compare the left and right child nodes of the current top element, because in addition to the current heap top element, the left and right child heaps satisfy the condition, then the current top top element needs to be exchanged with the larger (large top heap) of the left and right child nodes until Leaf node. We call this adjustment from the top of the pile to the screen.

The process of building a heap from an unordered sequence is a process of repeated screening. If this sequence is considered to be a complete binary tree, then the last non-terminal node is n/2 to take the bottom element, and thus can be filtered. Give a chestnut:

The stacking of 49, 38, 65, 97, 76, 13, 27, 49 sequences The initial heap and adjustment process is as follows: 

public class HeapSort {

   
    public static void heapAdjust(int[] arr, int start, int end) {
        int temp = arr[start];

        for(int i=2*start+1; i<=end; i*=2) {
     
            if(i < end && arr[i] < arr[i+1]) {
                i ++; 
            }
            if(temp >= arr[i]) {
                break; 
            }
            arr[start] = arr[i]; 
            start = i; 
        }

        arr[start] = temp;
    }


    public static void heapSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;

        
        for(int i=arr.length/2; i>=0; i--) {
            heapAdjust(arr, i, arr.length-1);
        }

        for(int i=arr.length-1; i>=0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i-1);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Hill sorting is an efficient implementation of insert sorting, also called downsizing incremental sorting. In simple insert sorting, if the sequence to be sorted is positive, the time complexity is O(n). If the sequence is basically ordered, the efficiency of using direct insert sorting is very high. Hill sorting takes advantage of this feature. The basic idea is: first divide the entire sequence to be recorded into several sub-sequences for direct insertion sorting, and then perform a direct insertion sorting on all records when the records in the entire sequence are basically ordered.

Give a chestnut:

As can be seen from the above sorting process, the feature of the Hill sorting is that the subsequence is not simply segmented by segment, but a record separated by an increment is composed into a subsequence. As in the example above, the increment of the first sort is 5, and the increment of the second sort is 3. Since the keywords recorded in the first two insertions are compared with the keywords of the previous record in the same subsequence, the smaller records are not moved step by step, but jumped to Moving forward, so that when the last order is sorted, the entire sequence has been basically ordered, as long as a small amount of comparison and movement of the record is made. Therefore, Hill sorting is more efficient than direct insert sorting.

The analysis of Hill sorting is complex, and time complexity is a function of the increment taken, which involves some mathematical problems. However, based on a large number of experiments, when n is in a certain range, the time complexity can reach O(n^1.3).

public class ShellSort {

    public static void shellInsert(int[] arr, int d) {
        for(int i=d; i<arr.length; i++) {
            int j = i - d;
            int temp = arr[i];    
            while (j>=0 && arr[j]>temp) {     
                arr[j+d] = arr[j];   
                j -= d;  
            }  

            if (j != i - d)    
                arr[j+d] = temp;

        }
    }

    public static void shellSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        int d = arr.length / 2;
        while(d >= 1) {
            shellInsert(arr, d);
            d /= 2;
        }
    }

}

Merging and sorting is another different sorting method, because the merge sorting uses the idea of ​​recursive partitioning, so it is easier to understand. The basic idea is to recursively sub-problems and then merge the results. The sequence to be sorted is treated as two ordered subsequences, then the two subsequences are merged, and the subsequences are then treated as two ordered sequences. . . . . Looking backwards, in fact, it is the first two or two mergers, and then the four or four mergers. . . Eventually an ordered sequence is formed. The space complexity is O(n) and the time complexity is O(nlogn).

public class MergeSort {

    public static void mergeSort(int[] arr) {
        mSort(arr, 0, arr.length-1);
    }

    
    public static void mSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int mid = (left + right) / 2;

        mSort(arr, left, mid); 
        mSort(arr, mid+1, right); 
        merge(arr, left, mid, right); 
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        //[left, mid] [mid+1, right]
        int[] temp = new int[right - left + 1]; 

        int i = left;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
            }
        }

        while(i <= mid) {
            temp[k++] = arr[i++];
        }

        while(j <= right) {
            temp[k++] = arr[j++];
        }

        for(int p=0; p<temp.length; p++) {
            arr[left + p] = temp[p];
        }

    }
}

If an interviewer asks you to write an O(n) time complexity sorting algorithm during the interview, you should never say: This is impossible! Although the lower limit of the previous sort based on comparison is O(nlogn). However, there is indeed a linear time complexity ordering, except that there is a premise that the number to be sorted must satisfy a certain range of integers, and counting sorting requires more auxiliary space. The basic idea is to count the number of each number by using the number to be sorted as the subscript of the count array. Then output sequentially to get an ordered sequence.

public class CountSort {

    public static void countSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;

        int max = max(arr);

        int[] count = new int[max+1];
        Arrays.fill(count, 0);

        for(int i=0; i<arr.length; i++) {
            count[arr[i]] ++;
        }

        int k = 0;
        for(int i=0; i<=max; i++) {
            for(int j=0; j<count[i]; j++) {
                arr[k++] = i;
            }
        }

    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            if(ele > max)
                max = ele;
        }

        return max;
    }

}

Bucket sorting is an improvement and promotion of counting sorting, but there are many materials on the Internet that confuse counting sorting and bucket sorting. In fact, bucket sorting is much more complicated than counting sorting.

The basic idea of ​​bucket sorting:

Suppose there is a set of key sequence K[1….n] of length N. First divide this sequence into M subintervals (barrels). Then, based on a mapping function, the keyword k of the sequence to be sorted is mapped into the i-th bucket (ie, the subscript i of the bucket array B), then the keyword k is taken as an element in B[i] (each Bucket B[i] is a set of sequences of size N/M). Then compare and sort all the elements in each bucket B[i] (you can use fast queue). Then enumerate all the contents of the output B[0]….B[M] in sequence, which is an ordered sequence. Bindex=f(key) where bindex is the subscript of the bucket array B (ie, the bindex bucket), and k is the key of the sequence to be sorted. The key to bucket sorting efficiency is the mapping function, which must be done: if the keyword k1 < k2, then f(k1) <= f(k2).

In other words, the minimum data in B(i) is greater than the largest data in B(i-1). Obviously, the determination of the mapping function has a lot to do with the characteristics of the data itself.

Give a chestnut: 

Suppose the sequence K = {49, 38, 35, 97, 76, 73, 27, 49}. These data are all between 1 and 100. So we customize 10 buckets and then determine the mapping function f(k) = k/10. Then the first keyword 49 will be located in the 4th bucket (49/10=4). All the keywords are piled into the bucket in turn, and quickly sorted in each non-empty bucket to get the figure as shown. An ordered sequence can be obtained by sequentially outputting the data in each B[i].

Bucket sorting analysis:

Bucket sorting utilizes the mapping of functions, reducing almost all comparison work. In fact, the calculation of the f(k) value of bucket sorting is equivalent to the division in the fast row, the subsequence in the hill sorting, the subproblem in the merge sorting, and the large amount of data has been segmented into basically ordered. Data block (bucket). Then you only need to do advanced comparison sorting on a small amount of data in the bucket. 

The time complexity of bucket sorting for N keywords is divided into two parts:

(1) Cycle calculation of the bucket mapping function for each keyword. This time complexity is O(N).

(2) Using the advanced comparison sorting algorithm to sort all the data in each bucket, the time complexity is ∑ O(Ni*logNi). Where Ni is the amount of data for the i-th bucket.

Obviously, part (2) is the decisive factor in the performance of the barrel sorting. Minimizing the amount of data in the bucket is the only way to increase efficiency (because the best average time complexity based on comparison sorting can only reach O(N*logN)). Therefore, we need to do the following two things:

(1) The mapping function f(k) can evenly distribute N data into M buckets, so that each bucket has [N/M] data amount.

(2) Try to increase the number of buckets. In the limit case, only one data can be obtained per bucket, which completely avoids the “comparison” sorting operation of the data in the bucket. Of course, it is not easy to do this. In the case of a large amount of data, the f(k) function will make the number of bucket collections huge and the space was wasted. This is a trade-off between time and space costs.

For N rows of data to be queued, M buckets, the average bucket sorting average time complexity of each bucket [N/M] data is:

O(N)+O(M*(N/M) log(N/M))=O(N+N (logN-logM))=O(N+N logN-N logM) When N=M, That is, in the limit case, there is only one data per bucket. The best efficiency of bucket sorting can reach O(N).

Summary: The average time complexity of bucket sorting is linear O(N+C), where C=N*(logN-logM). If the number of buckets M is larger with respect to the same N, the efficiency is higher, and the best time complexity reaches O(N). Of course, the space complexity of bucket sorting is O(N+M). If the input data is very large and the number of buckets is very large, the space cost is undoubtedly expensive. In addition, bucket sorting is stable.

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if(arr == null && arr.length == 0)
            return ;

        int bucketNums = 10; 
        List buckets = new ArrayList(); 

        for(int i=0; i<10; i++) {
            buckets.add(new LinkedList()); 
        }

        
        for(int i=0; i<arr.length; i++) {
            buckets.get(f(arr[i])).add(arr[i]);
        }

        
        for(int i=0; i<buckets.size(); i++) {
            if(!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i);
            }
        }

            int k = 0;
        for(List bucket : buckets) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }

    
    public static int f(int x) {
        return x / 10;
    }

}

The cardinality sorting is a sorting method different from the previous sorting method, and the cardinality sorting does not require comparison between the recording keywords. Cardinality sorting is a method of sorting single logical keywords by means of multi-keyword sorting. The so-called multi-keyword sorting is to have multiple keywords with different priorities. For example, if the scores of the two people are the same, the higher the language is in the front and the higher in the Chinese language, the higher the mathematics is in the front. . . If the numbers are sorted, the ones, tens, and hundreds are the keywords of different priorities. If the sort is to be sorted, the ones, tens, and hundreds are incremented at a time. The cardinality sorting is achieved by multiple allocations and collections, and the keywords with low priority are assigned and collected first.

Public  class  RadixSort {

    Public  static  void  radixSort ( int [] arr ) {
         if (arr ==  null  && arr . length ==  0 )
             return ;

        Int maxBit = getMaxBit(arr);


        For ( int i = 1 ; i <= maxBit; i ++ ) {

            List< List< Integer > > buf = distribute(arr, i); // Assign 
            collecte(arr, buf); // Collection
        }

    }

   public static List< List< Integer > > distribute ( int [] arr , int iBit ) {
         List< List< Integer > > buf = new ArrayList< List< Integer > > ();
         for ( int j = 0 ; j     
          < 10 ; j ++ ) {
            Buf . add( new  LinkedList< Integer > ());
        }
        For ( int i = 0 ; i < arr . length; i ++ ) {
            Buf . get(getNBit(arr[i], iBit)) . add(arr[i]);
        }
        Return buf;
    }

   public static void collecte ( int [] arr , List< List< Integer > > buf ) {
         int k = 0 ;
         for ( List< Integer > bucket : buf) {
             for ( int ele : bucket) {     
         
                Arr[k ++ ] = ele;
            }
        }


    }
 public static int getMaxBit ( int [] arr ) {
         int max = Integer . MIN_VALUE ;
         for ( int ele : arr) {
             int len = (ele + " " ) . length();
             if (len > max)     
        
                Max = len;
        }
   public static int getNBit ( int x , int n ) {     
         

        String sx = x +  " " ;
         if (sx . length() < n)
             return  0 ;
         else 
            return sx . charAt(sx . length() - n) -  ' 0 ' ;
    }

}

Related Articles

Core Java

1. What are primitive types in Java ? byte, short, int, long, float, double, char, boolean… 2. What are tokens? Name the 5 types of tokens available in Java with an example…

Hackerearth-Java

     1. Challenge : Welcome to Java! Welcome to the world of Java! In this challenge, we practice printing to stdout. The code stubs…

Spring

1. Hello World Program HelloWorld.java MainApp.java 2. How to create Spring applcation. Create Java Class Create XML File Create test class Load jar files required…

SPRING

1. Hello World Program HelloWorld.java package com.kodnest; public class HelloWorld { private String message; public void setMessage(String message){ this.message = message; } public void getMessage(){…

Responses

Your email address will not be published. Required fields are marked *

KodNest Training New Batch is starting on 02nd November 2020. Attend one week free demo classes.Register Now

New Report

Close