Data Structures and Algorithms: A Java Cheatsheet
Learn the essentials of data structures, searching, and sorting algorithms in Java with this cheatsheet for quick reference.
1. Data structures
Data structures in Java are specialized formats for organizing and storing data, and some common examples include lists, maps, sets, trees, and queues.[1]
- Lists allow ordered access and manipulation of data, often implemented with ArrayList or LinkedList.[1]
- Maps store data as key-value pairs, where each key is unique and used to retrieve its corresponding value. Examples include HashMap and TreeMap.[1]
- Sets are used to store unique elements, without duplicates. HashSet and TreeSet are examples of set data structures.[1]
- Trees are hierarchical data structures, often used for sorting or organizing data in a specific order, with examples such as Binary Search Tree and Red-Black Tree.[1]
- Queues are a data structure that allows adding elements at the back and removing them from the front in a FIFO (First-In, First-Out) order, with examples including LinkedList and PriorityQueue.[1]
Following are the data structures in java[1]:
1.1 Queue
In Java, the queue is an interface with implementations such as PriorityQueue (each item has a predefined priority), LinkedList (useful when adding or deleting nodes), ArrayDeque (Array Double-Ended Queue), and PriorityBlockingQueue (synchronized).[2]
class PriorityQueueExample{
public static void main(String args[])
{
// Creating empty priority queue
PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
// Adding items to the pQueue using add()
pQueue.add(10);
pQueue.add(20);
pQueue.add(15);
// Printing the top element of PriorityQueue
System.out.println(pQueue.peek());
// Printing the top element and removing it
// from the PriorityQueue container
System.out.println(pQueue.poll());
// Printing the top element again
System.out.println(pQueue.peek());
}
}1.2 List
ArrayList (array with preset methods), LinkedList, Vector (legacy synchronized array list), and Stack are concrete classes that implement the List interface.[3]
public class StackExample{
public static void main (String[] args){
Stack<String> stack = new Stack<String>();
stack.push("BMW");
stack.push("Audi");
stack.push("Ferrari");
stack.push("Bugatti");
stack.push("Jaguar");
stack.pop();
if(stack.isEmpty() == false){
System.out.println("The length of the array: "+ stack.search(stack.peek()));
}
Iterator iterator = stack.iterator();
while(iterator.hasNext()){
Object values = iterator.next();
System.out.println(values);
}
}
}1.3 Map
LinkedHashMap is similar to HashMap, except it stores the order, whereas Hashtable is synchronized (many threads can use it), making it the slower form of HashMap.[4]
1.4 Set
HashSet and LinkedHashSet are implementations of the set, which is a data structure interface that stores different values (a HashSet that has order).[5]
public class Main {
public static void main(String[] args) {
HashSet<String> cars = new HashSet<String>();
cars.add("Volvo");
cars.add("BMW");
cars.add("Ford");
cars.add("BMW");
cars.add("Mazda");
cars.contains("Mazda");
cars.remove("Volvo");
cars.clear();
}
}HashMap vs HashSet
The Map interface is implemented by Hashmap. HashSet, on the other hand, is the set interface’s implementation. For its implementation, HashMap does not use HashSet or any other set. TheHashSet’s internal implementation is based on Hashmap. The HashSet stores solely values and not key-value pairs. The HashMap modifies the key’s value when a value with an already existing key is attempted to be added, however, the HashSet does not allow you to insert an already existing element.[6]
1.6 Tree
A tree is a non-linear data structure that organizes data elements in terms of hierarchical relationships. [7][8]
// Binary tree node example
// Class containing left and right child
// of current node and key value
class Node {
int key;
Node left, right;
public Node(int item){
key = item;
left = right = null;
}
}2. Big O notation/ complexity
While deciding between algorithms, we employ parameters, and one of them is complexity. The most significant two types of complexity are time and space complexity. Because each piece of computer hardware is unique, we utilize broad notations to characterize complexity. An algorithm can be completed in an instant or it can take n time, where n is the input. Big O notation is a popular notation for describing the worst time complexity.[9]
2.1 Complexity comparison where n is the input size
O(n!) (factorial)[Terrible] >
O(2^n) (exponential(increment rate increases to endless))[Terrible] >
O(n^p) (polynomial)[Terrible] >
O(n*logn) (log-linear) [Bad] >
O(n) (linear) [Fair] >
O(logn) (logarithmic(increment rate decreases to zero)) [Good] >
O(1) (constant) [Perfect]
While examining the difficulty of an algorithm, we round the complexity because the greatest value defines the majority of the performance; for example, O(n2+ n + 1) is accepted as O(n2). If the complexity is O(n+m) and both values are changeable by variables, we do not round the complexity to O(n+m).[9]
2.2 Time Complexity
In general, the algorithm’s looping time is counted. Recursive complexity is used to explain recursive algorithms.[9]
2.3 Space Complexity
The element count of the utilized collection plus auxiliary space is counted.[9]
3. Searching Algorithms
There are 3 fundamental search algorithms[9]:
3.1 Sequential Search
Simple to implement, but slow to work. Each data set is examined individually by the algorithm. It has an O(N) complexity, where N is the number of data. Also, the data structure must be pre-sorted by a key.[9]
public int selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++){
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return smallerNumber;
} 3.2 Binary Search
The most widely used search algorithm. The algorithm examines the data in the center and searches for higher or smaller values based on the position of the value in relation to the median value. It has the formula O(log 2(N)). Also, the data structure must be pre-sorted by a key. [9]
public void binarySearch(int arr[], int searched)
{
int low = 0, high = arr.length - 1;
// This below check covers all cases , so need to check
// for mid=lo-(high-low)/2
while (high - low > 1) {
int mid = (high + low) / 2;
if (arr[mid] < searched) {
low = mid + 1;
}
else {
high = mid;
}
}
if (arr[low] == searched) {
System.out.println("Found At Index " + low );
}
else if arr[high] == searched) {
System.out.println("Found At Index " + hi );
}
else {
System.out.println("Not Found" );
}
}3.3 Hash Search
Hashing is the process of assigning a numeric or alphanumeric string to a piece of data by using a function whose output values are all the same length in bits. In the ideal case, the fastest search algorithm has an O(1) complexity. It is inefficient if there are a lot of collisions, and collisions aren’t avoided if there are a lot of keys.[9]
public void findingFrequencyWithHashMap(int arr[])
{
// Creates an empty HashMap
HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
// Traverse through the given array
for (int i = 0; i < arr.length; i++) {
// Get if the element is present
Integer c = hmap.get(arr[i]);
// If this is first occurrence of element
// Insert the element
if (hmap.get(arr[i]) == null) {
hmap.put(arr[i], 1);
}
// If elements already exists in hash map
// Increment the count of element by 1
else {
hmap.put(arr[i], ++c);
}
}
// Print HashMap
System.out.println(hmap);
}4 Sorting
4.1 Selection sort
When the data is half-sorted, this is useful. The time complexity is O(n2), and the space complexity is O(1). It starts with an empty array, then searches for the smallest values and keeps adding them to it. [10]
public int[] selectionSort(int arr[]){
int index , smallest;
int lastIndex= arr.length()- 1;
for(int i = 1; i < lastIndex; i++){ //Starts from the beginning
smallest = arr[lastIndex]; //Last element accepted as the smallest
index = lastIndex;
for(int j = i; j < lastIndex; j++){ //Search for the smaller
if(arr[j] < smallest){
smallest = D[j];
index = j;
}
arr[index] = arr[i]; //If there is a smaller one relocate
arr[i] = smallest;
}
}
return arr;
}4.2 Bubble sort
If the elements are sorted and the number of elements is small, this algorithm is better. This algorithm has an O(n²) time complexity and an O(1) space complexity. If all c elements are not sorted, the temporal complexity is O(c*n). This algorithm sequentially ranks each neighboring element among itself. [11]
public static void bubbleSort(int [] arr){
int lastIndex = arr.length()-1;
for (int i=0; i<lastIndex; i++){
for(int j=0; j<lastIndex-i; j++){
if(arr[j+1] < arr[j]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}Selection Sort vs Bubble Sort
Both have the same time and space complexity, but Selection Sort executes fewer swaps than Bubble Sort; thus, Selection Sort is faster and more efficient.
4.3 Insertion sort
This algorithm sorts an array of objects by inserting elements from the unsorted portion of the array into their respective location in the sorted portion of the array on a continuous basis. The complexity of time is O(n2), but the complexity of space is O(1). [12]
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}4.5 Merge sort
The space complexity is O(n log(n)) while the time complexity is O(n). Merge sort is a sorting method that divides an array into smaller subarrays, sorts each subarray, and then merges the sorted subarrays to generate the final sorted array. Simple to build, faster with larger data sets. Verbose, takes up more space and is slow with tiny data sets as compared to other techniques. [13]
void merge(int arr[], int left, int mid, int right)
{
// Find sizes of two subarrays to be merged
int size1 = mid - left + 1;
int size2 = right - mid;
/* Create temp arrays */
int Left[] = new int[size1];
int Right[] = new int[size2];
/*Copy data to temp arrays*/
for (int i = 0; i < size1; ++i){
Left[i] = arr[left + i];
}
for (int j = 0; j < size2; ++j){
Right[j] = arr[mid + 1 + j];
}
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int mergedArrIndex = left;
while (i < size1 && j < size2) {
if (Left[i] <= Right[j]) {
arr[mergedArrIndex] = Left[i];
i++;
}
else {
arr[mergedArrIndex] = Right[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < size1) {
arr[mergedArrIndex] = Left[i];
i++;
mergedArrIndex++;
}
/* Copy remaining elements of R[] if any */
while (j < size2) {
arr[mergedArrIndex] = Right[j];
j++;
mergedArrIndex++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int left, int right)
{
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Sort first and second halves
sort(arr, left, mid);
sort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}4.6 Quick sort
The space complexity is O(n²) and the time complexity is O(n). It selects an element to act as a pivot and partitions the specified array around the pivot. There are numerous variations of quickSort that use pivot as the first, last, random, or median element. Choose the final piece as a pivot[14]:
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
// pivot
int pivot = arr[high];
// Index of smaller element and
// indicates the right position
// of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller
// than the pivot
if (arr[j] < pivot) {
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}4.7 Heap sort
The space complexity is O(n log(n)) while the time complexity is O(1). [15]
Heap sort is a sorting technique that uses comparisons and is based on the Binary Heap data structure. It is similar to the selection sort in that we discover the minimum element first and set it at the beginning. Resume the previous steps for the remaining parts. [15]
public void sort(int arr[])
{
int size = arr.length;
// Build heap (rearrange array)
for (int i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
// One by one extract an element from heap
for (int i = size - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int size, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < size && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < size && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, size, largest);
}
}4.8 Counting sort
Time complexity is O(n+k), and space complexity is O (k). [16]
Counting sort is a sorting approach that uses keys that fall inside a defined range. It operates by calculating the number of items with unique key values (a kind of hashing). After that, perform some arithmetic operations to determine the position of each object in the output sequence. [16]
void sort(char arr[])
{
int n = arr.length;
// The output character array that will have sorted
// arr
char output[] = new char[n];
// Create a count array to store count of individual
// characters and initialize count array as 0
int count[] = new int[256];
for (int i = 0; i < 256; i++)
count[i] = 0;
// store count of each character
for (int i = 0; i < n; i++)
count[arr[i]]++;
// Change count[i] so that count[i] now contains
// actual position of this character in output array
for (int i = 1; i <= 255; i++)
count[i] += count[i - 1];
// Build the output character array
// To make it stable we are operating in reverse
// order.
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the output array to arr, so that arr now
// contains sorted characters
for (int i = 0; i < n; i++)
arr[i] = output[i];
}4.9 Bucket sort
The time complexity is O(n+k), as is the space complexity. [17]
Bucket sort is a sorting algorithm that divides data uniformly into many groups called buckets. The elements are then sorted using any sorting method, and the elements are eventually gathered in a sorted way. This part will teach us how bucket sort works, including its algorithm, complexity, example, and implementation in a Java program. [17]
// Bucket sort in Java
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public void bucketSort(float[] arr, int n) {
if (n <= 0)
return;
@SuppressWarnings("unchecked")
ArrayList<Float>[] bucket = new ArrayList[n];
// Create empty buckets
for (int i = 0; i < n; i++)
bucket[i] = new ArrayList<Float>();
// Add elements into the buckets
for (int i = 0; i < n; i++) {
int bucketIndex = (int) arr[i] * n;
bucket[bucketIndex].add(arr[i]);
}
// Sort the elements of each bucket
for (int i = 0; i < n; i++) {
Collections.sort((bucket[i]));
}
// Get the sorted array
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0, size = bucket[i].size(); j < size; j++) {
arr[index++] = bucket[i].get(j);
}
}
}4.10 Radix sort
The complexity of time is O(nk), and the complexity of space is O(n+k). Radix sort is a number sorting algorithm that ranks integers depending on their digit positions. Essentially, it employs the place value of a number’s digits. It does not compare numbers, unlike most other sorting algorithms such as Merge Sort, Insertion Sort, and Bubble Sort. [18]
4.11 Tim Sort
The space complexity is O(nlog(n)) while the time complexity is O(n). [19]
The Array is divided into Run chunks. We sort those runs one by one with insertion sort and then merge them with the combine function from merge sort. If the array’s size is less than run, the array is sorted solely by utilizing Insertion Sort. The run’s size might range from 32 to 64 depending on the size of the array. It is worth noting that the merge function works effectively when the size subarrays are powers of two. The concept is based on the notion that insertion sort is effective for small arrays. [19]
Note: Collections.sort() in Java use TimSort (mergeSort + sequentialSort).[19]
References
[1] javatpoint,(2021), Collections in java:
[2] GeeksforGeeks, (10 Jan 2023), Queue Interface in Java: https://www.geeksforgeeks.org/queue-interface-java/
[3] javatpoint, (2023), Java List:
https://www.javatpoint.com/java-list
[4] GeeksforGeeks, (11 March 2023), Map Interface in Java with Examples: https://www.geeksforgeeks.org/map-interface-java-examples/
[5] GeeksforGeeks, (10 Jan 2023), Set in Java: https://www.geeksforgeeks.org/set-in-java/
[6] Tutorialspoint, (2023), Difference between HashMap and HashSet in Java:
https://www.tutorialspoint.com/difference-between-hashmap-and-hashset-in-java
[7] javatpoint, (2023), Tree in Java:
https://www.javatpoint.com/tree
[8] Edureka, (01 March 2023), Binary Tree in Java: https://www.edureka.co/blog/java-binary-tree
[9] Chandan Singh, (1 August 2021), Search Algorithms in Java: https://stackabuse.com/search-algorithms-in-java/
[10] javatpoint, (2023), Selection Sort in Java: https://www.javatpoint.com/selection-sort-in-java
[11] GeeksforGeeks, (24 March 2023), Bubble Sort: https://www.geeksforgeeks.org/bubble-sort/
[12] GeeksforGeeks, (19 March 2023), Quick Sort: https://www.geeksforgeeks.org/quick-sort/
[13] GeeksforGeeks,(22 March 2023), Insertion Sort:
[https://www.geeksforgeeks.org/insertion-sort/]
[14] GeeksforGeeks, (17 Feb 2023), Merge Sort: https://www.geeksforgeeks.org/merge-sort/
[15] GeeksforGeeks, (25 March 2023), Heap Sort: https://www.geeksforgeeks.org/heap-sort/
[16] GeeksforGeeks, (16 March 2023), Counting Sort: https://www.geeksforgeeks.org/counting-sort/
[17] javatpoint, (2023), Bucket Sort in Java: https://www.javatpoint.com/bucket-sort-in-java
[18] GeeksforGeeks, (24 March 2023), Radix Sort: https://www.geeksforgeeks.org/radix-sort/
[19] GeeksforGeeks, (17 March 2023), Timsort: https://www.geeksforgeeks.org/timsort/
