Advance Java
1. Write an Example Snippet to Connect Java Application with mysql database.
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);
}
}
} 2. Wap to get the object of ResultSetMetaData.
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);}
}
}
3. Wap to create table in database.
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();
}
}
}
}
4. Wap to insert record in to table in the Database.
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();
}
}
}
}
5. Wap to Delete records in to a table in the database.
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();
}
}
}
}
6. Wap to update records in to a table in the database.
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();
}
}
}
}
7. How to execute and read select queries using JDBC?
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:@<hostname>:<port num>:<DB name>"
,"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();
}
}
}8. Write an example code for JDBC prepared statement.
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:@<hostname>:<port num>:<DB name>"
,"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){}
}
}
}9. Wap to reverse a linked list.
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 6510. Wap to insert a new node at the middle of the singly linked list.
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 11. Wap to insert new node at the start of the singly linked list.
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 12. Wap to insert new node at the end of the singly linked list.
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 13. Wap to delete a node in the middle of the singly linked list.
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 empty14. Wap to delete a node at the start of the singly linked list.
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 empty15. Wap to remove a node from the end of the singly linked list.
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 empty16. Wap to create and display circular Linked List.
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
17. Wap to generate Circular Linked List of N node and count nodes.
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: 618. Wap to find minimum and maximum node value in Circular Linked list.
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: 2419. Wap to insert node at the beginning of the Circular Linked list.
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 1020. Wap to insert a node at the end of the Circular linked list.
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 4021. Wap to insert a node at middle in Circular linked list.
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 4022. Wap to remove node at the beginning of the Circular Linked list.
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 empty23. Wap to remove node at the end of the Circular Linked list.
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 empty24. Wap to remove a node from middle of Circular Linked List.
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 empty25. Wap to implement Linked list as a queue (FIFO).
public class LinkedListExamples
{
public static void main(String[] args)
{
LinkedList<Integer> que = new LinkedList<Integer>();
//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
}
}26. Wap to replace an element at a specific position in linked list.
public class LinkedListReplace
{
public static void main(String[] args)
{
LinkedList<String> list = new LinkedList<String>();
//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]
}
}27. Wap to create clone of LinkedList.
public class LinkedListClone
{
public static void main(String[] args)
{
LinkedList<Integer> linkedList1 = new LinkedList<Integer>();
//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<Integer> linkedList2 = new LinkedList<Integer>();
//Cloning the linkedList1 into linkedList2
linkedList2 = (LinkedList<Integer>) linkedList1.clone();
//Printing the elements of linkedList2
System.out.println(linkedList2); //Output : [100, 200, 300, 400, 500]
}
}28. Wap to find the middle Node of a Linked List in single pass.
public class LinkedListMiddleNode {
public static void main(String args[]) {
//creating LinkedList with 5 elements including head
LinkList linkList = new LinkList();
LinkList.Node head = linkList.head();
linkList.add( new LinkList.Node("1"));
linkList.add( new LinkList.Node("2"));
linkList.add( new LinkList.Node("3"));
linkList.add( new LinkList.Node("4"));
//finding middle element of LinkedList in single pass
LinkList.Node current = head;
int length = 0;
LinkList.Node middle = head;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);
}
}
class LinkList{
private Node head;
private Node tail;
public LinkList(){
this.head = new Node("head");
tail = head;
}
public Node head(){
return head;
}
public void add(Node node){
tail.next = node;
tail = node;
}
public static class Node{
private Node next;
private String data;
public Node(String data){
this.data = data;
}
public String data() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node next() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String toString(){
return this.data;
}
}
}
Output:
length of LinkedList: 4
middle element of LinkedList: 2
29. Wap to convert binary tree to Doubly linked list.
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 7030. Wap to generate a Doubly linked list of n nodes and count numbers of node.
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: 531. Wap to get value of maximum and minimum node in Double Linked List.
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 : 4932. Wap to add new node at middle of Double Linked List.
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 33. Wap to add new node at the end of Double Linked List.
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);
}
}34. Wap to remove node from middle of Double Linked List.
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 empty35. Wap to remove node at the begining from Double Linked List.
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 empty36. Wap to remove node from the end of Doubly Linked List.
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 empty37. Wap to remove duplicate elements from Doubly Linked List.
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 5038. Wap to rotate Doubly Linked List by N nodes.
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 39. Wap to implement Binary Search Tree (BST).
ublic 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);
}
}40. Wap to find maximum width of a binary tree.
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<Node> queue = new LinkedList<Node>();
//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: 441. Wap to find largest Node in Binary tree.
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: 6842. Wap to find smallest node in Binary tree.
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: 843. Wap to find sum of all node in Binary Tree.
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: 4344. Wap to find maximum depth or height of a tree.
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: 545. Program to handle exception using try-catch statement.
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...");
}
} 46. Program for multiple catch block.
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 code47. Program for nested try block.
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.");
}
} 48. Program for final block.
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.48. Program for throw keyword.
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 valid49. Program for CustomExpection
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.50. Program for synchronized block using anonymous class.
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();
}
}
51. Program of Scriptlet tag to print user name.
hello.html
<html>
<body>
<form action="hello.jsp">
<input type="text" name="uname">
<input type="submit" value="go"><br/>
</form>
</body>
</html> hello.jsp
<html>
<body>
<%
String name=request.getParameter("uname");
out.print("welcome "+name);
%>
</form>
</body>
</html> 52. Program for expression tag that print user name.
index.jsp
<html>
<body>
<form action="hello.jsp">
<input type="text" name="uname"><br/>
<input type="submit" value="go">
</form>
</body>
</html> hello.jsp
<html>
<body>
<%= "Welcome "+request.getParameter("uname") %>
</body>
</html> 53. Program for JSP declaration tag .
index.jsp
<html>
<body>
<%!
int square(int n){
return n*n;
}
%>
<%= "Square of 2 is:"+square(4) %>
</body>
</html> 54. Bubble Sort
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;
}
}
55. Select Sort
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;
}
}
56. Insertion Sort
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;
}
}
}
57. Quick Sort
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;
}
}
58. Heap Sorting
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;
}
}
59. Hill Sorting
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;
}
}
}
60. Merge Sort
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];
}
}
}
61. Count Sort
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;
}
}
63. Bucket Sort
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<List<Integer>> buckets = new ArrayList<List<Integer>>();
for(int i=0; i<10; i++) {
buckets.add(new LinkedList<Integer>());
}
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<Integer> bucket : buckets) {
for(int ele : bucket) {
arr[k++] = ele;
}
}
}
public static int f(int x) {
return x / 10;
}
}
64. Cardinality Sort
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