1.

Linear and Binary Search Implementation

Aim:
To implement linear and binary search using both recursive and non-recursive functions in Java.

Code:

import java.util.Scanner;

public class SearchAlgorithms {

// Linear Search

public static int linearSearch(int[] arr, int key) {

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

if (arr[i] == key) return i;

return -1;

// Binary Search Iterative

public static int binarySearchIterative(int[] arr, int key) {

int low = 0, high = arr.length - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == key) return mid;

else if (arr[mid] < key) low = mid + 1;

else high = mid - 1;

return -1;

// Binary Search Recursive

public static int binarySearchRecursive(int[] arr, int low, int high, int key) {

if (low > high) return -1;

int mid = (low + high) / 2;

 if (arr[mid] == key) return mid;

else if (arr[mid] < key) return binarySearchRecursive(arr, mid + 1, high, key);

else return binarySearchRecursive(arr, low, mid - 1, key);

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of elements:");

int n = scanner.nextInt();

int[] arr = new int[n];

System.out.println("Enter the elements:");

for (int i = 0; i < n; i++) arr[i] = scanner.nextInt();

System.out.println("Enter the element to search:");

int key = scanner.nextInt();

// Linear Search

int linearResult = linearSearch(arr, key);

System.out.println("Linear Search Result: " +

(linearResult != -1 ? "Element found at index " + linearResult : "Element not found"));

// Binary Search Iterative

int binaryResultIterative = binarySearchIterative(arr, key);

System.out.println("Binary Search (Iterative) Result: " +

(binaryResultIterative != -1 ? "Element found at index " + binaryResultIterative : "Element

not found"));

// Binary Search Recursive

int binaryResultRecursive = binarySearchRecursive(arr, 0, arr.length - 1, key);

System.out.println("Binary Search (Recursive) Result: " +

 (binaryResultRecursive != -1 ? "Element found at index " + binaryResultRecursive : "Element
not found"));

scanner.close();

Sample Input:

Enter the number of elements:

Enter the elements:

2 4 6 8 10

Enter the element to search:

Actual Output:

Linear Search Result: Element found at index 3

Binary Search (Iterative) Result: Element found at index 3

Binary Search (Recursive) Result: Element found at index 3

2. List ADT Implementation with Arrays and Linked Lists

Aim:
To implement List ADT using arrays and linked lists.

Code:

import java.util.ArrayList;

class ListUsingArray {

private ArrayList<Integer> list = new ArrayList<>();

public void add(int element) {

list.add(element);

System.out.println("Added: " + element);

}
 public void remove(int element) {

if (list.remove(Integer.valueOf(element)))

System.out.println("Removed: " + element);

else

System.out.println("Element not found: " + element);

public void display() {

System.out.println("List: " + list);

class Node {

int data;

Node next;

Node(int data) {

this.data = data;

this.next = null;

class ListUsingLinkedList {

private Node head;

public void add(int data) {

Node newNode = new Node(data);

if (head == null) {

head = newNode;

} else {

Node current = head;

 while (current.next != null) current = current.next;

current.next = newNode;

System.out.println("Added: " + data);

public void remove(int data) {

if (head == null) return;

if (head.data == data) {

head = head.next;

System.out.println("Removed: " + data);

return;

Node current = head;

while (current.next != null && current.next.data != data) current = current.next;

if (current.next != null) {

current.next = current.next.next;

System.out.println("Removed: " + data);

} else {

System.out.println("Element not found: " + data);

public void display() {

Node current = head;

System.out.print("List: ");

while (current != null) {

System.out.print(current.data + " ");

current = current.next;

System.out.println();
 }

Sample Input (Array Implementation):

Add: 10, 20, 30

Remove: 20

Display List

Actual Output:

Added: 10

Added: 20

Added: 30

Removed: 20

List: [10, 30]

Sample Input (Linked List Implementation):

Add: 15, 25

Remove: 15

Display List

Actual Output:

Added: 15

Added: 25

Removed: 15

List: 25

3. Stack ADT and Queue ADT Implementation Using Arrays

Aim:
To implement Stack ADT and Queue ADT using arrays.

Code (Stack ADT):

class Stack {

private int[] stack;

private int top;

private int size;

public Stack(int size) {

this.size = size;

stack = new int[size];

top = -1;

public void push(int element) {

if (top == size - 1) {

System.out.println("Stack Overflow!");

} else {

stack[++top] = element;

System.out.println("Pushed: " + element);

public void pop() {

if (top == -1) {

System.out.println("Stack Underflow!");

} else {

System.out.println("Popped: " + stack[top--]);

public void display() {

if (top == -1) {

System.out.println("Stack is empty!");

} else {

System.out.print("Stack: ");

for (int i = 0; i <= top; i++) {

System.out.print(stack[i] + " ");

}
 System.out.println();

public class StackDemo {

public static void main(String[] args) {

Stack stack = new Stack(5);

stack.push(10);

stack.push(20);

stack.display();

stack.pop();

stack.display();

Sample Input (Stack):

Push: 10, 20

Display Stack

Pop

Display Stack

Actual Output (Stack):

Pushed: 10

Pushed: 20

Stack: 10 20

Popped: 20

Stack: 10

Code (Queue ADT):

class Queue {

private int[] queue;

private int front, rear, size;

public Queue(int size) {

this.size = size;

queue = new int[size];

front = -1;

rear = -1;

public void enqueue(int element) {

if (rear == size - 1) {

System.out.println("Queue Overflow!");

} else {

if (front == -1) front = 0;

queue[++rear] = element;

System.out.println("Enqueued: " + element);

public void dequeue() {

if (front == -1 || front > rear) {

System.out.println("Queue Underflow!");

} else {

System.out.println("Dequeued: " + queue[front++]);

public void display() {

if (front == -1 || front > rear) {

System.out.println("Queue is empty!");

} else {

System.out.print("Queue: ");

for (int i = front; i <= rear; i++) {

 System.out.print(queue[i] + " ");

System.out.println();

public class QueueDemo {

public static void main(String[] args) {

Queue queue = new Queue(5);

queue.enqueue(30);

queue.enqueue(40);

queue.display();

queue.dequeue();

queue.display();

Sample Input (Queue):

Enqueue: 30, 40

Display Queue

Dequeue

Display Queue

Actual Output (Queue):

Enqueued: 30

Enqueued: 40

Queue: 30 40

Dequeued: 30

Queue: 40

4. Convert Infix to Postfix Using Stack ADT

Aim:
To convert an infix expression to a postfix expression using Stack ADT.

Code:

import java.util.Stack;

public class InfixToPostfix {

public static int precedence(char ch) {

return switch (ch) {

case '+', '-' -> 1;

case '*', '/' -> 2;

case '^' -> 3;

default -> -1;

};

public static String convertToPostfix(String expression) {

StringBuilder result = new StringBuilder();

Stack<Character> stack = new Stack<>();

for (int i = 0; i < expression.length(); i++) {

char c = expression.charAt(i);

// If the character is an operand, add it to output

if (Character.isLetterOrDigit(c)) {

result.append(c);

// If the character is '(', push it onto the stack

else if (c == '(') {

stack.push(c);

// If the character is ')', pop until '(' is found

 else if (c == ')') {

while (!stack.isEmpty() && stack.peek() != '(') {

result.append(stack.pop());

if (!stack.isEmpty() && stack.peek() != '(') return "Invalid Expression";

else stack.pop();

} else {

// Operator: Pop operators with higher precedence

while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {

result.append(stack.pop());

stack.push(c);

// Pop remaining operators

while (!stack.isEmpty()) {

if (stack.peek() == '(') return "Invalid Expression";

result.append(stack.pop());

return result.toString();

public static void main(String[] args) {

String infix = "a+b*(c^d-e)^(f+g*h)-i";

System.out.println("Postfix Expression: " + convertToPostfix(infix));

Sample Input:

Infix Expression: a+b*(c^d-e)^(f+g*h)-i

Actual Output:

Postfix Expression: abcd^e-fgh*+^*+i-

5. Stack ADT and Queue ADT Implementation Using Singly Linked List

Aim:

To implement Stack ADT and Queue ADT using a singly linked list.

Code (Stack ADT):

class Node {

int data;

Node next;

Node(int data) {

this.data = data;

this.next = null;

class StackUsingLinkedList {

private Node top;

public StackUsingLinkedList() {

top = null;

public void push(int data) {

Node newNode = new Node(data);

newNode.next = top;

top = newNode;

System.out.println("Pushed: " + data);

}
 public void pop() {

if (top == null) {

System.out.println("Stack Underflow!");

} else {

System.out.println("Popped: " + top.data);

top = top.next;

public void display() {

if (top == null) {

System.out.println("Stack is empty!");

} else {

System.out.print("Stack: ");

Node temp = top;

while (temp != null) {

System.out.print(temp.data + " ");

temp = temp.next;

System.out.println();

public class StackLLDemo {

public static void main(String[] args) {

StackUsingLinkedList stack = new StackUsingLinkedList();

stack.push(10);

stack.push(20);

stack.display();

stack.pop();
 stack.display();

Sample Input (Stack):

Push: 10, 20

Display Stack

Pop

Display Stack

Actual Output (Stack):

Pushed: 10

Pushed: 20

Stack: 20 10

Popped: 20

Stack: 10

Code (Queue ADT):

class QueueUsingLinkedList {

private Node front, rear;

public QueueUsingLinkedList() {

front = rear = null;

public void enqueue(int data) {

Node newNode = new Node(data);

if (rear == null) {

front = rear = newNode;

} else {

rear.next = newNode;

rear = newNode;

}
 System.out.println("Enqueued: " + data);

public void dequeue() {

if (front == null) {

System.out.println("Queue Underflow!");

} else {

System.out.println("Dequeued: " + front.data);

front = front.next;

if (front == null) rear = null;

public void display() {

if (front == null) {

System.out.println("Queue is empty!");

} else {

System.out.print("Queue: ");

Node temp = front;

while (temp != null) {

System.out.print(temp.data + " ");

temp = temp.next;

System.out.println();

public class QueueLLDemo {

public static void main(String[] args) {

QueueUsingLinkedList queue = new QueueUsingLinkedList();

 queue.enqueue(30);

queue.enqueue(40);

queue.display();

queue.dequeue();

queue.display();

Sample Input (Queue):

Enqueue: 30, 40

Display Queue

Dequeue

Display Queue

Actual Output (Queue):

Enqueued: 30

Enqueued: 40

Queue: 30 40

Dequeued: 30

Queue: 40

6. Dequeue (Double-Ended Queue) Implementation Using Array and Linked Lists

Aim:

To implement Dequeue ADT using:

a) Array
b) Singly Linked List
c) Doubly Linked List

Code (Using Array):

class Dequeue {

private int[] dequeue;

private int front, rear, size;

public Dequeue(int size) {

this.size = size;
 dequeue = new int[size];

front = -1;

rear = -1;

public void insertFront(int data) {

if (front == 0 && rear == size - 1 || front == rear + 1) {

System.out.println("Dequeue Overflow!");

} else if (front == -1) {

front = rear = 0;

dequeue[front] = data;

} else if (front == 0) {

front = size - 1;

dequeue[front] = data;

} else {

dequeue[--front] = data;

System.out.println("Inserted at front: " + data);

public void insertRear(int data) {

if (front == 0 && rear == size - 1 || front == rear + 1) {

System.out.println("Dequeue Overflow!");

} else if (rear == -1) {

front = rear = 0;

dequeue[rear] = data;

} else if (rear == size - 1) {

rear = 0;

dequeue[rear] = data;

} else {

dequeue[++rear] = data;
 }

System.out.println("Inserted at rear: " + data);

public void deleteFront() {

if (front == -1) {

System.out.println("Dequeue Underflow!");

} else {

System.out.println("Deleted from front: " + dequeue[front]);

if (front == rear) {

front = rear = -1;

} else if (front == size - 1) {

front = 0;

} else {

front++;

public void deleteRear() {

if (front == -1) {

System.out.println("Dequeue Underflow!");

} else {

System.out.println("Deleted from rear: " + dequeue[rear]);

if (front == rear) {

front = rear = -1;

} else if (rear == 0) {

rear = size - 1;

} else {

rear--;

}
 }

public void display() {

if (front == -1) {

System.out.println("Dequeue is empty!");

} else {

System.out.print("Dequeue: ");

if (rear >= front) {

for (int i = front; i <= rear; i++) {

System.out.print(dequeue[i] + " ");

} else {

for (int i = front; i < size; i++) {

System.out.print(dequeue[i] + " ");

for (int i = 0; i <= rear; i++) {

System.out.print(dequeue[i] + " ");

System.out.println();

public class DequeueDemo {

public static void main(String[] args) {

Dequeue dequeue = new Dequeue(5);

dequeue.insertRear(10);

dequeue.insertFront(20);

dequeue.display();
 dequeue.deleteFront();

dequeue.deleteRear();

dequeue.display();

Sample Input (Dequeue Using Array):

InsertRear: 10

InsertFront: 20

Display Dequeue

DeleteFront

DeleteRear

Display Dequeue

Actual Output (Dequeue Using Array):

Inserted at rear: 10

Inserted at front: 20

Dequeue: 20 10

Deleted from front: 20

Deleted from rear: 10

Dequeue is empty!

7. Priority Queue ADT Implementation

Aim:

To implement a Priority Queue ADT in Java.

Code:

import java.util.PriorityQueue;

class PriorityQueueDemo {

public static void main(String[] args) {

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// Insert elements into the priority queue

 priorityQueue.add(30);

priorityQueue.add(20);

priorityQueue.add(40);

System.out.println("Priority Queue: " + priorityQueue);

// Remove the highest priority element

System.out.println("Removed: " + priorityQueue.poll());

// Display the remaining elements

System.out.println("Priority Queue after removal: " + priorityQueue);

// Peek the highest priority element

System.out.println("Highest priority element: " + priorityQueue.peek());

Sample Input:

Insert: 30, 20, 40

Poll

Peek

Actual Output:

Priority Queue: [20, 30, 40]

Removed: 20

Priority Queue after removal: [30, 40]

Highest priority element: 30

8. Binary Search Tree Operations

Aim:

To construct a Binary Search Tree (BST) and perform search and delete operations.

Code:

class Node {
 int key;

Node left, right;

public Node(int key) {

this.key = key;

left = right = null;

class BST {

Node root;

public BST() {

root = null;

void insert(int key) {

root = insertRec(root, key);

Node insertRec(Node root, int key) {

if (root == null) {

root = new Node(key);

return root;

if (key < root.key) {

root.left = insertRec(root.left, key);

} else if (key > root.key) {

root.right = insertRec(root.right, key);

return root;
}

void inorder() {

inorderRec(root);

void inorderRec(Node root) {

if (root != null) {

inorderRec(root.left);

System.out.print(root.key + " ");

inorderRec(root.right);

Node search(Node root, int key) {

if (root == null || root.key == key) return root;

if (key < root.key) return search(root.left, key);

return search(root.right, key);

void delete(int key) {

root = deleteRec(root, key);

Node deleteRec(Node root, int key) {

if (root == null) return root;

if (key < root.key) root.left = deleteRec(root.left, key);

else if (key > root.key) root.right = deleteRec(root.right);

else {

if (root.left == null) return root.right;

else if (root.right == null) return root.left;

 root.key = minValue(root.right);

root.right = deleteRec(root.right, root.key);

return root;

int minValue(Node root) {

int minValue = root.key;

while (root.left != null) {

root = root.left;

minValue = root.key;

return minValue;

public class BSTDemo {

public static void main(String[] args) {

BST bst = new BST();

bst.insert(50);

bst.insert(30);

bst.insert(70);

bst.insert(20);

bst.insert(40);

bst.insert(60);

bst.insert(80);

System.out.println("Inorder traversal of BST:");

bst.inorder();

System.out.println("\nSearch for 40:");

 System.out.println(bst.search(bst.root, 40) != null ? "Found" : "Not Found");

System.out.println("Delete 40:");

bst.delete(40);

System.out.println("Inorder traversal after deletion:");

bst.inorder();

Sample Input:

Insert: 50, 30, 70, 20, 40, 60, 80

Search: 40

Delete: 40

Inorder Traversal

Actual Output:

Inorder traversal of BST:

20 30 40 50 60 70 80

Search for 40:

Found

Delete 40:

Inorder traversal after deletion:

20 30 50 60 70 80

9. Dictionary ADT Using Hashing

Aim:

To implement a Dictionary (ADT) using Hashing.

Code:

import java.util.HashMap;

public class DictionaryDemo {

 public static void main(String[] args) {

HashMap<Integer, String> dictionary = new HashMap<>();

// Insert key-value pairs

dictionary.put(1, "One");

dictionary.put(2, "Two");

dictionary.put(3, "Three");

System.out.println("Dictionary: " + dictionary);

// Search for a key

System.out.println("Search key 2: " + dictionary.get(2));

// Delete a key-value pair

dictionary.remove(3);

System.out.println("Dictionary after deletion: " + dictionary);

// Display all entries

System.out.println("Final Dictionary: " + dictionary);

Sample Input:

Insert: (1, "One"), (2, "Two"), (3, "Three")

Search: 2

Delete: 3

Display Dictionary

Actual Output:

Dictionary: {1=One, 2=Two, 3=Three}

Search key 2: Two

Dictionary after deletion: {1=One, 2=Two}

Final Dictionary: {1=One, 2=Two}

10. Dijkstra’s Algorithm for Single-Source Shortest Path

Aim:

To implement Dijkstra’s algorithm for single-source shortest path in a graph.

Code:

import java.util.Arrays;

public class Dijkstra {

static final int INF = Integer.MAX_VALUE;

static int minDistance(int[] dist, boolean[] sptSet, int V) {

int min = INF, minIndex = -1;

for (int v = 0; v < V; v++) {

if (!sptSet[v] && dist[v] <= min) {

min = dist[v];

minIndex = v;

return minIndex;

static void dijkstra(int[][] graph, int src, int V) {

int[] dist = new int[V];

boolean[] sptSet = new boolean[V];

Arrays.fill(dist, INF);

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet, V);

sptSet[u] = true;
 for (int v = 0; v < V; v++) {

if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {

dist[v] = dist[u] + graph[u][v];

System.out.println("Vertex \t Distance from Source");

for (int i = 0; i < V; i++) {

System.out.println(i + " \t " + dist[i]);

public static void main(String[] args) {

int[][] graph = {

{0, 10, 0, 30, 100},

{10, 0, 50, 0, 0},

{0, 50, 0, 20, 10},

{30, 0, 20, 0, 60},

{100, 0, 10, 60, 0}

};

dijkstra(graph, 0, 5);

Sample Input:

Graph with vertices and weights

Source: 0

Actual Output:

Vertex Distance from Source

0 0

1 10
2 50

3 30

4 60