Data Structures in Java
A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. The way that data is organized and stored in a computer program's memory relies closely on Java record structures.
The Java standard library includes a significant number of built-in structures. A few of the record systems that permit programmers short and simple ways to save and arrange data include linked lists, stacks, queues, and arrays.
Developers can quickly perform operations like insertion, deletion, searching, and sorting because they provide a range of mechanisms for getting access to, altering, and managing data. Java programmers can reduce memory use and considerably boost the overall efficiency of their programs by using these data structures.
Types of Data Structures
There are the following two types of Data Structures:
- Primitive Data Structures
- Non-primitive Data Structures
1) Primitive Data Structures: It is also known as primitive data types; these are basic built-in data types in Java. They include:
- byte: Stores whole numbers from -128 to 127.
- short: Stores whole numbers from -32,768 to 32,767.
- int: Stores whole numbers from -2,147,483,648 to 2,147,483,647.
- float: Stores floating-point numbers with single precision.
- char: Stores individual characters.
- boolean: Stores true or false values.
- long: Stores large whole numbers.
- double: Stores floating-point numbers with double precision.
2) Non-primitive Data Structures: Non-primitive record structures are more complex and are composed of primitive data types. They may be, in addition, categorized into two types:
- Linear Data Structures: In linear data structures, the elements are arranged linearly or sequentially. Examples include:
- Arrays: A group of identically-typed elements placed in an array according to a predetermined arrangement.
- Stacks: A Last-In-First-Out (LIFO) structure in which only the topmost items may be added or removed.
- Queues: First-In-First-Out (FIFO) structures are utilized in queues, where items are inserted at the rear and taken out at the front.
- Linked List: A related list comprises a collection of gadgets referred to as nodes, each of which has a reference to the node after it and data within
- Non-linear Data Structures: In non-linear data structures, the elements are arranged in a non-sequential manner. Examples include:
- Trees: Trees are a type of node-based hierarchical structure, with a root node at the top and child nodes branching out of it. Examples include red-black trees, AVL trees, binary search trees, and binary trees.
- Graphs: A set of nodes linked by using edges, wherein nodes may have any quantity of connections. Graphs are used to symbolize complex relationships among items.
- Set: It is type of data structure that keeps a collection of unique elements. In other words, duplicate elements are not allowed in a set.
- Heap: A specialized tree-based structure in which every node has a value more or smaller than its kids, relying on whether or not it is a max heap or a min-heap.
- Hash Table: A hash table is a data structure that is used for keeping key-value pairs, thus allowing for very quick data insertion, retrieval, and deletion. It works with the help of a "hash function" for converting a key into a numerical index.
1) Arrays
An array is a collection of elements that have the same type. Elements of an array are arranged in contiguous memory allocation. In Java, arrays can be used to store primitive data types as well as objects. Arrays provide quick and easy access to elements.
In primitive data types, elements are stored in contiguous memory allocation, and in the case of objects, the object’s reference is stored in contiguous memory allocation. Arrays can be used to implement other data structures like queue, stack, and deque.
To read more Java Arrays
Example
import java.util.*;
public class Main
{
// main method
public static void main(String[] args)
{
int[] numbers = {10, 20, 30, 40, 50}; // Initialize an array of integers
System.out.println("Element at index 0: " + numbers[0]);
System.out.println("Element at index 2: " + numbers[2]);
System.out.println("Element at index 4: " + numbers[4]);
int sum = 0;
for (int i = 0; i < numbers.length; i++)
{
sum = sum + numbers[i];
}
System.out.println("Sum of array elements: " + sum);
numbers[2] = 35; // Updating an element in the array
System.out.println("Updated element at index 2: " + numbers[2]);
System.out.print("Elements of the array are: ");
for (int i = 0; i < numbers.length; i++)
{
System.out.print(numbers[i] + " ");
}
}
}
Output:
Element at index 0: 10 Element at index 2: 30 Element at index 4: 50 Sum of array elements: 150 Updated element at index 2: 35 Elements of the array are: 10 20 35 40 50
ArrayList
In Java, ArrayList is a dynamic data structure (resizable array) that allows for the storage and manipulation of elements. In contrast to a normal array, an ArrayList can grow its size when an element is added and can also reduce its size when an element is removed. It is part of the Java Collections Framework and is implemented using an array internally. ArrayList is present in the java.util package.
To read more Java ArrayList
Example
import java.util.*;
public class Main
{
// main mehtod
public static void main(String[] args)
{
// Create an ArrayList to store integers
ArrayList numbers=new ArrayList<>(List.of(10, 20, 30, 40, 50));
//Access and print elements from the ArrayList
System.out.println("Element at index 0: " + numbers.get(0));
System.out.println("Element at index 2: " + numbers.get(2));
System.out.println("Element at index 4: " + numbers.get(4));
// Updating an element in the ArrayList located at index 2
numbers.set(2, 35);
System.out.println("Updated element at index 2: " + numbers.get(2));
// Iterate through the ArrayList using a for-each loop and print the elements
System.out.print("Elements of the ArrayList are: ");
for (int i = 0; i < numbers.size(); i++)
{
System.out.print(numbers.get(i) + " ");
}
}
}
Output:
Element at index 0: 10 Element at index 2: 30 Element at index 4: 50 Updated element at index 2: 35 Elements of the ArrayList are: 10 20 35 40 50
2) Linked List
A linked list is a linear data structure that allows efficient deletion and insertion of elements as compared to arrays. In contrast to arrays, linked lists do not require contiguous memory allocation. Memory for each node of a linked list can be allocated independently, thus allowing dynamic memory allocation, which leads to efficient insertion and deletion operations. The individual items in a linked list are called nodes. Each node has two pieces of information: one is the value of the node, and the other is the link that connects to the next node. Note that accessing elements in a linked list is slower than in arrays. Similar to arrays, it can be used to implement other data structures like a queue, stack, and deque.
To read more Java LinkedList
Example
import java.util.*;
public class Main
{
// main method
public static void main(String[] args)
{
// Create a LinkedList to store integers
LinkedList linkedList1 = new LinkedList<>();
// Add elements to the LinkedList
linkedList1.add(10);
linkedList1.add(20);
linkedList1.add(30);
linkedList1.add(40);
linkedList1.add(50);
// Print the LinkedList
System.out.println("LinkedList: " + linkedList1);
// Remove an element from the LinkedList
linkedList1.removeFirst();
System.out.println("LinkedList after removing first element: " + linkedList1);
// Check if an element exists in the LinkedList
boolean containsElement=linkedList1.contains(30);
System.out.println("LinkedList contains element 30? " + containsElement);
// Get the first and last elements of the LinkedList
int firstElement = linkedList1.getFirst();
int lastElement = linkedList1.getLast();
System.out.println("First element: " + firstElement);
System.out.println("Last element: " + lastElement);
// Clear the LinkedList
linkedList1.clear();
System.out.println("LinkedList after clearing: " + linkedList1);
}
}
Output:
LinkedList: [10, 20, 30, 40, 50] LinkedList after removing first element: [20, 30, 40, 50] LinkedList contains element 30? true First element: 20 Last element: 50 LinkedList after clearing: []
3) Stack
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, i.e., the element that is most recently inserted is also the element that is removed first. It is thread-safe and synchronized. It has the push() method for adding elements and the pop() method for removing the top element from the stack. The peek() method is used for retrieving the top element of the stack. It is present in the java.util package.
To read more Java Stack
Example
import java.util.Stack;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a stack for storing integers
Stack stack = new Stack<>();
// Push elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Print the top element of the stack
System.out.println("Top element is: " + stack.peek());
// Pop elements from the stack
int poppedElement = stack.pop();
System.out.println("Popped element is: " + poppedElement);
// Check if the stack is empty
System.out.println("Is stack empty? " + stack.isEmpty());
// Get the size of the stack
System.out.println("Stack size is: " + stack.size());
// Iterate over the stack
System.out.print("Elements of the stack are: ");
for (Integer element:stack)
{
System.out.print(element + " ");
}
}
}
Output:
Top element is: 30 Popped element is: 30 Is stack empty? false Stack size is: 2 Elements of the stack are: 10 20
4) Queue
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, i.e., the element that is most recently inserted is also the element that is removed last. It represents a collection of elements where elements are inserted at the rear and removed from the front.
In Java, Queue is an interface and hence its direct instantiation is not possible. Classes like LinkedList or ArrayDeque implement the Queue interface. Queue interface as well as the class LinkedList or ArrayDeque is part of the java.util package.
To read more Java Queue
Example
import java.util.LinkedList;
import java.util.Queue;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a Queue for storing integers
Queue queue = new LinkedList<>();
// Enqueue elements to the Queue
queue.add(10);
queue.add(20);
queue.add(30);
queue.add(40);
queue.add(50);
// Access and print the front element of the Queue
System.out.println("The front element is: " + queue.peek());
// Dequeue elements from the Queue and print them
while (!queue.isEmpty())
{
int element = queue.poll();
System.out.println("The dequeued element is: " + element);
System.out.println("The front element is: " + queue.peek());
}
}
}
Output:
The front element is: 10 The dequeued element is: 10 The front element is: 20 The dequeued element is: 20 The front element is: 30 The dequeued element is: 30 The front element is: 40 The dequeued element is: 40 The front element is: 50 The dequeued element is: 50 The front element is: null
5) Map
In Java, a Map is an interface that is present in the java.util package that keeps data in key-value pairs, where each key present in the Map must be unique.
To read more Java Map Interface
Dictionary (HashMap): For storing data as key-value pairs in Java, a HashMap is used. It is part of the Java Collections Framework and is implemented based on the hash table data structure. Java HashMap is present in java.util package. It implements the Map interface.
To read more Java HashMap
Example
import java.util.HashMap;
public class Main
{
// main method
public static void main(String[] args) {
// Create a HashMap to store String keys and Integer values
HashMap hashMap = new HashMap<>();
// Add key-value pairs to the HashMap
hashMap.put("John", 25);
hashMap.put("Alice", 30);
hashMap.put("Bob", 35);
// Access and print values based on keys
System.out.println("Age of John is: " + hashMap.get("John"));
System.out.println("Age of Alice is: " + hashMap.get("Alice"));
// Check if a key exists in the HashMap
System.out.println("Is Bob present? " + hashMap.containsKey("Bob"));
// Update the value associated with a key
hashMap.put("Alice", 32);
// Remove a key-value pair from the HashMap
hashMap.remove("John");
// Print all key-value pairs in the HashMap
System.out.println("Key-Value pairs in the HashMap:");
for (String key : hashMap.keySet())
{ // displaying the key-value pair
System.out.println(key + ": " + hashMap.get(key));
}
// Check the size of the HashMap
System.out.println("The size of the HashMap is: " + hashMap.size());
}
}
Output:
Age of John is: 25 Age of Alice is: 30 Is Bob present? true Key-Value pairs in the HashMap: Bob: 35 Alice: 32 The size of the HashMap is: 2
TreeMap: TreeMap is a class in Java that implements the Map interface and provides a sorted key-value mapping based on the natural order of the keys or a custom comparator.
To read more Java TreeMap
Example
import java.util.TreeMap;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a TreeMap
TreeMap scores = new TreeMap<>();
// Inserting key-value pairs into the TreeMap
scores.put("Alice", 90);
scores.put("Bob", 80);
scores.put("Charlie", 95);
scores.put("David", 87);
scores.put("Eve", 92);
// Accessing and print values from the TreeMap
System.out.println("Score of Alice is: " + scores.get("Alice"));
System.out.println("Score of Charlie is: " + scores.get("Charlie"));
System.out.println("Score of David is: " + scores.get("David"));
// Updating a value in the TreeMap
scores.put("Bob", 85);
// Removing a key-value pair from the TreeMap
scores.remove("Eve");
// Iterating through the TreeMap using a for-each loop
System.out.println("Scores in the TreeMap are: ");
for (String name : scores.keySet())
{
int score = scores.get(name);
System.out.println(name + ": " + score);
}
}
}
Output:
Score of Alice is: 90 Score of Charlie is: 95 Score of David is: 87 Scores in the TreeMap are: Alice: 90 Bob: 85 Charlie: 95 David: 87
6) Set
In Java, a Set is an interface and is a collection where duplication of elements is not allowed. Classes such as LinkedHashSet, TreeSet, and HashSet implement the Set interface. Set interface is present in the java.util package.
To read more Java Set
HashSet: Implements hashing, where one can store keys in any order, but has quick insert, search, and delete operations.
To read more Java HashSet
Example
import java.util.HashSet;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a HashSet
HashSet set = new HashSet<>();
// Add elements to the HashSet
set.add("Apple");
set.add("Banana");
set.add("Orange");
set.add("Grapes");
set.add("Mango");
set.add("Apple"); // will not be added as “Apple is already added”
// Print the HashSet
System.out.println("The HashSet is: " + set);
// Check if an element exists
System.out.println("Does HashSet contain 'Apple'? " + set.contains("Apple"));
// Remove an element
set.remove("Banana");
// Print the updated HashSet
System.out.println("Updated HashSet is: " + set);
// Get the size of the HashSet
System.out.println("The size of the HashSet is: " + set.size());
// Clear the HashSet
set.clear();
// Check if the HashSet is empty
System.out.println("Is HashSet empty? " + set.isEmpty());
}
}
Output:
The HashSet is: [Apple, Grapes, Mango, Orange, Banana] Does HashSet contain 'Apple'? true Updated HashSet is: [Apple, Grapes, Mango, Orange] The size of the HashSet is: 4 Is HashSet empty? true
LinkedHashSet: It is similar to HashSet, where the order of insertion is maintained.
To read more Java LinkedHashSet
Example
import java.util.LinkedHashSet;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a LinkedHashSet
LinkedHashSet set = new LinkedHashSet<>();
// Add elements to the LinkedHashSet
set.add("Apple");
set.add("Banana");
set.add("Orange");
set.add("Grapes");
set.add("Mango");
set.add("Apple"); // will not be added as "Apple" is already added
// Print the LinkedHashSet
System.out.println("The LinkedHashSet is: " + set);
// Check if an element exists
System.out.println("Does LinkedHashSet contain 'Apple'? " + set.contains("Apple"));
// Remove an element
set.remove("Banana");
// Printing the updated LinkedHashSet
System.out.println("Updated LinkedHashSet is: " + set);
// Getting the size of the LinkedHashSet
System.out.println("The size of the LinkedHashSet is: " + set.size());
// Clear the LinkedHashSet
set.clear();
// Check if the LinkedHashSet is empty
System.out.println("Is LinkedHashSet empty? " + set.isEmpty());
}
}
Output:
The LinkedHashSet is: [Apple, Banana, Orange, Grapes, Mango] Does LinkedHashSet contain 'Apple'? true Updated LinkedHashSet is: [Apple, Orange, Grapes, Mango] The size of the LinkedHashSet is: 4 Is LinkedHashSet empty? true
TreeSet: TreeSet is an implementation of the SortedSet interface in Java that uses a self-balancing binary search tree called a red-black tree for keeping elements in sorted order. It takes moderate time for insertion, searching, and deletion.
To read more Java TreeSet
Example
import java.util.TreeSet;
public class Main
{
// main method
public static void main(String[] args)
{
// Creating a TreeSet
TreeSet numbers = new TreeSet<>();
// Add elements to the TreeSet
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(4);
// Print the TreeSet
System.out.println("Elements in the TreeSet are: " + numbers);
// Check if an element exists
System.out.println("Does TreeSet contain element 4? " + numbers.contains(4));
// Remove an element
numbers.remove(2);
// Print the TreeSet after removal
System.out.println("Elements in the TreeSet after removal: " + numbers);
// Get the size of the TreeSet
System.out.println("The size of the TreeSet is: " + numbers.size());
// Get the first and last element
System.out.println("The first element is: " + numbers.first());
System.out.println("The last element is: " + numbers.last());
// Iterating over the TreeSet
System.out.print("Iterating over the TreeSet: ");
for (int number : numbers)
{
System.out.print(number + " ");
}
}
}
Output:
Elements in the TreeSet are: [1, 2, 4, 5, 8] Does TreeSet contain element 4? true Elements in the TreeSet after removal: [1, 4, 5, 8] The size of the TreeSet is: 4 The first element is: 1 The last element is: 8 Iterating over the TreeSet: 1 4 5 8
7) Heap
A heap is a data structure where each node has two children (one is the left child and the other is the right child). It is of two types: one is a min-heap, and the other is a max-heap.
To read more Heap in Java
Min-heap: It is a binary heap where the parent node is always less than or equal to its child nodes. This property must hold true for every node present in the binary heap. Thus, the root node of the heap has the smallest value. A min heap is an example of a complete binary tree.
Example
// Min-heap implementation
import java.util.ArrayList;
class MinHeap {
private ArrayList heap;
// Constructor for initializing the heap
public MinHeap() {
heap = new ArrayList<>();
}
// A method for returning the parent node index
private int parentNodeIndex(int j) {
return (j - 1) / 2;
}
// A method for returning the left child node index
private int leftChildIndex(int j) {
return 2 * j + 1;
}
// A method for returning the right child node index
private int rightChildIndex(int j) {
return 2 * j + 2;
}
// A method for swapping the elements present at indices k and l
private void swapEle(int k, int l) {
int tmp = heap.get(k);
heap.set(k, heap.get(l));
heap.set(l, tmp);
}
// Inserting a new value into the heap
public void insertNode(int val) {
// Adding the new value at the end of the heap
heap.add(val);
// Getting the index of the newly added value
int currentIdx = heap.size() - 1;
// Bubbling up to restore heap property
while (currentIdx > 0 && heap.get(currentIdx) < heap.get(parentNodeIndex(currentIdx))) {
// Swapping with the parent if the current value is less
swapEle(currentIdx, parentNodeIndex(currentIdx));
// Moving up to the parent index
currentIdx = parentNodeIndex(currentIdx);
}
}
// A method that extracts and returns the min value from the min heap
public int extractMinVal() {
if (heap.isEmpty()) {
throw new RuntimeException("Heap is empty");
}
// at the root, the minimum value is present
int minVal = heap.get(0);
// Removing the last element
int lastElement = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
// Moving the last element to the root
// By doing this, the minimum element is removed from the heap.
heap.set(0, lastElement);
// Bubbling down for restoring the property of heap
int currIndex = 0;
while (true) {
int leftIdx = leftChildIndex(currIndex);
int rightIdx = rightChildIndex(currIndex);
int smallestVal = currIndex;
// Finding the smallest value among current, left child, and right child
if (leftIdx < heap.size() && heap.get(leftIdx) < heap.get(smallestVal)) {
smallestVal = leftIdx;
}
if (rightIdx < heap.size() && heap.get(rightIdx) < heap.get(smallestVal)) {
smallestVal = rightIdx;
}
if (smallestVal == currIndex) {
// Heap property is restored
break;
}
// Swapping with the smallest child
swapEle(currIndex, smallestVal);
// Moving down to the index of the smallest child
currIndex = smallestVal;
}
}
// Returning the minimum value
return minVal;
}
// Checks if the heap is empty
public boolean isEmpty() {
return heap.isEmpty();
}
}
public class Main {
// main method
public static void main(String[] args) {
// creating an object of MinHeap class
MinHeap minHeapObj = new MinHeap();
// Insert values into the min heap
minHeapObj.insertNode(101);
minHeapObj.insertNode(50);
minHeapObj.insertNode(105);
minHeapObj.insertNode(210);
minHeapObj.insertNode(250);
// Extract and print the minimum values from the heap
System.out.println("Extracted Min value is: " + minHeapObj.extractMinVal());
System.out.println("Extracted Min value is: " + minHeapObj.extractMinVal());
System.out.println("Extracted Min value is: " + minHeapObj.extractMinVal());
}
}
Output:
Extracted Min value is: 50 Extracted Min value is: 101 Extracted Min value is: 105
Max-heap: It is a binary heap where the parent node is always equal to or greater than its child nodes. This property must hold true for every node present in the binary heap. Thus, the root node of the heap has the largest value. A max heap is also an example of a complete binary tree.
Example
// Max-heap implementation
import java.util.ArrayList;
class MaxHeap {
private ArrayList heap;
// Constructor for initializing the heap
public MaxHeap() {
heap = new ArrayList<>();
}
// A method for returning the parent node index
private int parentNodeIndex(int j) {
return (j - 1) / 2;
}
// A method for returning the left child node index
private int leftChildIndex(int j) {
return 2 * j + 1;
}
// A method for returning the right child node index
private int rightChildIndex(int j) {
return 2 * j + 2;
}
// A method of swapping the elements present at indices k and l
private void swapEle(int k, int l) {
int tmp = heap.get(k);
heap.set(k, heap.get(l));
heap.set(l, tmp);
}
// Inserting a new value into the heap
public void insertNode(int val) {
// Adding the new value at the end of the heap
heap.add(val);
// Getting the index of the newly added value
int currentIdx = heap.size() - 1;
// Bubbling up to restore the max-heap property
while (currentIdx > 0 && heap.get(currentIdx) > heap.get(parentNodeIndex(currentIdx))) {
// Swapping with the parent if the current value is larger
swapEle(currentIdx, parentNodeIndex(currentIdx));
// Moving up to the parent index
currentIdx = parentNodeIndex(currentIdx);
}
}
// A method that extracts and returns the max value from the max heap
public int extractMaxVal() {
if (heap.isEmpty()) {
throw new RuntimeException("Heap is empty");
}
// at the root, the maximum value is present
int maxVal = heap.get(0);
// Removing the last element
int lastElement = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
// Moving the last element to the root
// By doing this, the maximum element present in the heap is removed
heap.set(0, lastElement);
// Bubble down for restoring the property of the max-heap
int currIndex = 0;
while (true) {
int leftIdx = leftChildIndex(currIndex);
int rightIdx = rightChildIndex(currIndex);
int largestVal = currIndex;
// Finding the largest value among current, left child, and right child
if (leftIdx < heap.size() && heap.get(leftIdx) > heap.get(largestVal)) {
largestVal = leftIdx;
}
if (rightIdx < heap.size() && heap.get(rightIdx) > heap.get(largestVal)) {
largestVal = rightIdx;
}
if (largestVal == currIndex) {
// Heap property is restored
break;
}
// Swapping with the largest child
swapEle(currIndex, largestVal);
// Moving down to the index of the largest child
currIndex = largestVal;
}
}
// Return the maximum value present in the heap
return maxVal;
}
// Checks if the heap is empty
public boolean isEmpty() {
return heap.isEmpty();
}
}
public class Main {
// main method
public static void main(String[] args) {
// creating an object of the max-heap class
MaxHeap maxHeapObj = new MaxHeap();
// Insert values into the max-heap
maxHeapObj.insertNode(101);
maxHeapObj.insertNode(50);
maxHeapObj.insertNode(105);
maxHeapObj.insertNode(210);
maxHeapObj.insertNode(250);
// Extract and print the max values from the heap
System.out.println("Extracted Max value is: " + maxHeapObj.extractMaxVal());
System.out.println("Extracted Min value is: " + maxHeapObj.extractMaxVal());
System.out.println("Extracted Min value is: " + maxHeapObj.extractMaxVal());
}
}
Output:
Extracted Max value is: 250 Extracted Min value is: 210 Extracted Min value is: 105
8) Graph
Graphs are a data structure that represents a collection of interconnected nodes or vertices. They are composed of vertices and edges, where vertices represent entities and edges represent the relationships between those entities.
To read more Graph in Java
Example
import java.util.*;
public class Main
{
private int V; // Number of vertices
private List> adjacencyList; // Adjacency list representation
public Main(int V)
{
this.V = V;
adjacencyList = new ArrayList<>(V); // creating adjacency list
// Initialize the adjacency list
for (int i = 0; i < V; i++)
{
adjacencyList.add(new ArrayList<>());
}
}
// Function to add an edge between two vertices
public void addEdge(int source, int destination)
{
adjacencyList.get(source).add(destination);
adjacencyList.get(destination).add(source);
}
// Function to perform Breadth-First Search traversal of the graph
public void bfs(int startVertex)
{
boolean[] visited = new boolean[V];
Queue queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (!queue.isEmpty())
{
int currentVertex = queue.poll();
System.out.print(currentVertex + " ");
List neighbors = adjacencyList.get(currentVertex);
for (int neighbor : neighbors)
{
if (!visited[neighbor])
{
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
// Function to perform Depth-First Search traversal of the graph
public void dfs(int startVertex)
{
boolean[] visited = new boolean[V];
dfsUtil(startVertex, visited);
System.out.println();
}
private void dfsUtil(int vertex,boolean[] visited)
{
visited[vertex] = true;
System.out.print(vertex + " ");
List neighbors = adjacencyList.get(vertex);
for (int neighbor : neighbors)
{
if (!visited[neighbor])
{
dfsUtil(neighbor, visited);
}
}
}
// main method
public static void main(String[] args)
{
int V = 5; // Number of vertices
Main graph = new Main(V);
// Add edges
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
System.out.print("BFS traversal is: ");
graph.bfs(0);
System.out.print("DFS traversal is: ");
graph.dfs(0);
}
}
Output:
BFS traversal is: 0 1 2 3 4 DFS traversal is: 0 1 3 2 4
9) Tree
A tree is a widely used data structure in computer science that represents a hierarchical structure. It consists of nodes connected by edges, where each node can have zero or more child nodes. Top node is considered the root node.
To read more Trees Data Structure
Example
import java.util.*;
class TreeNode {
int value;
TreeNode left;
TreeNode right;
// constructor of the class
public TreeNode(int value) {
this.value = value;
left = null;
right = null;
}
}
public class Main
{
// main method
public static void main(String[] args) {
// Create a binary search tree
TreeNode root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(80);
// Perform common operations
System.out.print("In-order Traversal is: ");
inOrderTraversal(root);
System.out.println("\nSearch for value 40: " + search(root, 40));
System.out.println("Search for value 90: " + search(root, 90));
int minValue = findMinValue(root);
System.out.println("Minimum value in the tree is: " + minValue);
int maxValue = findMaxValue(root);
System.out.println("Maximum value in the tree is: " + maxValue);
}
// In-order traversal: left subtree, root, right subtree
public static void inOrderTraversal(TreeNode node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}
// Search for a value in the tree
public static boolean search(TreeNode node, int value) {
if (node == null)
return false;
if (node.value == value)
return true;
if (value < node.value)
return search(node.left, value);
else
return search(node.right, value);
}
// Find the minimum value in the tree
public static int findMinValue(TreeNode node) {
if (node.left == null)
return node.value;
return findMinValue(node.left);
}
// Find the maximum value in the tree
public static int findMaxValue(TreeNode node) {
if (node.right == null)
return node.value;
return findMaxValue(node.right);
}
}
Output:
In-order Traversal is: 20 30 40 50 60 70 80 Search for value 40: true Search for value 90: false Minimum value in the tree is: 20 Maximum value in the tree is: 80
Advantages of Data Structures
- Efficient Data Organization: Data structures provide organized ways to store and manage data, allowing for efficient Access, manipulation, and retrieval operations. They optimize memory usage and facilitate faster execution of algorithms.
- Better Performance: Developers can improve performance in terms of speed and memory utilization by selecting the suitable data structure for a particular activity. Performance is optimized because specific data structures are made to excel at particular actions like searching, sorting, or inserting information.
- Code Reusability: Java offers a wide range of built-in data structures that are simple for programmers to use. These reusable data structures save time and effort by removing the need to create sophisticated algorithms from scratch.
- Code Simplicity: Data structures make the implementation of complicated processes simpler to code. They offer high-level abstractions and encapsulate the specifics of data management, which improves the code's readability, maintainability, and clarity.
- Flexibility and Adaptability: Data structures offer flexibility in handling different types and sizes of data. They can dynamically adjust to accommodate changing data requirements and provide mechanisms for efficient data manipulation.
- Standardized and Well-Tested: The standard library for Java contains built-in data structures that have undergone significant testing and optimization, guaranteeing their dependability and performance. Utilizing these common data structures lowers the possibility of errors and gives application development a solid foundation.
- Scalability: Data structures provide scalability options, allowing applications to handle large volumes of data efficiently. They can dynamically grow or shrink based on the data size, ensuring optimal performance even with increasing data demands.
- Algorithm Design: Data structures are crucial in algorithm design and analysis. They provide the underlying structure and operations necessary for implementing various algorithms and solving complex problems.
Subscribe to Tpoint Tech
We request you to subscribe our newsletter for upcoming updates.
We deliver comprehensive tutorials, interview question-answers, MCQs, study materials on leading programming languages and web technologies like Data Science, MEAN/MERN full stack development, Python, Java, C++, C, HTML, React, Angular, PHP and much more to support your learning and career growth.
Contact info
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Follow us
