Name: Simran kumari
Roll No: 22F-BSCS-172
Subject: DSA
LAB NO 2:
Lab Task 1: Implementing Singly Linked List :
Tasks:
1. Create a Node class to represent each element in the linked list.
2. Implement functions to add a node at the beginning, end, and a
specified position.
3. Implement functions to delete a node by value, by position, and
delete all nodes.
4. Write a function to reverse the linked list.
Ans) class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
class LinkedList {
Node head;
// Add node at the beginning
public void addAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
// Add node at the end
public void addAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
Node temp = head;
while (temp.next != null) {
temp = temp.next;
temp.next = newNode;
}
// Add node at a specific position
public void addAtPosition(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
addAtBeginning(data);
return;
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
if (temp == null) {
System.out.println("Position out of bounds");
return;
newNode.next = temp.next;
temp.next = newNode;
// Delete node by value
public void deleteByValue(int value) {
if (head == null) {
System.out.println("List is empty");
return;
if (head.data == value) {
head = head.next;
return;
Node temp = head;
while (temp.next != null && temp.next.data != value) {
temp = temp.next;
if (temp.next == null) {
System.out.println("Value not found");
return;
temp.next = temp.next.next;
// Delete node by position
public void deleteByPosition(int position) {
if (head == null) {
System.out.println("List is empty");
return;
if (position == 0) {
head = head.next;
return;
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
if (temp == null || temp.next == null) {
System.out.println("Position out of bounds");
return;
temp.next = temp.next.next;
// Delete all nodes
public void deleteAll() {
head = null;
// Reverse the linked list
public void reverse() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
head = prev;
// Display the linked list
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
System.out.println("null");
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.addAtBeginning(10);
list.addAtEnd(20);
list.addAtPosition(15, 1);
list.display(); // 10 -> 15 -> 20 -> null
list.deleteByValue(15);
list.display(); // 10 -> 20 -> null
list.addAtEnd(30);
list.display(); // 10 -> 20 -> 30 -> null
list.deleteByPosition(1);
list.display(); // 10 -> 30 -> null
list.reverse();
list.display(); // 30 -> 10 -> null
list.deleteAll();
list.display(); // null
}
Lab Task 2: Implementing a Stack using Linked List
Tasks:
1. Implement a stack using a singly linked list.
2. Implement push (to add an element), pop (to remove the top element), and peek (to view
the top element) operations.
3. Add an isEmpty function to check if the stack is empty.
4. Add a function to display all elements in the stack.
Ans) class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
class Stack {
private Node top; // Top of the stack
// Constructor to initialize the stack
public Stack() {
this.top = null;
}
// Check if the stack is empty
public boolean isEmpty() {
return top == null;
// Push operation to add an element
public void push(int data) {
Node newNode = new Node(data);
newNode.next = top;
top = newNode;
// Pop operation to remove the top element
public int pop() {
if (isEmpty()) {
System.out.println("Stack underflow! No element to pop.");
return -1;
int poppedData = top.data;
top = top.next;
return poppedData;
// Peek operation to view the top element
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty! No top element.");
return -1;
return top.data;
// Display all elements in the stack
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return;
Node temp = top;
System.out.println("Stack elements:");
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.display(); // Displays 30, 20, 10
System.out.println("Top element: " + stack.peek()); // 30
stack.pop(); // Removes 30
stack.display(); // Displays 20, 10
System.out.println("Top element after pop: " + stack.peek()); // 20
stack.pop();
stack.pop();
stack.display(); // Stack is empty
System.out.println("Is stack empty? " + stack.isEmpty()); // true
Lab Task 3: Application of Stack – Checking for Balanced
Parentheses
Task
1)Take a string of parentheses (like "( [ { } ] )") as input.
2) Implement a stack to check if the parentheses are balanced.
3) For instance, for an input of "({[]})", the output should confirm
balanced parentheses.
4)Provide informative output on whether the input string is
balanced or not.
Ans) import java.util.Stack;
public class BalancedParentheses {
// Method to check if the parentheses are balanced
public static boolean isBalanced(String expression) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char current = expression.charAt(i);
// Push opening brackets to the stack
if (current == '(' || current == '[' || current == '{') {
stack.push(current);
// Check for matching closing brackets
else if (current == ')' || current == ']' || current == '}') {
// If stack is empty, no matching opening bracket
if (stack.isEmpty()) {
return false;
char top = stack.pop();
if (!isMatchingPair(top, current)) {
return false;
}
// If stack is empty, all parentheses are balanced
return stack.isEmpty();
// Helper method to check if the characters form a matching pair
private static boolean isMatchingPair(char opening, char closing)
{
return (opening == '(' && closing == ')') ||
(opening == '[' && closing == ']') ||
(opening == '{' && closing == '}');
public static void main(String[] args) {
String input1 = "({[]})";
String input2 = "([)]";
String input3 = "{[()]}";
String input4 = "{[(])}";
System.out.println("Input: " + input1 + " -> " +
(isBalanced(input1) ? "Balanced" : "Not Balanced"));
System.out.println("Input: " + input2 + " -> " +
(isBalanced(input2) ? "Balanced" : "Not Balanced"));
System.out.println("Input: " + input3 + " -> " +
(isBalanced(input3) ? "Balanced" : "Not Balanced"));
System.out.println("Input: " + input4 + " -> " +
(isBalanced(input4) ? "Balanced" : "Not Balanced"));
}
Lab Task 4: Circular Linked List Implementation
Task
1)Create a Node class and a CircularLinkedList class.
2)Implement functions to add nodes at the beginning and end of the
list.
3) Implement a function to traverse the list and print all elements,
showing the circular nature of the list.
4)Write a method to delete a node from the list.
Ans) class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
class CircularLinkedList {
private Node tail;
// Constructor to initialize the circular linked list
public CircularLinkedList() {
this.tail = null;
// Add a node at the beginning
public void addAtBeginning(int data) {
Node newNode = new Node(data);
if (tail == null) {
tail = newNode;
tail.next = newNode; // Point to itself to form a circular
structure
} else {
newNode.next = tail.next;
tail.next = newNode;
// Add a node at the end
public void addAtEnd(int data) {
Node newNode = new Node(data);
if (tail == null) {
tail = newNode;
tail.next = newNode; // Point to itself to form a circular
structure
} else {
newNode.next = tail.next;
tail.next = newNode;
tail = newNode; // Update the tail to the new node
// Traverse and display the circular linked list
public void traverse() {
if (tail == null) {
System.out.println("The list is empty.");
return;
Node current = tail.next; // Start from the head
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != tail.next);
System.out.println("(back to head)");
}
// Delete a node by value
public void delete(int value) {
if (tail == null) {
System.out.println("The list is empty. No node to delete.");
return;
Node current = tail.next;
Node previous = tail;
// Find the node to delete
do {
if (current.data == value) {
if (current == tail.next) { // Deleting the head node
tail.next = current.next;
} else if (current == tail) { // Deleting the tail node
previous.next = current.next;
tail = previous;
} else { // Deleting a middle node
previous.next = current.next;
System.out.println("Node with value " + value + "
deleted.");
return;
previous = current;
current = current.next;
} while (current != tail.next);
System.out.println("Node with value " + value + " not found.");
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.addAtBeginning(10);
list.addAtEnd(20);
list.addAtEnd(30);
list.addAtBeginning(5);
list.traverse(); // 5 -> 10 -> 20 -> 30 -> (back to head)
list.delete(10);
list.traverse(); // 5 -> 20 -> 30 -> (back to head)
list.delete(30);
list.traverse(); // 5 -> 20 -> (back to head)
list.delete(5);
list.traverse(); // 20 -> (back to head)
list.delete(20);
list.traverse(); // The list is empty.
Lab Task 5: Implement a Stack with Dynamic Size
Tasks:
1. Implement a stack using an array with an initial size, say 10.
2. If the stack reaches its capacity, double the array size to
accommodate more
elements.
3. Implement push, pop, and peek methods along with the resizing
logic.
Ans) class DynamicStack {
private int[] stack;
private int top;
private int capacity;
// Constructor to initialize the stack
public DynamicStack(int initialCapacity) {
this.capacity = initialCapacity;
this.stack = new int[capacity];
this.top = -1;
}
// Push method to add an element to the stack
public void push(int data) {
if (top == capacity - 1) {
resize(); // Double the stack size when capacity is reached
stack[++top] = data;
// Pop method to remove the top element
public int pop() {
if (isEmpty()) {
System.out.println("Stack underflow! No element to pop.");
return -1;
return stack[top--];
// Peek method to view the top element
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty! No top element.");
return -1;
return stack[top];
// Check if the stack is empty
public boolean isEmpty() {
return top == -1;
// Resize method to double the size of the stack
private void resize() {
int newCapacity = capacity * 2;
int[] newStack = new int[newCapacity];
// Copy elements to the new stack
for (int i = 0; i < capacity; i++) {
newStack[i] = stack[i];
capacity = newCapacity;
stack = newStack;
System.out.println("Stack resized to: " + newCapacity);
}
// Display all elements in the stack
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return;
System.out.println("Stack elements:");
for (int i = 0; i <= top; i++) {
System.out.print(stack[i] + " ");
System.out.println();
public static void main(String[] args) {
DynamicStack stack = new DynamicStack(10);
// Push elements
for (int i = 1; i <= 15; i++) {
stack.push(i);
stack.display(); // Display stack elements
System.out.println("Top element: " + stack.peek()); // Peek top
element
stack.pop(); // Remove top element
stack.display(); // Display stack after pop
System.out.println("Top element after pop: " + stack.peek());
