LAB FILE

Advanced Data
Structure and
Algorithms
R1UC503B

Name: Divyam
Adm. No.: 22SCSE1570012
Section: 1 CNCS
Submitted to: Dr. Vipul Narayan

Program 1
Find the Maximum and Minimum Elements in
an Array: Write a function to find the
maximum and minimum elements in an array.
=>Program:
public class MaxMin {
public static int[] findMaxMin(int[] arr) {
int max = arr[0], min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
return new int[]{max, min};
}

public static void main(String[] args) {

int[] array = {3, 1, 4, 1, 5, 9, 2};
int[] result = findMaxMin(array);
System.out.println("Max: " + result[0] + "
Min: " + result[1]);
}
}
=>Output:
 Program 2
Reverse an Array: Write a function to reverse
an Array in place.
=>Program:
public class ReverseArray {
public static void reverse(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}

public static void main(String[] args) {

int[] array = {1, 2, 3, 4, 5};
reverse(array);
for (int num : array) {
System.out.print(num + " ");
}
}
}

=>Output:
 Program 3
Find the kth largest/smallest Element in an
Array:
Write a function to find the kth smallest or
largest element in an Array.
=>Program:
import java.util.Arrays;

public class KthElement {

public static int kthSmallest(int[] arr, int k) {
Arrays.sort(arr);
return arr[k - 1];
}

public static int kthLargest(int[] arr, int k) {

Arrays.sort(arr);
return arr[arr.length - k];
}

public static void main(String[] args) {

int[] array = {3, 1, 4, 1, 5, 9, 2};
int k = 3;
System.out.println("3rd Smallest: " + kthSmallest(array,
k));
System.out.println("3rd Largest: " + kthLargest(array,
k));
}
}

=>Output:
 Program 4
Sort an array of 0s, 1s and 2s: Given an array
containing only 0s, 1s and 2s. Sort the array in
linear time.
=>Program:
public class Sort012 {
public static void sort(int[] arr) {
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) {
swap(arr, low++, mid++);
} else if (arr[mid] == 1) {
mid++;
} else {
swap(arr, mid, high--);
}
}
}

private static void swap(int[] arr, int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String[] args) {

int[] array = {2, 0, 1, 2, 0, 1, 1};
sort(array);
for (int num : array) {
System.out.print(num + " ");
}
}
}

=>Output:

Program 5
Move All Zeroes to End of Array: Write a
function to move all zeroes in an array to the
end while maintaining the relative order of
other elements.
=>Program:
public class MoveZeroes {
public static void moveZeroes(int[] arr) {
int count = 0;
for (int num : arr) {
if (num != 0) {
arr[count++] = num;
}
}
while (count < arr.length) {
arr[count++] = 0;
}
}

public static void main(String[] args) {

int[] array = {0, 1, 0, 3, 12};
moveZeroes(array);
for (int num : array) {
System.out.print(num + " ");
}
}
}
=>Output:

Program 6
Reverse a Linked List: Write a function to
reverse a singly linked list.
=>Program:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class ReverseLinkedList {

public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}

public static void main(String[] args) {

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

ListNode reversedHead = reverseList(head);

while (reversedHead != null) {
System.out.print(reversedHead.val + " ");
reversedHead = reversedHead.next;
}
}
}
=>Output:

Program 7
Detect a Cycle in a Linked List: Write a
function to detect if a cycle exists in a linked
list.

=>Program:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class DetectCycle {

public static boolean hasCycle(ListNode head) {
if (head == null) return false;

ListNode slow = head; // Tortoise

ListNode fast = head; // Hare

while (fast != null && fast.next != null) {

slow = slow.next; // Move slow by 1
fast = fast.next.next; // Move fast by 2

if (slow == fast) { // Cycle detected

return true;
}
}
return false; // No cycle
}

public static void main(String[] args) {

// Creating a linked list with a cycle for testing
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = head.next; // Creating a cycle

boolean hasCycle = hasCycle(head);

System.out.println("Cycle detected: " + hasCycle);
}
}
=>Output:

Program 8
Find the Middle of a Linked List: Write a
function to find the middle element of a linked
list.
=>Program:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class FindMiddle {

public static ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

public static void main(String[] args) {

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

ListNode middle = findMiddle(head);

System.out.println("Middle element: " + middle.val);
}
}
=>Output:

