Data Structure & Algorithm in Java

⌘K
  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Introduction to Data Stru...
  5. Operations Performed in Data Structure

Operations Performed in Data Structure

  1. Arrays:
    • Access: Retrieve the value at a specific index.
    • Insertion: Add an element at the end or a specific index.
    • Deletion: Remove an element from a specific index.
    • Search: Find the index of a specific value.
  2. Linked Lists:
    • Insertion: Add a node at the beginning, end, or at a specific position.
    • Deletion: Remove a node from the beginning, end, or a specific position.
    • Traversal: Visit each node sequentially.
    • Search: Find a node with a specific value.
  3. Stacks:
    • Push: Add an element to the top of the stack.
    • Pop: Remove and return the top element from the stack.
    • Peek: View the top element without removing it.
    • isEmpty: Check if the stack is empty.
  4. Queues:
    • Enqueue: Add an element to the rear of the queue.
    • Dequeue: Remove and return the front element from the queue.
    • Peek: View the front element without removing it.
    • isEmpty: Check if the queue is empty.
  5. Trees:
    • Insertion: Add a node to the tree.
    • Deletion: Remove a node from the tree.
    • Traversal: Visit each node in a specific order (e.g., inorder, preorder, postorder).
    • Searching: Find a specific node in the tree.
  6. Graphs:
    • Insertion: Add a vertex or an edge to the graph.
    • Deletion: Remove a vertex or an edge from the graph.
    • Traversal: Visit each vertex and edge in the graph (e.g., breadth-first search, depth-first search).
    • Shortest Path: Find the shortest path between two vertices.
    • Connectivity: Check if two vertices are connected.
  7. Hash Tables:
    • Insertion: Add a key-value pair to the hash table.
    • Deletion: Remove a key-value pair from the hash table.
    • Search: Find the value associated with a given key.
    • Collision Handling: Resolve collisions that occur when multiple keys hash to the same index.

Operations on different Data Structure: 
There are different types of operations that can be performed for the manipulation of data in every data structure. Some operations are explained and illustrated below: 

  • Traversing: Traversing a Data Structure means to visit the element stored in it. It visits data in a systematic manner. This can be done with any type of DS. 

Below is the program to illustrate traversal in an array, stack, queue and LinkedList:

Array:

public class ArrayTraversal {
    public static void main(String[] args) {
        // Sample array
        int[] array = {1, 2, 3, 4, 5};

        // Traversing the array using a for loop
        System.out.println("Traversing the array using a for loop:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(); // Just for formatting
    }
}

Stack:

import java.util.Stack;

public class StackTraversal {
    public static void main(String[] args) {
        // Create a stack
        Stack<Integer> stack = new Stack<>();

        // Push elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        // Print stack elements using traversal
        System.out.println("Stack elements:");
        traverseStack(stack);
    }

    // Traversal function to print stack elements without modifying the stack
    public static void traverseStack(Stack<Integer> stack) {
        // Create a temporary stack to store elements while traversing
        Stack<Integer> tempStack = new Stack<>();

        // Copy elements from the original stack to the temporary stack
        while (!stack.isEmpty()) {
            int element = stack.pop();
            System.out.println(element); // Print the element
            tempStack.push(element); // Push the element to the temporary stack
        }

        // Restore elements back to the original stack from the temporary stack
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }
}

Queue:

import java.util.LinkedList;
import java.util.Queue;

public class QueueTraversal {
    public static void main(String[] args) {
        // Create a queue
        Queue<Integer> queue = new LinkedList<>();

        // Add elements to the queue
        queue.add(10);
        queue.add(20);
        queue.add(30);
        queue.add(40);
        queue.add(50);

        // Traverse the queue and print its elements
        System.out.println("Queue elements:");
        for (Integer element : queue) {
            System.out.println(element);
        }
    }
}

LinkedList:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to insert a new node at the end of the linked list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Method to traverse the linked list and print its elements
    public void traverse() {
        Node current = head;
        System.out.print("Linked List: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // Inserting elements into the linked list
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        
        // Traversing and printing the linked list
        list.traverse();
    }
}
  • Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the required element is added to the required data-structure. It is unsuccessful in some cases when the size of the data structure is full and when there is no space in the data-structure to add any additional element. The insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In stack, this operation is called Push. In the queue, this operation is called Enqueue.

Below is the program to illustrate insertion in array, stack, queue and LinkedList :

Array:

public class ArrayInsertion {
    public static void main(String[] args) {
        // Sample array
        int[] array = {1, 2, 3, 4, 5};
        
        // Element to be inserted and its position
        int elementToInsert = 10;
        int position = 2; // Insert at index 2 (third position)
        
        // Print the original array
        System.out.println("Original Array:");
        printArray(array);
        
        // Inserting the element into the array
        array = insertIntoArray(array, elementToInsert, position);
        
        // Print the array after insertion
        System.out.println("\nArray after insertion:");
        printArray(array);
    }
    
    // Method to insert an element into an array at a specified position
    public static int[] insertIntoArray(int[] array, int element, int position) {
        // Create a new array with increased size to accommodate the new element
        int[] newArray = new int[array.length + 1];
        
        // Copy elements from the original array to the new array until the position
        for (int i = 0; i < position; i++) {
            newArray[i] = array[i];
        }
        
        // Insert the new element at the specified position
        newArray[position] = element;
        
        // Copy the remaining elements from the original array to the new array
        for (int i = position + 1; i < newArray.length; i++) {
            newArray[i] = array[i - 1];
        }
        
        return newArray;
    }
    
