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 ' ;
}
}
Responses