Porgram 9
Merge Two Sorted Linked Lists: Write a
function to merge two sorted linked lists into
one sorted linked list.
=>Program:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class MergeTwoSortedLists {

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;

while (l1 != null && l2 != null) {

if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}

public static void main(String[] args) {

ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);

ListNode l2 = new ListNode(1);

l2.next = new ListNode(3);
l2.next.next = new ListNode(4);

ListNode mergedHead = mergeTwoLists(l1, l2);

while (mergedHead != null) {
System.out.print(mergedHead.val + " ");
 mergedHead = mergedHead.next;
}
}
}

=>Output:

Program 10
Remove Nth Node from End of List: Write a
function to remove the Nth node from the
start/end of a linked list.
=>Program:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class RemoveNthFromEnd {

public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;

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

first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}

public static void main(String[] args) {

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

head = removeNthFromEnd(head, 2);

while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
}

=>Output:

Program 11
Implement a Stack Using Arrays/Lists: Write a
function to implement a stack using an array
or list with basic operations: push, pop, peek,
and isEmpty.
=>Program:
import java.util.ArrayList;
import java.util.List;
public class Stack {
private List<Integer> stack;
public Stack() {
stack = new ArrayList<>();
}

public void push(int value) {

stack.add(value);
}
public int pop() {
if (stack.isEmpty()) {
System.out.println("Stack is empty. Can't pop");
return -1;
} else {
return stack.remove(stack.size() - 1);
}
}
public int peek() {
if (stack.isEmpty()) {
System.out.println("Stack is empty. Can't peek");
return -1;
} else {
return stack.get(stack.size() - 1);
}
}
public boolean isEmpty() {
return stack.isEmpty();
}

public static void main(String[] args) {

Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Peek: " + stack.peek());
System.out.println("Pop: " + stack.pop());
System.out.println("IsEmpty: " + stack.isEmpty());
}
}
=>Output:

Program 12
Implement a Stack Using Linked List: Write a
function to implement a stack using a linked
list with basic operations: push, pop, peek, and
isEmpty.
=>Program:
class ListNode {
int value;
ListNode next;
ListNode(int value) {
this.value = value;
}
}
public class Stack {
private ListNode top;
public Stack() {
top = null;
}
public void push(int value) {
ListNode newNode = new ListNode(value);
newNode.next = top;
top = newNode;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Can't pop");
return -1;
} else {
int poppedValue = top.value;
top = top.next;
return poppedValue;
}
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty. Can't peek");
return -1;
} else {
return top.value;
}
}
public boolean isEmpty() {
return top == null;
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(40);
stack.push(120);
 System.out.println("Peek: " + stack.peek());
System.out.println("Pop: " + stack.pop());
System.out.println("IsEmpty: " + stack.isEmpty());
}
}

=>Output:

Program 13
Check for Balanced Parentheses: Write a
function to check if a string containing
parentheses is balanced.
=>Program:
import java.util.Stack;

public class BalancedParentheses {

public static boolean isBalanced(String str) {
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
return false;
}
}
}
return stack.isEmpty();
}

public static void main(String[] args) {

String test1 = "(())"; // Balanced
String test2 = "(()"; // Unbalanced
String test3 = "())"; // Unbalanced
String test4 = "()()"; // Balanced

System.out.println("Test 1: " + isBalanced(test1)); // true

System.out.println("Test 2: " + isBalanced(test2)); // false
System.out.println("Test 3: " + isBalanced(test3)); // false
System.out.println("Test 4: " + isBalanced(test4)); // true
}
}
=>Output:

Program 14
Evaluate Postfix Expression: Write a function
to evaluate a given postfix expression.
=>Program:
import java.util.Stack;

public class PostfixEvaluator {

public static int evaluatePostfix(String expression) {
Stack<Integer> stack = new Stack<>();
for (char ch : expression.toCharArray()) {
if (Character.isDigit(ch)) {
stack.push(ch - '0'); // Convert char to int
} else {
int b = stack.pop();
int a = stack.pop();
switch (ch) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(a - b);
break;
case '*':
stack.push(a * b);
break;
case '/':
stack.push(a / b);
break;
}
}
}
return stack.pop(); // The result will be the only element left in the stack
}