    // Method to print an array
    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(); // Just for formatting
    }
}

Stack:

public class StackInsertion {
    private int maxSize; // Maximum size of the stack
    private int[] stackArray; // Array to hold the stack elements
    private int top; // Index indicating the top of the stack

    // Constructor to initialize the stack
    public StackInsertion(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // Initialize top as -1 to indicate an empty stack
    }

    // Method to push an element onto the stack
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack Overflow! Cannot push element " + value + ".");
            return;
        }
        stackArray[++top] = value; // Increment top and insert the element
        System.out.println("Pushed element " + value + " onto the stack.");
    }

    // Method to check if the stack is full
    public boolean isFull() {
        return (top == maxSize - 1);
    }

    public static void main(String[] args) {
        int stackSize = 5; // Define the size of the stack
        StackInsertion stack = new StackInsertion(stackSize);

        // Push elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        stack.push(60); // This will cause a stack overflow
    }
}

Queue:

// Node class to represent elements in the queue
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Queue class implementing insertion operation
class Queue {
    private Node front;
    private Node rear;

    public Queue() {
        this.front = null;
        this.rear = null;
    }

    // Method to check if the queue is empty
    public boolean isEmpty() {
        return front == null;
    }

    // Method to insert (enqueue) an element into the queue
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        System.out.println("Inserted " + data + " into the queue");
    }

    // Method to display the elements in the queue
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        System.out.println("Elements in the queue:");
        Node current = front;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// Main class to test the Queue implementation
public class QueueInsertion {
    public static void main(String[] args) {
        Queue queue = new Queue();
        
        // Inserting elements into the queue
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        
        // Displaying the elements in the queue
        queue.display();
    }
}

LinkedList:

import java.util.LinkedList;

public class LinkedListInsertion {
    public static void main(String[] args) {
        // Creating a LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // Adding elements to the LinkedList
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Orange");

        // Displaying the original list
        System.out.println("Original LinkedList: " + linkedList);

        // Inserting an element at the beginning of the list
        linkedList.addFirst("Grapes");

        // Inserting an element at the end of the list
        linkedList.addLast("Pineapple");

        // Inserting an element at a specific position
        linkedList.add(2, "Mango");

        // Displaying the updated list
        System.out.println("LinkedList after insertion: " + linkedList);
    }
}
  • Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an element in the given data structure. The operation of deletion is successful when the required element is deleted from the data structure. The deletion has the same name as a deletion in the data-structure as an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is called Dequeue.

Below is the program to illustrate dequeue in Stack, Queue and LinkedList:

Stack:

import java.util.*;

public class StackDeletion {
    public static void main(String[] args) {
        // Create a stack using Java's built-in Stack class
        Stack<Integer> stack = new Stack<>();
        
        // Push some elements onto the stack
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        
        // Print the stack before deletion
        System.out.println("Stack before deletion: " + stack);
        
        // Perform deletion (pop operation)
        int deletedElement = stack.pop();
        
        // Print the element deleted from the stack
        System.out.println("Element deleted from the stack: " + deletedElement);
        
        // Print the stack after deletion
        System.out.println("Stack after deletion: " + stack);
    }
}

Queue:

import java.util.LinkedList;
import java.util.Queue;

public class QueueDeletion {
    public static void main(String[] args) {
        // Create a queue
        Queue<Integer> queue = new LinkedList<>();

        // Add elements to the queue
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        queue.offer(40);
        queue.offer(50);

        // Print the original queue
        System.out.println("Original Queue: " + queue);

        // Delete an element from the queue (perform dequeue operation)
        int deletedElement = queue.poll();

        // Print the deleted element
        System.out.println("Deleted Element: " + deletedElement);

        // Print the queue after deletion
        System.out.println("Queue after deletion: " + queue);
    }
}

LinkedList:

class LinkedList {
    Node head;

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // Method to insert a new node at the end of the linked list
    public void append(int new_data) {
        Node new_node = new Node(new_data);

        if (head == null) {
            head = new_node;
            return;
        }

        Node last = head;
        while (last.next != null) {
            last = last.next;
        }

        last.next = new_node;
    }

    // Method to delete a node with given key from linked list
    public void deleteNode(int key) {
        Node temp = head, prev = null;

        // If head node itself holds the key to be deleted
        if (temp != null && temp.data == key) {
            head = temp.next; // Changed head
            return;
        }

        // Search for the key to be deleted, keep track of the previous node as we need to change 'prev.next'
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }

        // If key was not present in linked list
        if (temp == null) {
            return;
        }

        // Unlink the node from linked list
        prev.next = temp.next;
    }

    // Method to print the linked list
    public void printList() {
        Node currNode = head;
        System.out.print("LinkedList: ");

        while (currNode != null) {
            System.out.print(currNode.data + " ");
            currNode = currNode.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        linkedList.append(5);

        System.out.println("Original LinkedList:");
        linkedList.printList();

        // Deleting node with value 3
        linkedList.deleteNode(3);

        System.out.println("\nLinkedList after deletion of node with value 3:");
        linkedList.printList();
    }
}

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *