Data Structures and Algorithms (DSA) are the building blocks of computer programming. They help in organizing and processing data efficiently. In this article, we will explore some fundamental DSA constructs using Java, a popular object-oriented programming language. We will keep the language simple and the examples relatable, so even a 15-year-old can understand!
Table of Contents
Data Structures in Java
Arrays
An array is a basic data structure that stores elements of the same type in a contiguous block of memory. In Java, arrays are objects.
int[] arr = new int[5]; // Declare an array of integers
arr[0] = 1; // Assign value to the first elementArrayList
ArrayList is a part of the Java Collection Framework. It is a dynamic array, meaning its size can be changed dynamically.
ArrayList<Integer> arrList = new ArrayList<Integer>(); // Declare an ArrayList
arrList.add(1); // Add an elementLinkedList
A LinkedList consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
LinkedList<String> linkedList = new LinkedList<String>(); // Declare a LinkedList
linkedList.add("Data"); // Add an elementAlgorithms in Java
Sorting Algorithms
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.
void selectionSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}Searching Algorithms
Linear Search
Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one.
int search(int arr[], int x) {
int n = arr.length;
for(int i = 0; i < n; i++) {
if(arr[i] == x)
return i;
}
return -1;
}Binary Search
Binary Search: Search a sorted array by repeatedly dividing the search interval in half.
int binarySearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}Advanced Data Structures in Java
Stacks
A Stack is a linear data structure that follows the LIFO (Last In First Out) principle. It has two main operations: push (insert element) and pop (remove element).
Stack<Integer> stack = new Stack<Integer>();
stack.push(1); // Pushes 1 onto the stack
stack.pop(); // Removes the top elementQueues
A Queue is a linear data structure that follows the FIFO (First In First Out) principle. It has two main operations: enqueue (add element) and dequeue (remove element).
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1); // Adds 1 to the queue
queue.remove(); // Removes the front elementAdvanced Algorithms in Java
Graph Algorithms
Depth-First Search (DFS)
DFS is an algorithm for traversing or searching tree or graph data structures. It uses a stack data structure.
void DFS(int v, boolean visited[], LinkedList<Integer> adj[]) {
visited[v] = true;
System.out.print(v + " ");
for (Integer i : adj[v]) {
if (!visited[i])
DFS(i, visited, adj);
}
}Breadth-First Search (BFS)
BFS is an algorithm for traversing or searching tree or graph data structures. It uses a queue data structure.
void BFS(int s, LinkedList<Integer> adj[], boolean visited[]) {
Queue<Integer> queue = new LinkedList<Integer>();
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
s = queue.poll();
System.out.print(s + " ");
for (Integer i : adj[s]) {
if (!visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
}Trees in Java
A Tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node.
Binary Tree
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}Binary Search Tree (BST)
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
- The left sub-tree of a node has a key less than its parent node’s key.
- The right sub-tree of a node has a key greater than its parent node’s key.
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BST {
Node root;
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
}Graphs in Java
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.
class Graph {
private int numVertices;
private LinkedList<Integer> adjLists[];
Graph(int vertices) {
numVertices = vertices;
adjLists = new LinkedList[vertices];
for (int i = 0; i < vertices; i++)
adjLists[i] = new LinkedList();
}
void addEdge(int src, int dest) {
adjLists[src].add(dest);
}
}Table outlining some common constructs used in the DSA (Data Structures and Algorithms) implemented in Java:
| Construct | Description | Example |
|---|---|---|
| Arrays | Collection of elements stored in contiguous memory locations, accessed by index. | int[] arr = new int[5]; |
| Linked Lists | Linear data structure where elements are stored in nodes, each node pointing to the next. | LinkedList<Integer> list = new LinkedList<>(); |
| Stacks | LIFO (Last In First Out) data structure where elements are inserted and removed from the same end. | Stack<Integer> stack = new Stack<>(); |
| Queues | FIFO (First In First Out) data structure where elements are inserted at the rear and removed from the front. | Queue<Integer> queue = new LinkedList<>(); |
| Trees | Hierarchical data structure consisting of nodes, with each node having zero or more children nodes. | BinarySearchTree<Integer> bst = new BinarySearchTree<>(); |
| Graphs | Non-linear data structure consisting of nodes (vertices) and edges connecting these nodes. | Graph graph = new Graph(5); |
| Hash Tables | Data structure that implements an associative array abstract data type, mapping keys to values. | HashMap<String, Integer> map = new HashMap<>(); |
| Sorting Algorithms | Algorithms that arrange elements in a specific order, such as ascending or descending. | Arrays.sort(arr); |
| Searching Algorithms | Algorithms that find an element within a data structure. | int index = Arrays.binarySearch(arr, key); |
| Recursion | Technique where a function calls itself directly or indirectly, allowing solutions to be defined in terms of simpler instances. | public int factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); } |
| Dynamic Programming | Technique used to solve problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computations. | int fib(int n) { int[] dp = new int[n+1]; ... } |
Conclusion
Understanding Data Structures and Algorithms (DSA) is crucial for coding and problem-solving in computer science. Java, with its versatile and object-oriented approach, provides a great platform to learn and implement DSA. Remember, the key to mastering DSA is practice. So, keep coding and exploring new constructs!