public static void main(String[] args) {

String expression1 = "23*54*+";
String expression2 = "12+34-*";
String expression3 = "34+5*6-";

System.out.println("Result of expression 1: " + evaluatePostfix(expression1));

// 26
System.out.println("Result of expression 2: " + evaluatePostfix(expression2));
// -2
 System.out.println("Result of expression 3: " + evaluatePostfix(expression3));
// 27
}
}

=>Output:

Program 15
Next Greater Element: Write a function to find
the next greater element for each elementin
an array.
=>Program:
import java.util.Stack;
import java.util.Arrays;

public class NextGreaterElement {

public static int[] nextGreater(int[] nums) {
int[] result = new int[nums.length];
Stack<Integer> stack = new Stack<>();
Arrays.fill(result, -1);

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

while (!stack.isEmpty() &&
nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}

public static void main(String[] args) {

int[] nums = {4, 5, 2, 10, 8};
int[] result = nextGreater(nums);
 System.out.println(Arrays.toString(result)); //
[5, 10, 10, -1, -1]
}
}

=>Output:

Program 16
Implement a Queue Using Arrays/Lists: Write a
function to implement a queue using an array
or list with basic operations: enqueue,
dequeue, front, and isEmpty.
=>Program:
import java.util.LinkedList;

public class QueueUsingList {

private LinkedList<Integer> queue;

public QueueUsingList() {
queue = new LinkedList<>();
}
public void enqueue(int data) {
queue.addLast(data);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1;
}
return queue.removeFirst();
}
public int front() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return -1;
}
return queue.getFirst();
}

public boolean isEmpty() {

return queue.isEmpty();
}

public static void main(String[] args) {

QueueUsingList queue = new QueueUsingList();
queue.enqueue(1);
queue.enqueue(2);
 queue.enqueue(3);
System.out.println("Front element: " + queue.front()); // 1
System.out.println("Dequeued element: " + queue.dequeue()); // 1
System.out.println("Is queue empty? " + queue.isEmpty()); // false
}
}

=>Output:

