Operations performed in data structures generally depend on the type of data structure being used.
Here’s a general overview of common data structures and their typical operations:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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();
}
}