Program 17
Implement a Queue Using Linked List: Write a
function to implement a queue using a linked
list with basic operations: enqueue, dequeue,
front, and isEmpty.
=>Program:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class QueueUsingLinkedList {
private Node front;
private Node rear;
public QueueUsingLinkedList() {
front = null;
rear = null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
public int dequeue() {
if (front == null) {
return -1;
}
int data = front.data;
front = front.next;
if (front == null) {
rear = null;
}
return data;
}
public int front() {
if (front == null) {
return -1;
}
return front.data;
}
public boolean isEmpty() {
return front == null;
 }
public static void main(String[] args) {
QueueUsingLinkedList queue = new QueueUsingLinkedList();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println("Front element: " + queue.front()); // 1
System.out.println("Dequeued element: " + queue.dequeue()); // 1
System.out.println("Is queue empty? " + queue.isEmpty()); // false
}
}

=>Output:

Program 18
Find the kth largest/smallest Element in an
Array:
Write a function to find the kth smallest or
largest element in an Array.
=>Program:
public class CircularQueue {
private int[] queue;
private int front, rear, size, capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
queue = new int[capacity];
front = rear = size = 0;
}
public void enqueue(int data) {
if (size == capacity) return;
queue[rear] = data;
rear = (rear + 1) % capacity;
size++;
}
public int dequeue() {
if (size == 0) return -1;
int data = queue[front];
front = (front + 1) % capacity;
size--;
return data;
}
public int front() {
return size == 0 ? -1 : queue[front];
}
public int rear() {
return size == 0 ? -1 : queue[(rear - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return size == 0;
 }
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
System.out.println(cq.front()); // 1
System.out.println(cq.dequeue()); // 1
System.out.println(cq.isEmpty()); // false
}
}

=>Output:

Program 19
Generate Binary Numbers from 1 to N: Write a
function to generate binary numbers from1 to
N using a queue.
=>Program:
import java.util.LinkedList;
import java.util.Queue;

public class BinaryNumbers {

public static void generateBinary(int N) {
Queue<String> queue = new LinkedList<>();
queue.add("1");
for (int i = 1; i <= N; i++) {
String binary = queue.poll();
System.out.println(binary);
queue.add(binary + "0");
queue.add(binary + "1");
}
}
public static void main(String[] args) {
generateBinary(5);
}
}
=>Output:

Program 20
Implement a Queue Using Stacks: Write a
function to implement a queue using two
stacks.
=>Program:
import java.util.Stack;
public class QueueUsingStacks {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public QueueUsingStacks() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void enqueue(int data) {
stack1.push(data);
}
public int dequeue() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int front() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean isEmpty() {
return stack1.isEmpty() && stack2.isEmpty();
}
public static void main(String[] args) {
QueueUsingStacks queue = new QueueUsingStacks();
queue.enqueue(1);
queue.enqueue(2);
 System.out.println("Front element: " + queue.front()); //
1
System.out.println("Dequeued element: " +
queue.dequeue()); // 1
System.out.println("Is queue empty? " + queue.isEmpty());
// false
}
}
=>Output:

Program 21
Implement a Binary Tree: Write a class to
implement a basic binary tree with insert,
delete, and traversal operations.
=>Program:
class Node {
int data; Node left, right;
Node(int item) { data = item; left = right = null; }
}
public class BinaryTree {
Node root;
public void insert(int data) { root = insertRec(root, data); }
private Node insertRec(Node root, int data) {
if (root == null) { root = new Node(data); return root; }
if (data < root.data) root.left = insertRec(root.left, data);
else if (data > root.data) root.right = insertRec(root.right, data);
return root;
}
public void delete(int data) { root = deleteRec(root, data); }
private Node deleteRec(Node root, int data) {
if (root == null) return root;
if (data < root.data) root.left = deleteRec(root.left, data);
else if (data > root.data) root.right = deleteRec(root.right, data);
else {
if (root.left == null) return root.right;
else if (root.right == null) return root.left;
root.data = minValue(root.right);
root.right = deleteRec(root.right, root.data);
}
return root;
}
private int minValue(Node root) {
int minv = root.data;
while (root.left != null) {
minv = root.left.data; root = root.left;
}
return minv;
}
public void inorder() { inorderRec(root); }
private void inorderRec(Node root) {
 if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(50); tree.insert(30); tree.insert(20);
tree.insert(40); tree.insert(70); tree.insert(60);
tree.insert(80); tree.inorder();
tree.delete(20); tree.inorder();
}
}

=>Output:

Program 22
Inorder Traversal: Write a function to perform
inorder traversal of a binary tree.
=>Program:
class Node {
int data; Node left, right;
Node(int item) { data = item; left = right = null;
}
}

public class BinaryTree {

Node root;
public void inorder() { inorderRec(root); }
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
 tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.inorder(); // Output: 4 2 5 1 3
}
}

=>Output:

Program 23
Preorder Traversal: Write a function to perform
preorder traversal of a binary tree.
=>Program:
class Node {
int data; Node left, right;
Node(int item) { data = item; left = right = null; }
}

public class BinaryTree {

Node root;

public void preorder() { preorderRec(root); }

private void preorderRec(Node root) {

if (root != null) {
System.out.print(root.data + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.print("Preorder Traversal: ");
 tree.preorder(); // Output: 1 2 4 5 3
}
}

=>Output:

Program 24
Postorder Traversal: Write a function to
perform postorder traversal of a binary tree.
=>Program:
class Node {
int data; Node left, right;
Node(int item) { data = item; left = right = null; }
}

public class BinaryTree {

Node root;

public void postorder() { postorderRec(root); }

private void postorderRec(Node root) {

if (root != null) {
postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.data + " ");
}
}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
 System.out.print("Postorder Traversal: ");
tree.postorder(); // Output: 4 5 2 3 1
}
}

=>Output:

Program 25
Level Order Traversal: Write a function to
perform level order traversal of a binary tree.
=>Program:
import java.util.LinkedList;
import java.util.Queue;

class Node {
int data; Node left, right;
Node(int item) { data = item; left = right = null; }
}

public class BinaryTree {

Node root;

public void levelOrder() { levelOrderRec(root); }

private void levelOrderRec(Node root) {

if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.print(current.data + " ");
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
 tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.print("Level Order Traversal: ");
tree.levelOrder(); // Output: 1 2 3 4 5
}
}
=>Output: