Dsa

Sorting algorithms are fundamental tools in computer science used to organize data efficiently. Sorting algorithms are techniques used to rearrange elements in a list or array in a specific order. The order could be ascending or descending based on certain criteria, such as numerical value or alphabetical order. Sorting algorithms play a crucial role in various applications, including databases, search algorithms, and more.

In Java, sorting algorithms can be implemented using various approaches, each with its unique characteristics and performance implications. In Java, there are various sorting algorithms, each with its advantages and disadvantages. In this guide, we’ll explore some of the most commonly used sorting algorithms, including their implementations, complexities, and use cases.

Sorting algorithms in Java : Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element per iteration and then finding its correct position in the sorted array.

public int[] insertionSort(int[] list) {
   
  int i;   // Counter for outer loop
  int j;   // Counter for inner loop

  int key;    // To hold the key value purpose we use it 

  int temp;   // It will be helpful while swapping values 

  for(i = 1; i < list.length; i++) {
     // Outer for loop starts with 1 and checks till the end value.
     // Here we consider the 0th element is already sorted that's why we start from 1
  
     key = list[i];   // It is our key value which is list[i] for every iteration  
     j = i - 1;         // It will start point of comparison moving downwards till 0 
   
     // We end the while loop when j value reaches 0 or when the key value is no longer smaller than the value
     while(j >= 0 && key < list[j]) {
       // Swap the values using the temp variable and arrange them in increasing order        
       temp = list[j];
       list[j] = list[j + 1];
       list[j + 1] = temp;
       j--;     // Decreasing j by 1 as we move towards the left 
     }

   }
   
  return list;
}

This insertionSort method implements the insertion sort algorithm for sorting an array of integers in increasing order. It iterates through the array, considering each element as a key and inserting it into the correct position in the sorted subarray to its left. The inner loop compares the key with the elements to its left and swaps them if necessary to maintain the sorted order. Finally, it returns the sorted array.

Explanation

Given an array of integers, sort them in increasing order using insertion sort:

Initial array: 5, 8, 1, 3, 9, 6

Definition of sorted: All items to the left are smaller. For example, 5 is already considered sorted as there are no elements to its left.

So, we start our insertion sort process from index 1:

1. Key (k) = 8. Compare k < 5? No. So, 8’s position is correct. Consider 5 and 8 as sorted.
2. Next, at index 2:
   • Key (k) = 1.
   • Compare k < 8? Yes, swap: 5, 1, 8, 3, 9, 6.
   • Compare k < 5? Yes, swap: 1, 5, 8, 3, 9, 6.
   • Element till index 2 is sorted.
3. Start at index 3:
   • Key (k) = 3.
   • Compare k < 8? Yes, swap: 1, 5, 3, 8, 9, 6.
   • Compare k < 5? Yes, swap: 1, 3, 5, 8, 9, 6.
   • Compare k < 1? No, no swap.
   • Elements till index 3 are now sorted.
4. Start at index 4:
   • Key (k) = 9.
   • Compare k < 8? No, no swap. Also, all elements left of 8 are sorted, indicating 9’s position is correct.
   • Elements till index 4 are also sorted.
5. Start at index 5:
   • Key (k) = 6.
   • Compare k < 9? Yes, swap: 1, 3, 5, 8, 6, 9.
   • Compare k < 8? Yes, swap: 1, 3, 5, 6, 8, 9.
   • Compare k < 5? No, no swap. End of loop.

Finally, we obtain the sorted list using insertion sort. Final array: {1, 3, 5, 6, 8, 9}

Note: Insertion Sort is not a fast sorting algorithm as it uses nested loops to shift items into place. It is useful only for small datasets. It runs in O(n^2) time complexity and O(1) space complexity.

Selection Sort

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the array and moves it to the beginning. This process continues until the entire array is sorted.

public int[] selectionSort(int[] list) {
    int i; // Outer loop counter
    int j; // Inner loop counter
    int minValue; // To track minimum value
    int minIndex; // To track the index of the minimum value in the array
    int temp = 0; // For swapping purposes

    // Let's consider this array: 7, 8, 5, 4, 9, 2

    // Outer loop should iterate from 0 to 5 (i.e., 6 iterations)
    // So the outer loop should be: for i = 0 to 5
    for (i = 0; i < list.length; i++) {
        // Initialize minValue and minIndex to the first unsorted item each time through the outer loop
        minValue = list[i];
        minIndex = i;

        // Inner loop starts at the first unsorted item and continues through the last item in the list
        // So the inner loop should be: for j = i to 5
        for (j = i; j < list.length; j++) {
            // Inside the inner loop, if the list item is less than the current minValue,
            // update minValue and store its index in minIndex
            if (list[j] < minValue) {
                minValue = list[j];
                minIndex = j;
            }
        }

        // After that, we check if the minValue is less than the value at the current index of the outer loop
        // If yes, then swap that value with the value at minIndex
        if (minValue < list[i]) {
            temp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = temp;
        }
    }
    return list;
}

This selectionSort method implements the selection sort algorithm for sorting an array of integers in increasing order. It iterates through the array, finding the minimum element in the unsorted part of the array and swapping it with the first unsorted element. This process repeats until the entire array is sorted. Finally, it returns the sorted array.

Explanation

Selection Sort: It finds the smallest item from the unsorted part of the list and moves it to the first element of the list while performing selection sort.

Consider this array: 7, 8, 5, 4, 9, 2 // also imagine indices from 0 to 5.

So initially, our minValue is 7 and minIndex is 0.

• Now, comparison:
  • Is 8 < minValue (7)? No.
  • Is 5 < minValue (7)? Yes, the new minValue is 5 and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4 and minIndex is 3.
  • Is 9 < minValue (4)? No. Is 2 < minValue (4)? Yes, the new minValue is 2 and minIndex is 5.

We found our first smallest element, so we swap that element with the first element ==> 2, 8, 5, 4, 9, 7.

• Our second iteration starts with index 1, so our first element is 8, and minValue is 8, with minIndex as 1. Now, start comparison toward the right side of 8.
  • Is 5 < minValue (8)? Yes, the new minValue is 5, and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4, and minIndex is 3.
  • Is 9 < minValue (4)? No.
  • Is 7 < minValue (4)? No.

We found our smallest element for the second iteration, so we swap it with the first element ==> 2, 4, 5, 8, 9, 7.

• Now, start comparison towards the right side of 5, and we see that 5 is the smallest element among them, so there’s no need to swap.

• Again, we start comparison towards the right side of 8. So, minValue is 8, and minIndex is 3.
  • Is 9 < minValue (8)? No.
  • Is 7 < minValue (8)? Yes, the new minValue is 7, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 9, 8.

• Now, for the next iteration, minValue is 9, and minIndex is 4.
  • Is 8 < minValue (9)? Yes, the new minValue is 8, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 8, 9.

Note: Selection Sort is not a fast sorting algorithm because it uses nested loops to sort. It is useful only for small datasets means suitable for small arrays or when auxiliary memory is limited. It runs in O(n^2) time complexity and O(1) space complexity.

Bubble Sort

Bubble Sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

public int[] bubbleSort(int[] list) {
    int i; // outer loop counter
    int j; // inner loop counter
    int temp = 0; // for swapping purpose

    for (i = 0; i < list.length - 1; i++) { // outer loop iterate till the end
        for (j = 0; j < list.length - 1 - i; j++) { // inner loop iterate till the end where already sorted element bubbled at the end
            if (list[j] > list[j + 1]) { // if we consider two adjacent values then previous value greater means we need to swap them with next value
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
    return list;
}

This bubbleSort method implements the bubble sort algorithm for sorting an array of integers in increasing order. It iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order. This process repeats until the array is sorted. Finally, it returns the sorted array.

Explanation

Bubble Sort: It is a simple sorting algorithm that repeatedly compares adjacent elements in the list and swaps them if they are in the wrong order. This process continues until the list is sorted.

Unsorted list: 5, 8, 1, 6, 9, 2 // Imagine indices from 0 to 5.

So, what is bubble sort?

In bubble sort, we repeatedly compare adjacent items, for example, 5 and 8, so that with every iteration, larger items “bubble” to the right side.

• First iteration:
  • Is 5 > 8? No.
    • Is 8 > 1? Yes ==> Swap ==> 5, 1, 8, 6, 9, 2
      • Is 8 > 6? Yes ==> Swap ==> 5, 1, 6, 8, 9, 2
        • Is 8 > 9? No.
          • Is 9 > 2? Yes ==> Swap ==> 5, 1, 6, 8, 2, 9

• Second iteration:
  • Is 5 > 1? Yes ==> Swap ==> 1, 5, 6, 8, 2, 9
    • Is 5 > 6? No.
      • Is 6 > 8? No.
        • Is 8 > 2? Yes ==> Swap ==> 1, 5, 6, 2, 8, 9

• Third iteration:
  • Is 1 > 5? No.
    • Is 5 > 6? No.
      • Is 6 > 2? Yes ==> Swap ==> 1, 5, 2, 6, 8, 9
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fourth Iteration:
  • Is 1 > 5? No.
    • Is 5 > 2? Yes ==> Swap ==> 1, 2, 5, 6, 8, 9
      • Is 5 > 6? No.
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fifth Iteration:
  • All elements are in sorted order; no need to do any swapping.

Final sorted list: 1, 2, 5, 6, 8, 9

Note: Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is useful only for small data sets. It runs in O(n^2) and O(1) space complexity.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts each half separately, and then merges the sorted halves.

// passing low and high index to this function
// e.g 38,27,43,3,9,82,10 ==> low -> 0 and high -> 6 (size - 1)th index
private void mergeSort(int low, int high) {
    if (low < high)      // base condition
    {
        int mid = low + (high - low) / 2;    // we need to find mid (it is 3 here)
        // perform recursive division into low to mid and then mid + 1 to high
        mergeSort(low, mid);      // 38,27,43,3  ===for next recursive call ===> 38,27 and 43,3 === next recursive call ==> 38 and 27 | 43 and 3 here as we reached base condition where low and high are equal and return back and execute remaining code
        mergeSort(mid + 1, high);   // we start when the above statement executed completely and reached the base case, so now 9,82,10  === for the next recursive call ===> 9,82 and 10  ==== for the next call ===> 9 and 82 | 10 here also we reached the base condition so go back now
        merge(low, mid, high);    // it will just merge the elements according to the sorting order
    }
}

// we pass low, mid, and high value
private void merge(int low, int mid, int high) {
    // for copying purposes means we copy number values to helper[] from low to till high
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    // we tried to sort the numbers[] element and placed them in exact same order
    while (i <= mid && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
        } else {
            numbers[k] = helper[j];
            j++;
        }
        k++;
    }

    // if still some values remain to be placed in sorted order in numbers[] we will do that here
    while (i <= mid) {
        numbers[k] = helper[i];
        k++;
        i++;
    }
}

These methods implement the merge sort algorithm. mergeSort is a recursive method that divides the array into two halves and recursively calls itself on each half until it reaches the base case where low is no longer less than high. Then, the merge method merges the two sorted halves into a single sorted array.

Explanation

Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, recursively calls itself for the two halves, and then merges the two sorted halves.

For example, with an input array like 38, 27, 43, 3, 9, 82, 10:

First, we call mergeSort(0, 6) as the initial entry point.

In mergeSort:

• We find the mid index (low + (high – low) / 2) to split the array into two halves.
• Then, we recursively call mergeSort for the left half (low to mid) and the right half (mid + 1 to high).
• Finally, we merge the sorted halves using the merge function.

In merge:

• We create a helper array to copy elements from the original array.
• We iterate through the two halves, comparing elements and merging them into the original array in sorted order.
• If any elements remain in the left half after merging, we copy them back to the original array.

Let’s go through the merge sort algorithm step by step:

1. Initial array: {38, 27, 43, 3, 9, 82, 10}
2. Initial call to mergeSort(0, 6):
   • Since low (0) is less than high (6), we proceed.
   • Calculate mid = 0 + (6 – 0) / 2 = 3
3. Recursive call 1: mergeSort(0, 3)
   • Since low (0) is less than high (3), we proceed.
   • Calculate mid = 0 + (3 – 0) / 2 = 1
4. Recursive call 2a: mergeSort(0, 1)
   • Since low (0) is less than high (1), we proceed.
   • Calculate mid = 0 + (1 – 0) / 2 = 0
5. Recursive call 2b: mergeSort(1, 3)
   • Since low (1) is less than high (3), we proceed.
   • Calculate mid = 1 + (3 – 1) / 2 = 2
6. Recursive call 3: mergeSort(1, 2)
   • Since low (1) is less than high (2), we proceed.
   • Calculate mid = 1 + (2 – 1) / 2 = 1
7. Recursive call 4: mergeSort(2, 3)
   • Since low (2) is less than high (3), we proceed.
   • Calculate mid = 2 + (3 – 2) / 2 = 2
8. Back to Recursive call 4: merge(1, 1, 2)
   • Helper array: {27, 43, 43, 3, 9, 82, 10}
   • i = 1, j = 2, k = 1
   • Compare helper[i] (27) with helper[j] (43), place the smaller one (27) in numbers[k] (numbers[1]), increment i and k.
   • numbers: {38, 27, 43, 3, 9, 82, 10}
   • Increment k to 2 and i to 2.
9. Back to Recursive call 3: merge(1, 1, 3)
   • Helper array: {27, 38, 43, 3, 9, 82, 10}
   • i = 1, j = 3, k = 1
   • Compare helper[i] (27) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[1]), increment j and k.
   • numbers: {38, 3, 43, 3, 9, 82, 10}
   • Increment k to 2 and j to 4.
   • Compare helper[i] (27) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[2]), increment j and k.
   • numbers: {38, 3, 9, 3, 9, 82, 10}
   • Increment k to 3 and j to 5.
   • Compare helper[i] (27) with helper[j] (82), place the smaller one (27) in numbers[k] (numbers[3]), increment i and k.
   • numbers: {38, 3, 9, 27, 9, 82, 10}
   • Increment k to 4 and i to 2.
10. Back to Recursive call 2a: merge(0, 0, 1)
    • Helper array: {38, 38, 9, 27, 9, 82, 10}
    • i = 0, j = 1, k = 0
    • Compare helper[i] (38) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[0]), increment j and k.
    • numbers: {3, 3, 9, 27, 9, 82, 10}
    • Increment k to 1 and j to 2.
    • Compare helper[i] (38) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[1]), increment j and k.
    • numbers: {3, 9, 9, 27, 9, 82, 10}
    • Increment k to 2 and j to 3.
    • Compare helper[i] (38) with helper[j] (27), place the smaller one (27) in numbers[k] (numbers[2]), increment i and k.
    • numbers: {3, 9, 27, 27, 9, 82, 10}
    • Increment k to 3 and i to 1.
11. Back to Recursive call 1: merge(0, 1, 3)
    • Helper array: {3, 9, 27, 38, 9, 82, 10}
    • i = 0, j = 2, k = 0
    • Compare helper[i] (3) with helper[j] (9), place the smaller one (3) in numbers[k] (numbers[0]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 1 and i to 1.
    • Compare helper[i] (9) with helper[j] (27), place the smaller one (9) in numbers[k] (numbers[1]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 2 and i to 2.
    • Compare helper[i] (27) with helper[j] (38), place the smaller one (27) in numbers[k] (numbers[2]), increment j and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 3 and j to 3.
12. Final array: {3, 9, 27, 38, 9, 82, 10}

This process continues until the entire array is sorted. The merge sort algorithm effectively divides the array into smaller segments, sorts them individually, and then merges them back together in sorted order.

Note: Merge Sort has a time complexity of O(n log n) in the average and worst cases, and O(n) in the best case, making it efficient for large datasets and O(n) space complexity.

Quick Sort

Quick Sort is another divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It then recursively sorts the subarrays.

private void quickSort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];  // Choosing the pivot element

    // Partitioning the array
    while (i <= j) {
        // Finding element on the left side that should be on the right
        while (numbers[i] < pivot) {
            i++;
        }
        // Finding element on the right side that should be on the left
        while (numbers[j] > pivot) {
            j--;
        }

        // If we found a value on the left that should be on the right and vice versa, swap them
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    // Recursively sort the left and right partitions
    if (low < j) {
        quickSort(low, j);
    }
    if (i < high) {
        quickSort(i, high);
    }
}

This quickSort method implements the Quick Sort algorithm. It chooses a pivot element (here, the middle element) and partitions the array into two sub-arrays such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the sub-arrays until the entire array is sorted. The exchange method is assumed to swap the values at two indices in the array.

Explanation

Quick Sort is a divide and conquer algorithm. In this algorithm, the original data is divided into two parts, sorted individually, and then combined.

suppose

{6,4,2,1,5,3} is an array where low is pointing to 0th index and high is pointing to last index.

means,

• Set low to 0 and high to array.length - 1, then pass these values to quickSort(low, high).
• Assign low to i, which is the left side counter of the pivot, and assign high to j, which is the right side counter of the pivot.
• Find the pivot. What is a pivot? A pivot is a point we consider while sorting. We arrange smaller values than the pivot to its left side and greater values to its right side. We can take any value as the pivot, but it’s best to take it randomly. Here, we use the middle element as the pivot.
• We will check i <= j. If low becomes greater than high, we stop our following checks: i) First, we check the left side of the pivot to find any greater value than the pivot. If we find such a value, we terminate the while loop. Otherwise, we iterate until we reach the pivot. Since we don’t have any problem with values smaller than the pivot (as those should be on the left side), we increment i and move towards the pivot to check the next value. ii) After completing the left side (either by complete check or finding a greater value, terminating the while loop), we look at the right side of the pivot. We apply the same logic: while(any value > pivot). If true, we decrement j. If we find any smaller value than the pivot, the while loop terminates. iii) So, in the above two cases, we find whether the left side of the pivot will contain any greater value than the pivot or whether the right side of the pivot will contain any smaller value than the pivot. Because we sort the values according to the pivot, if we find a smaller value to the right and a larger value to the left, we need to place them on their respective sides. For this purpose, we use another if() condition: if i is not greater than j, then only do we exchange the values. Finally, we increment i and decrement j.
• As we perform sorting according to the pivot, only small values are placed on the left side of the pivot and large values are placed on the right side. However, we notice that neither the left side nor the right side is sorted.

For example, with an array like 6, 4, 2, 1, 5, 3:

• We call quickSort(0, 5) initially, where low = 0 and high = 5.
• We select a pivot element, here we choose the middle element, which is 2.
• We partition the array around the pivot, ensuring that elements less than the pivot are on the left and elements greater than the pivot are on the right.
• We recursively call quickSort for the left and right partitions, ensuring that all elements are sorted individually.
• We repeat this process until the entire array is sorted.

Let’s go through the Quick Sort algorithm step by step:

1. Initial array: {6, 4, 2, 1, 5, 3}
2. Initial call to quickSort(0, 5):
   • i = 0, j = 5
   • Pivot = numbers[0 + (5 – 0) / 2] = numbers[2] = 2
3. While loop (i=0, j=5):
   • i moves from left to right until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves from right to left until it finds a value less than or equal to the pivot. (j stops at 3)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 4, 2, 1, 5, 6}
   • Increment i and decrement j (i = 1, j = 4)
4. While loop (i=1, j=4):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 1)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 2, j = 3)
5. While loop (i=2, j=3):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 2)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 2)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array remains {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 3, j = 1)
6. While loop termination (i=3, j=1):
   • i > j, so the while loop terminates.
7. Recursive call 1: quickSort(0, 1)
   • This is the left side partition.
   • i = 0, j = 1
   • Subarray: {3, 1}
   • Pivot = numbers[0] = 3
   • While loop terminates immediately as i > j.
8. Recursive call 2: quickSort(3, 5)
   • This is the right side partition.
   • i = 3, j = 5
   • Subarray: {4, 5, 6}
   • Pivot = numbers[3] = 4
   • While loop terminates immediately as i > j.
9. Final sorted array: {1, 2, 3, 4, 5, 6}

This process continues recursively until all partitions have size 1 or less, meaning the array is sorted. The Quick Sort algorithm effectively divides the array into smaller partitions, sorts them individually, and then combines them to get the sorted array.

Note: Quick Sort has a time complexity of O(n log n) in the average and best cases, and O(n^2) in the worst case. However, its average case performance is typically much better than other O(n^2) algorithms like Bubble Sort and Selection Sort. It has space complexity O(log n) to O(n). Also, Quick Sort is efficient and widely used, but it has a higher worst-case time complexity compared to Merge Sort.

Conclusion

In this guide, we’ve covered several sorting algorithms in Java, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort. Each algorithm has its advantages and disadvantages, and the choice of algorithm depends on factors such as the size of the dataset, memory constraints, and desired performance characteristics. By understanding these sorting algorithms, you can choose the most appropriate one for your specific use case and optimize the efficiency of your Java applications.

Graphs are fundamental data structures in computer science and are widely used to model complex relationships between entities. They are versatile and can represent a variety of real-world scenarios such as social networks, transportation networks, and computer networks. In this blog post, we’ll delve into some essential graph algorithms implemented in Java, covering Depth-First Search (DFS), Breadth-First Search (BFS), Dijkstra’s Shortest Path Algorithm, detecting cycles in a directed graph, and performing a topological sort.

Understanding Graphs

Before diving into the algorithms, let’s briefly review what graphs are. We know that data arranged in a linear manner is called linear data structures, such as Arrays, LinkedLists, Stacks, and Queues. Whereas, when data is stored non-linearly, it is referred to as non-linear data structures, such as Trees and Graphs. A graph consists of a set of vertices (nodes) and a set of edges (connections) that establish relationships between these vertices. Edges can be directed or undirected, depending on whether they have a specific direction or not. Graphs can also be weighted, where each edge has an associated weight or cost.

A graph is a powerful non-linear data structure consisting of two components:

• Vertices (nodes): Represent individual entities or data points. Think of them as points on a map.
• Edges: Represent connections between vertices, indicating relationships or interactions. Edges can be bidirectional (undirected) or unidirectional (directed), like arrows showing one-way relationships.

A graph G is an ordered pair consisting of a set V of vertices and a set E of edges.

G = (V,E)

In an ordered pair, (a,b) is not equivalent to (b,a) if a ≠ b.

In an unordered pair, {a,b} equals {b,a}.

Edges:

• Directed: (u,v) i.e., u → v
• Undirected: {u,v} i.e., u — v

Example:

V = {v1, v2, v3, v4, v5, v6, v7, v8} // Set of vertices

E = { {v1, v2}, {v1, v3}, {v2, v4}, {v3, v5}, {v4, v6}, {v5, v7}, {v6, v8}, {v7, v8}, {v2, v5}, {v3, v6} }

Graph Examples

Consider a social network like Facebook. Users are represented as vertices, and friendships are represented as edges. If A and B are friends, we can have either a directed edge A -> B (meaning A follows B) or an undirected edge {A, B} (meaning they follow each other).

Common Graphs Examples

• Maps: Represent cities as vertices and roads as edges (weighted to denote distance).
• World Wide Web: Represent web pages as vertices and hyperlinks as directed edges pointing from source pages to destination pages.
• File systems: Represent directories as vertices and subdirectory/file connections as edges.

Graph Representations:

• Adjacency Matrix: Square matrix, where (i,j) reflects the edge weight between vertices i and j. Suitable for dense graphs with many edges.
• Adjacency List: Array or list of lists, where each index stores connections for a specific vertex. More efficient for sparse graphs with fewer edges.

Implementing Graphs in Java

To start, we’ll implement a simple graph representation in Java. We’ll use an adjacency list to store the graph, which is a list of lists where each list represents the neighbors of a particular vertex.

import java.util.*;

class Graph {
    private int V; // Number of vertices
    private LinkedList<Integer> adjList[]; // Adjacency list representation

    // Constructor
    Graph(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList<>();
    }

    // Function to add an edge to the graph
    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    // Getter for the adjacency list of a vertex
    LinkedList<Integer> getAdjList(int v) {
        return adjList[v];
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        for (int i = 0; i < graph.V; i++) {
            LinkedList<Integer> list = graph.getAdjList(i);
            System.out.print("Adjacency list of vertex " + i + ": ");
            for (Integer node : list) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }
}

This Graph class represents an undirected graph using an adjacency list representation. It has a constructor to initialize the graph with a given number of vertices. The addEdge method adds an edge between two vertices. The getAdjList method returns the adjacency list of a specified vertex.

The main method demonstrates how to use the Graph class by creating a graph with 4 vertices and adding some edges. Then, it prints the adjacency list of each vertex.

Common Types of Graphs

Here are some common types of graphs and their java implementations:

Directed Graphs (Digraphs)

Directed graphs, also known as digraphs, are graphs in which edges have a direction associated with them. This means that the relationship between nodes is one-way. They are used to model relationships like dependencies, flows, or hierarchical structures.

   A
  ↗ ↘
 B   C
  ↘ ↗
   D

• Vertices are represented by letters: A, B, C, D.
• Arrows indicate the direction of the edges.
• Arrows point from the source vertex to the destination vertex, representing a directed edge from the source to the destination.

Implementation: In Java, you can implement a directed graph using adjacency lists or adjacency matrices. Here’s a basic example of implementing a directed graph using adjacency lists:

import java.util.*;

class Digraph {
    private int V;
    private List<Integer>[] adj;

    public Digraph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

Undirected Graphs

Undirected graphs are graphs in which edges do not have any direction associated with them. The relationship between nodes is bidirectional. They are used to model symmetric relationships, such as friendships in social networks or connections in a network.

   A
  / \
 /   \
B --- C
 \   /
  \ /
   D

• Vertices are represented by letters: A, B, C, D.
• Edges are represented by lines connecting the vertices.
• Each line connects two vertices, representing an undirected edge between them.

Implementation: Similar to directed graphs, undirected graphs can be implemented using adjacency lists or adjacency matrices. Here’s a basic example of implementing an undirected graph using adjacency lists:

import java.util.*;

class Graph {
    private int V;
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

Weighted Graphs

Weighted graphs are graphs in which each edge has an associated weight or cost. They are used to model scenarios where the relationship between nodes has a numerical value associated with it, such as distances between cities or costs of transportation.

   
   A
2/   \4
/     \
B--5-- C
\1   3/
 \   /
   D

• Vertices are represented by letters: A, B, C, D.
• Edges are represented by lines connecting the vertices.
• Each line connecting two vertices represents an edge.
• Beside each edge, there is a number indicating the weight of that edge.
• For example, the edge between vertices A and B has a weight of 2, the edge between vertices B and D has a weight of 1, etc.

Implementation: Weighted graphs can be implemented similarly to undirected or directed graphs, with the addition of storing weights along with edges. Here’s an example of implementing a weighted graph using adjacency lists:

import java.util.*;

class WeightedGraph {
    private int V;
    private List<Edge>[] adj;

    class Edge {
        int v, w;

        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public WeightedGraph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w, int weight) {
        adj[v].add(new Edge(w, weight));
        adj[w].add(new Edge(v, weight)); // For undirected graphs
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }
}

Graph Algorithms

Now that we have our graph implementation ready, let’s explore some fundamental graph algorithms.

Depth-First Search (DFS) Traversal Algorithm

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of vertices to visit next.

class DFS {
    // Depth-First Search traversal
    void dfsUtil(int v, boolean visited[], Graph graph) {
        visited[v] = true;
        System.out.print(v + " ");

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor])
                dfsUtil(neighbor, visited, graph);
        }
    }

    void dfs(int v, Graph graph) {
        boolean visited[] = new boolean[graph.V];
        dfsUtil(v, visited, graph);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        DFS dfs = new DFS();
        System.out.print("Depth-First Search traversal starting from vertex 2: ");
        dfs.dfs(2, graph);
    }
}

This DFS class contains methods for performing a Depth-First Search (DFS) traversal on a graph. The dfsUtil method is a recursive utility function that performs DFS traversal starting from a specified vertex (v). It marks the vertex as visited, prints its value, and then recursively visits its unvisited neighbors. The dfs method initializes an array to track visited vertices and calls dfsUtil to start the DFS traversal from a specified vertex.

The main method demonstrates how to use the DFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a DFS traversal starting from vertex 2 and prints the traversal result.

Breadth-First Search (BFS) Traversal Algorithm

BFS is another traversal algorithm that explores all the neighboring nodes at the present depth prior to moving on to the nodes at the next depth level.

import java.util.LinkedList;

class BFS {
    // Breadth-First Search traversal
    void bfs(int v, Graph graph) {
        boolean visited[] = new boolean[graph.V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[v] = true;
        queue.add(v);

        while (!queue.isEmpty()) {
            v = queue.poll();
            System.out.print(v + " ");

            LinkedList<Integer> neighbors = graph.getAdjList(v);
            for (Integer neighbor : neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        BFS bfs = new BFS();
        System.out.print("Breadth-First Search traversal starting from vertex 2: ");
        bfs.bfs(2, graph);
    }
}

This BFS class contains a method for performing a Breadth-First Search (BFS) traversal on a graph. The bfs method initializes a boolean array to track visited vertices and a queue to store vertices for traversal. It starts the traversal from a specified vertex (v), marks it as visited, and adds it to the queue. Then, it repeatedly dequeues vertices from the queue, prints them, and adds their unvisited neighbors to the queue.

The main method demonstrates how to use the BFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a BFS traversal starting from vertex 2 and prints the traversal result.

Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph. It maintains a priority queue to continuously select the vertex with the smallest distance from the source.

import java.util.*;

class Dijkstra {
    // Dijkstra's Shortest Path Algorithm
    void dijkstra(int src, Graph graph) {
        int V = graph.V;
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
        pq.add(src);

        while (!pq.isEmpty()) {
            int u = pq.poll();
            LinkedList<Integer> neighbors = graph.getAdjList(u);
            for (Integer v : neighbors) {
                int weight = 1; // Assuming unweighted graph, modify for weighted graph
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(v);
                }
            }
        }

        // Print shortest distances
        System.out.println("Shortest distances from source vertex " + src + ":");
        for (int i = 0; i < V; i++) {
            System.out.println("Vertex " + i + ": " + dist[i]);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        Dijkstra dijkstra = new Dijkstra();
        int sourceVertex = 0;
        dijkstra.dijkstra(sourceVertex, graph);
    }
}

This Dijkstra class contains a method for finding the shortest path distances from a source vertex to all other vertices in a graph using Dijkstra’s algorithm. The dijkstra method initializes an array to store shortest distances (dist), initializes all distances to infinity except for the source vertex distance which is set to 0. It then uses a priority queue (pq) to greedily select the vertex with the shortest distance and updates the distances to its neighbors if a shorter path is found. Finally, it prints the shortest distances from the source vertex to all other vertices.

The main method demonstrates how to use the Dijkstra class by creating a graph with 6 vertices and adding some edges. Then, it performs Dijkstra’s algorithm starting from a specified source vertex and prints the shortest distances to all other vertices.

Detecting Cycles in a Directed Graph

Detecting cycles in a directed graph is crucial in various applications such as deadlock detection and task scheduling. We’ll use a modified DFS approach to detect cycles.

class CycleDetection {
    boolean isCyclicUtil(int v, boolean visited[], boolean recStack[], Graph graph) {
        if (recStack[v])
            return true;

        if (visited[v])
            return false;

        visited[v] = true;
        recStack[v] = true;

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (isCyclicUtil(neighbor, visited, recStack, graph))
                return true;
        }

        recStack[v] = false;
        return false;
    }

    boolean isCyclic(Graph graph) {
        boolean visited[] = new boolean[graph.V];
        boolean recStack[] = new boolean[graph.V];

        for (int i = 0; i < graph.V; i++) {
            if (isCyclicUtil(i, visited, recStack, graph))
                return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        CycleDetection cycleDetection = new CycleDetection();
        if (cycleDetection.isCyclic(graph))
            System.out.println("The graph contains a cycle");
        else
            System.out.println("The graph doesn't contain a cycle");
    }
}

This CycleDetection class contains methods to detect cycles in a graph using depth-first search (DFS). The isCyclicUtil method recursively checks if there is a cycle starting from a given vertex (v) by maintaining a boolean array (recStack) to keep track of the vertices in the current recursion stack. If a vertex is visited and also present in the recursion stack, it indicates the presence of a cycle. The isCyclic method iterates through all vertices in the graph and calls isCyclicUtil for each vertex to check for cycles.

The main method demonstrates how to use the CycleDetection class by creating a graph with 4 vertices and adding some edges. Then, it checks if the graph contains a cycle and prints the result.

Topological Sorting of a Graph

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

import java.util.*;

class TopologicalSort {
    Stack<Integer> stack = new Stack<>();

    void topologicalSortUtil(int v, boolean visited[], Graph graph) {
        visited[v] = true;

        LinkedList<Integer> neighbors = graph.getAdjList(v);
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor])
                topologicalSortUtil(neighbor, visited, graph);
        }

        stack.push(v);
    }

    void topologicalSort(Graph graph) {
        int V = graph.V;
        boolean visited[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i])
                topologicalSortUtil(i, visited, graph);
        }

        // Print topological order
        System.out.println("Topological order:");
        while (!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topologicalSort(graph);
    }
}

This TopologicalSort class contains methods to perform topological sorting on a directed acyclic graph (DAG) using depth-first search (DFS). The topologicalSortUtil method recursively traverses the graph, marking visited vertices and pushing them onto a stack after visiting all of their neighbors. The topologicalSort method initiates DFS traversal for each vertex and then prints the topological order by popping vertices from the stack.

The main method demonstrates how to use the TopologicalSort class by creating a graph with 6 vertices and adding directed edges between them. Then, it performs topological sorting and prints the topological order.

Conclusion

In this blog post, we explored several essential graph algorithms implemented in Java, including DFS, BFS, Dijkstra’s Shortest Path Algorithm, cycle detection in directed graphs, and topological sorting. Understanding these algorithms is crucial for tackling a wide range of graph-related problems efficiently. Feel free to experiment with these implementations and explore further applications in your projects. Happy coding!

Binary trees are a fundamental data structure in computer science, widely used for representing hierarchical data. In this blog post, we will delve into the concept of binary trees, their implementation in Java, traversal algorithms, and some common operations associated with them.

Understanding Binary Trees

What is a Tree?

A tree is a non-linear data structure used for storing data. It is comprised of nodes and edges without any cycles. Each node in a tree can point to n number of other nodes within the tree. It serves as a way to represent hierarchical structures, with a parent node called the root and multiple levels of additional nodes.

• It’s a non-linear data structure used for storing data
• It is made up of nodes and edges without having any cycle. // its so important
• Each node in a tree can point to n number of nodes in a tree
• It is a way of representing a hierarchical structure with a parent node called a root and many levels of additional nodes

What is a Binary Tree?

A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node of the tree is called the root node. Each node contains a data element and references to its left and right children (or null if the child does not exist).

In simple words, A tree is called a binary tree if each node has zero, one, or two children.

       1
      / \
     2   3
    / \
   4   5

Binary trees are commonly used in various applications such as expression trees, binary search trees, and more.

How to represent a Binary Tree in java?

TreeNode Representation:

null<-----|left|data|right|------>null

Structure of TreeNode in a Binary Tree:

To represent a binary tree in Java, we can create a TreeNode class to define the structure of each node in the tree. Here’s how we can do it:

public class TreeNode {
    private int data;      // Data of the node
    private TreeNode left; // Pointer to the left child node
    private TreeNode right; // Pointer to the right child node
    
    // Constructor to initialize the node with data
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
    
    // Getters and setters for the data, left, and right pointers
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

In this TreeNode class:

• Each node has a data field to store the value of the node.
• Each node has a left field to store a reference to its left child node.
• Each node has a right field to store a reference to its right child node.
• The constructor initializes the node with the given data and sets both left and right pointers to null initially.

With this TreeNode class, you can create instances of the TreeNode class to represent each node in the binary tree. You can then use these instances to build the binary tree by setting the left and right pointers of each node accordingly. The root of the binary tree is typically represented by a reference to the topmost node in the tree. Initially, if the tree is empty, the root reference is set to null. As you add nodes to the tree, you update the root reference accordingly.

In simple words, Initially, the root node points to null. When we create any temporary node to insert into the tree, such as a temporary node with 15 as its data and left and right node pointers pointing to null, we can then add more nodes to the left or right.

How to implement a binary tree in java?

Let’s start by implementing a basic binary tree structure in Java:

public class BinaryTree {

  private TreeNode root;      // Created one root node of TreeNode type
 
  private class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int data;

    public TreeNode(int data) {
       this.data = data;
    }
  }

  public void createBinaryTree() {
     TreeNode first = new TreeNode(1);
     TreeNode second = new TreeNode(2);
     TreeNode third = new TreeNode(3);
     TreeNode fourth = new TreeNode(4);
     TreeNode fifth = new TreeNode(5);

     root = first;     // root ---> first
     first.left = second;
     first.right = third;  // second <--- first ---> third

     second.left = fourth;
     second.right = fifth;
  }

  public static void main(String[] args) {
     BinaryTree bt = new BinaryTree();
     bt.createBinaryTree();
  }
}

This BinaryTree class represents a simple binary tree. It has a nested class TreeNode which represents each node in the binary tree. The createBinaryTree method initializes the tree structure by creating nodes and linking them appropriately. Finally, the main method demonstrates creating an instance of BinaryTree and initializing it.

Traversal Algorithms

Traversal is the process of visiting all the nodes in a tree in a specific order. There are three common methods for traversing binary trees:

1. In-order traversal: Visit the left subtree, then the root, and finally the right subtree.
2. Pre-order traversal: Visit the root, then the left subtree, and finally the right subtree.
3. Post-order traversal: Visit the left subtree, then the right subtree, and finally the root.

Let’s implement these traversal algorithms in Java.

Pre-Order Traversal Of Binary Tree in Java

1. Visit the root node.
2. Traverse the left subtree in pre-order fashion.
3. Traverse the right subtree in pre-order fashion.

Recursive Pre-Order Traversal

It recursively traverses the tree in the following order: root, left subtree, right subtree.

public void preOrder(TreeNode root) {
    if(root == null) {
        return;
    }
    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it prints the data of the current node, traverses the left subtree recursively, and then traverses the right subtree recursively.

Consider the following binary tree:

     1
    / \
   2   3
  / \
 4   5

In pre-order traversal, the order of node visits would be: 1, 2, 4, 5, 3.

Here’s how the execution progresses:

1. pre_order_traversal(1) – Visit root node 1.
2. pre_order_traversal(2) – Visit root node 2.
3. pre_order_traversal(4) – Visit root node 4.
4. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(4)), finish left subtree traversal.
5. pre_order_traversal(5) – Visit root node 5.
6. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(5)), finish left subtree traversal.
7. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(2)), finish left subtree traversal.
8. pre_order_traversal(3) – Visit root node 3.
9. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(3)), finish right subtree traversal.
10. pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

Pre-order traversal: 1 2 4 5 3

In this execution, we maintain a call stack. For each method call, we track the line number and the root node being passed to that method. When we reach the base condition, we backtrack to the previous calls and execute the next steps.

Iterative Pre-Order Traversal Of Binary Tree

Iterative pre-order traversal is a way to traverse a binary tree iteratively, without using recursion. we utilize the stack data structure. Initially, we push the root node onto the stack. While the stack is not empty, we iterate using a while loop and perform pre-order traversal operations. As long as the stack is not empty, we pop the top node from the stack and assign it to the temp node. We then print its data. Since in pre-order traversal, we first visit the left node and then the right node, while pushing nodes into the stack, we need to push the right node first and then the left node so that we process the left node first (due to LIFO).

public void IterativePreOrder() {
    if(root == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode temp = stack.pop();
        System.out.println(temp.data);
        if(temp.right != null) {
            stack.push(temp.right);
        }
        if(temp.left != null) {
            stack.push(temp.left);
        }
    }
}

This method iterativePreOrder performs an iterative pre-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It prints the data of each node as it visits them. If a node has a right child, it is pushed onto the stack first so that it is visited after the left child (since pre-order traversal visits the left subtree before the right subtree). Finally, the method returns once all nodes have been visited.

Consider the following binary tree:

       1
      / \
     2   3
    / \
   4   5

The iterative pre-order traversal will visit the nodes in the order: 1, 2, 4, 5, 3.

Here’s how the execution goes step by step:

1. Start with an empty stack and initialize the current node as the root.
2. Push the root node onto the stack.
3. While the stack is not empty, do the following:
   • a. Pop the top node from the stack and process it (print its value or perform any other desired operation).
   • b. Push the right child onto the stack if it exists.
   • c. Push the left child onto the stack if it exists.

Let’s execute the algorithm step by step:

1. Start with an empty stack: Stack = []
2. Push the root node (1) onto the stack: Stack = [1]
3. Pop the top node from the stack (1), process it: Output = [1], Stack = []
4. Push the right child (3) onto the stack: Stack = [3]
5. Push the left child (2) onto the stack: Stack = [3, 2]
6. Pop the top node from the stack (2), process it: Output = [1, 2], Stack = [3]
7. Push the right child (5) onto the stack: Stack = [3, 5]
8. Push the left child (4) onto the stack: Stack = [3, 5, 4]
9. Pop the top node from the stack (4), process it: Output = [1, 2, 4], Stack = [3, 5]
10. There’s no left or right child for node 4, so proceed.
11. Pop the top node from the stack (5), process it: Output = [1, 2, 4, 5], Stack = [3]
12. There’s no left or right child for node 5, so proceed.
13. Pop the top node from the stack (3), process it: Output = [1, 2, 4, 5, 3], Stack = []
14. The stack is empty, so the traversal is complete.

The output of the iterative traversal is: [1, 2, 4, 5, 3], which is the pre-order traversal of the given binary tree.

During the execution of iterative pre-order traversal, we follow the described algorithm. We push the root node onto the stack initially. Then, as long as the stack is not empty, we pop nodes from the stack, print their data, and push their right and left children onto the stack accordingly.

In Order Binary Tree traversal

1. Traverse the left subtree in In-order fashion.
2. Visit the root node.
3. Traverse the right subtree in In-order fashion.

In-order traversal of a binary tree involves visiting the left subtree in in-order fashion, then visiting the root node, and finally traversing the right subtree in in-order fashion.

Recursive In-Order Binary Tree Traversal

In Recursive In-order traversal, we visit each node in the tree in the following order:

1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.

public void RecursiveInOrder(TreeNode root) {
    if(root == null) { // base case
        return;
    }
    
    RecursiveInOrder(root.left);
    System.out.print(root.data + " ");
    RecursiveInOrder(root.right);
}

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it recursively traverses the left subtree, then prints the data of the current node, and finally recursively traverses the right subtree.
• This process effectively traverses the tree in an in-order sequence.

Consider the same binary tree:

     1
    / \
   2   3
  / \
 4   5

In in-order traversal, the order of node visits would be: 4, 2, 5, 1, 3.

Here’s how the execution progresses:

1. in_order_traversal(1) – Traverse left subtree.
2. in_order_traversal(2) – Traverse left subtree.
3. in_order_traversal(4) – Visit root node 4.
4. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(4)), finish left subtree traversal.
5. Print root node 2.
6. in_order_traversal(5) – Visit root node 5.
7. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(5)), finish left subtree traversal.
8. Print root node 1.
9. in_order_traversal(3) – Traverse right subtree.
10. Print root node 3.
11. in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

In-order traversal:4 2 5 1 3

During the execution of recursive in-order traversal, we maintain a method call stack. For each method call, we keep track of the line number and the root node being passed to that method. Initially, we pass the root node to this method. Then, we visit the left subtree of the root node, print the root node’s data, and finally visit the right subtree of the root node. This tracking of each recursive method call, line number, and root node helps during backtracking.

Iterative In Order Traversal of binary tree in java

In iterative in-order traversal, we visit the left node first, then perform in-order traversal for that node, come back to print the root node’s data, and finally visit the right node to perform its in-order traversal.

To achieve this, we create a stack of TreeNodes and initialize a temp node with the root node. We traverse the tree until the stack is not empty or temp is not null (indicating there are nodes to traverse or backtrack).

If temp is not null, we push it onto the stack and move to its left child. If temp is null, indicating we have reached a leaf node, we pop the top node from the stack, print its data, and move to its right child. This process continues until all nodes are traversed.

public void iterativeInOrderTraversal(TreeNode root) {
   if (root == null) {
     return;
   }

  Stack<TreeNode> stack = new Stack<>();
  TreeNode temp = root;
  while (!stack.isEmpty() || temp != null) {
    if (temp != null) {
      stack.push(temp);
      temp = temp.left;
    } else {
      temp = stack.pop();
      System.out.print(temp.data + " ");
      temp = temp.right;
    }    
  }
}

This method iterativeInOrderTraversal performs an iterative in-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It traverses the left subtree first, then visits the current node, and finally traverses the right subtree. If a node has a left child, it is pushed onto the stack and the left child becomes the current node. If a node does not have a left child or has already been visited, it is popped from the stack, its data is printed, and its right child becomes the current node. The traversal continues until all nodes have been visited and the stack is empty.

Consider the same binary tree:

       1
      / \
     2   3
    / \
   4   5

The iterative in-order traversal will visit the nodes in the order: 4, 2, 5, 1, 3.

Here’s how the execution goes step by step:

1. Start with an empty stack and initialize the current node as the root.
2. Push the root node onto the stack and move to the left child until reaching a null node.
3. When a null node is reached, pop the top node from the stack, process it (print its value or perform any other desired operation), and move to its right child.

Let’s execute the algorithm step by step:

1. Start with an empty stack: Stack = []
2. Push the root node (1) onto the stack and move to the left child: Stack = [1], Current Node = 1
3. Move to the left child of 1 (2) and push it onto the stack: Stack = [1, 2], Current Node = 2
4. Move to the left child of 2 (4) and push it onto the stack: Stack = [1, 2, 4], Current Node = 4
5. The left child of 4 is null, so pop 4 from the stack, process it: Output = [4], Stack = [1, 2], Current Node = 2
6. Move to the right child of 4 (null), so no action needed: Output = [4], Stack = [1, 2], Current Node = 2
7. Process node 2: Output = [4, 2], Stack = [1], Current Node = 2
8. Move to the right child of 2 (5) and push it onto the stack: Stack = [1, 5], Current Node = 5
9. The left child of 5 is null, so process node 5: Output = [4, 2, 5], Stack = [1], Current Node = 5
10. Move to the right child of 5 (null), so no action needed: Output = [4, 2, 5], Stack = [1], Current Node = 5
11. Process node 1: Output = [4, 2, 5, 1], Stack = [], Current Node = 1
12. Move to the right child of 1 (3) and push it onto the stack: Stack = [3], Current Node = 3
13. The left child of 3 is null, so process node 3: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
14. Move to the right child of 3 (null), so no action needed: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
15. The stack is empty, so the traversal is complete.

The output of the traversal is: [4, 2, 5, 1, 3], which is the in-order traversal of the given binary tree.

Post Order traversal of Binary Tree

1. Traverse the left subtree in Post-order fashion.
2. Traverse the right subtree in Post-order fashion.
3. Visit the root node.

Recursive Post-Order Traversal of Binary Tree

In recursive post-order traversal, we visit each node in the tree in the following order:

1. Recursively traverse the left subtree.
2. Recursively traverse the right subtree.
3. Visit the root node.

       1
      / \
     2   3
    / \
   4   5

In post-order traversal, the order of node visits would be: 4, 5, 2, 3, 1.

public void RecursivePostOrder(TreeNode root) {
    if(root == null) {
        return;
    }
    
    RecursivePostOrder(root.left);
    RecursivePostOrder(root.right);
    System.out.print(root.data + " ");
}

In this code:

• If the root is null, indicating an empty subtree, the method returns.
• If the root is not null, it recursively traverses the left subtree, then recursively traverses the right subtree, and finally prints the data of the current node.
• This process effectively traverses the tree in a post-order sequence.

Here’s how the execution progresses:

1. post_order_traversal(1) – Traverse left subtree.
2. post_order_traversal(2) – Traverse left subtree.
3. post_order_traversal(4) – Visit root node 4.
4. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(4)), finish left subtree traversal.
5. post_order_traversal(5) – Visit root node 5.
6. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(5)), finish left subtree traversal.
7. Print root node 2.
8. post_order_traversal(3) – Traverse right subtree.
9. Print root node 3.
10. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(3)), finish right subtree traversal.
11. Print root node 1.
12. post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(1)), finish right subtree traversal.

And the output of the traversal will be:

Post-order traversal: 4 5 2 3 1

In recursive post-order traversal, we utilize a method call stack. For each recursive call, we visit the left and right nodes respectively, and then print the data of the root node.

To illustrate this, we maintain a method call stack where we track the line number and the root node being passed to that method. This approach ensures that we visit the left and right subtrees first before printing the data of the root node.

Iterative post-order traversal of a binary tree

Iterative post-order traversal is a bit more complex compared to pre-order and in-order traversals because you need to ensure that you visit the left and right subtrees before processing the root node. One common approach to achieve this iteratively is to use two stacks.

public void iterativePostOrderTraversal(TreeNode root) {
   if (root == null) {
     return;
   }

   Stack<TreeNode> stack1 = new Stack<>();
   Stack<TreeNode> stack2 = new Stack<>();
   stack1.push(root);

   while (!stack1.isEmpty()) {
       TreeNode temp = stack1.pop();
       stack2.push(temp);
       if (temp.left != null) {
           stack1.push(temp.left);
       }
       if (temp.right != null) {
           stack1.push(temp.right);
       }
   }

   while (!stack2.isEmpty()) {
       System.out.print(stack2.pop().data + " ");
   }
}

This method iterativePostOrderTraversal performs an iterative post-order traversal of the binary tree. It starts from the root node and uses two stacks to keep track of nodes to be visited. It pushes nodes onto stack2 in a pre-order traversal (root, right, left) using stack1. After traversing all nodes, it pops nodes from stack2 to print their data, resulting in a post-order traversal (left, right, root). The traversal continues until all nodes have been visited and both stacks are empty.

Here’s how the execution goes step by step:

1. Start with two empty stacks: Stack1 and Stack2. Initialize the current node as the root.
2. Push the root node onto Stack1.
3. While Stack1 is not empty, do the following: a. Pop the top node from Stack1 and push it onto Stack2. b. Push the left child onto Stack1 if it exists. c. Push the right child onto Stack1 if it exists.
4. Once Stack1 is empty, all nodes have been pushed onto Stack2. Pop nodes from Stack2 to get the post-order traversal.

Let’s execute the algorithm step by step:

1. Start with two empty stacks: Stack1 = [], Stack2 = [].
2. Push the root node (1) onto Stack1: Stack1 = [1].
3. Pop the top node from Stack1 (1) and push it onto Stack2: Stack2 = [1].
4. Push the right child (3) onto Stack1: Stack1 = [3].
5. Push the left child (2) onto Stack1: Stack1 = [3, 2].
6. Pop the top node from Stack1 (2) and push it onto Stack2: Stack2 = [1, 2].
7. Push the right child (5) onto Stack1: Stack1 = [3, 5].
8. Push the left child (4) onto Stack1: Stack1 = [3, 5, 4].
9. Pop the top node from Stack1 (4) and push it onto Stack2: Stack2 = [1, 2, 4].
10. Pop the top node from Stack1 (5) and push it onto Stack2: Stack2 = [1, 2, 4, 5].
11. Pop the top node from Stack1 (3) and push it onto Stack2: Stack2 = [1, 2, 4, 5, 3].
12. All nodes have been processed and pushed onto Stack2.
13. Pop nodes from Stack2 to get the post-order traversal: Output = [4, 5, 2, 3, 1].

The output of the traversal is: [4, 5, 2, 3, 1], which is the post-order traversal of the given binary tree.

Level order traversal of a Binary Tree in Java

In level order traversal, also known as breadth-first traversal, we visit each node level by level. To achieve this, we use a queue data structure. Initially, we add the root node to the queue. Then, we iterate while the queue is not empty.

During each iteration, we dequeue a node from the queue and assign it to the temp node. We print the data of this node. If the temp node has left and/or right children, we enqueue them into the queue. This ensures that we traverse the tree level by level, visiting each node before moving on to its children.

This approach is useful for applications like level-wise printing of a binary tree or finding the shortest path in a graph represented as a tree.

if (root == null) {
   return;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
  TreeNode temp = queue.poll();
  System.out.print(temp.data + " ");
  if (temp.left != null) {
    queue.offer(temp.left);
  }
  if (temp.right != null) {
    queue.offer(temp.right);
  }
}


// o/p : 1,2,3,4,5

This code performs a level-order traversal of the binary tree using a queue. It starts from the root node and adds it to the queue. Then, it repeatedly dequeues nodes from the queue, prints their data, and enqueues their left and right children if they exist. This process continues until all nodes in the tree have been visited.

Bonus: Binary Search in Java

Binary search in Java is a searching algorithm commonly applied to arrays or lists. It is used to find the position of a target value within a sorted array or list.

Binary trees, on the other hand, are a data structure consisting of nodes in a hierarchy, where each node has at most two children, referred to as the left and right child. Binary search trees (BSTs) are a specific type of binary tree where the values are stored in a sorted order, and each node’s value is greater than all values in its left subtree and less than all values in its right subtree.

While binary search and binary trees share the term “binary,” they are distinct concepts and are not directly related in terms of implementation. However, binary search trees leverage the principles of binary search to efficiently search, insert, and delete elements. The property of binary search trees ensures that searching for a value can be performed efficiently, similar to binary search in sorted arrays.

Here’s the explanation and execution of the binary search algorithm in Java

int low = 0;
int high = nums.length - 1;
while(low <= high) {
  int mid = (high + low) / 2;
  if(nums[mid] == key) {
    return mid;
  }

  if(key < nums[mid]) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
return -1;

In binary search, we look into the array until the low index becomes greater than the high index. We iterate until this condition holds true.

First, we find the mid index of the array using the formula (high + low) / 2.

If we find the key at the exact mid position, we return that mid index.

If the key is less than the value at the mid index, it means our key is in the first half of the array. So, we update high to mid - 1 and continue searching in that half.

If the key is greater than the value at the mid index, it means our key is in the right side of the array. So, we update low to mid + 1 and continue searching in that half.

If we don’t find the key in the array, we return -1, indicating that the key is not present in the array.

Let’s execute the algorithm step by step:

nums[]: 1, 10, 20, 47, 59, 65, 75, 88, 99
key: 65

low = 0, high = 8
Iteration 1:
  mid = (0 + 8) / 2 = 4
  nums[mid] = 59
  Since key (65) > nums[mid], update low = mid + 1 = 4 + 1 = 5

low = 5, high = 8
Iteration 2:
  mid = (5 + 8) / 2 = 6
  nums[mid] = 75
  Since key (65) < nums[mid], update high = mid - 1 = 6 - 1 = 5

low = 5, high = 5
Iteration 3:
  mid = (5 + 5) / 2 = 5
  nums[mid] = 65
  Since key (65) == nums[mid], return mid = 5 (key found at index 5)

Key 65 found at index 5 in the array.

Code

public class BinarySearch {
   
  public int binarySearch(int[] nums, int key) {
     int low = 0;
     int high = nums.length - 1;
     while (low <= high) {
       int mid = (high + low) / 2;
       if (nums[mid] == key) {
          return mid;
       }
       if (key < nums[mid]) {
          high = mid - 1;
       } else {
          low = mid + 1;
       }
    }
    return -1;
  }

  public static void main(String[] args) {
     BinarySearch bs = new BinarySearch();
     int[] nums = {1, 10, 20, 47, 59, 65, 75, 88, 99};
     int key = 65;
     System.out.println(bs.binarySearch(nums, key));
  }
}

This BinarySearch class implements the binary search algorithm to find the index of a key in a sorted array. The binarySearch method takes an array of integers (nums) and a key to search for. It initializes the low and high pointers to the start and end indices of the array, respectively. Then, it iteratively calculates the mid index, compares the key with the element at the mid index, and updates the low and high pointers accordingly based on whether the key is smaller or larger than the mid element. If the key is found, the method returns the index of the key; otherwise, it returns -1. The main method demonstrates how to use the binarySearch method to search for a key in a sorted array and prints the index of the key.

Conclusion

Binary trees are powerful data structures that offer efficient storage and retrieval of hierarchical data. Understanding their implementation and traversal algorithms is crucial for any Java programmer. By mastering binary trees, you’ll be equipped to tackle a wide range of programming challenges that involve hierarchical data representation and manipulation.

Doubly Linked Lists are a fundamental data structure in computer science, particularly in Java programming. They offer efficient insertion, deletion, and traversal operations compared to other data structures like arrays or singly linked lists. In this blog, we’ll delve into the concept of doubly linked lists, their implementation in Java, and explore some common operations associated with them.

What is a Doubly Linked List?

A Doubly Linked List is a type of linked list where each node contains a data element and two references or pointers: one pointing to the next node in the sequence, and another pointing to the previous node. This bidirectional linkage allows traversal in both forward and backward directions, making operations like insertion and deletion more efficient compared to singly linked lists.

Each node in a doubly linked list typically has the following structure:

class Node {
    int data;
    Node prev;
    Node next;
}

Here, data represents the value stored in the node, prev is a reference to the previous node, and next is a reference to the next node.

How to represent Doubly Linked List in java?

Doubly Linked List:

1. It is called a two-way linked list.
2. Given a node, we can navigate the list in both forward and backward directions, which is not possible in a singly linked list.
3. In a singly linked list, a node can only be deleted if we have a pointer to its previous node. However, in a doubly linked list, we can delete the node even if we don’t have a pointer to its previous node.
4. ListNode in a Doubly Linked List:

<------| previous | data | next |------->

In this visual representation:

• <------ indicates the direction of the previous pointers.
• |prev| represents the pointer to the previous node.
• |data| represents the data stored in the node.
• |next| represents the pointer to the next node.
• -------> indicates the direction of the next pointers.

Each node in the doubly linked list contains pointers to both the previous and next nodes, allowing bidirectional traversal.

ListNode in a Doubly Linked List:

public class ListNode {
    int data;
    ListNode previous;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
    }
}

Doubly Linked List:

null <-----head-----> 1 <-------> 10 <-------> 15 <-------> 65 <------tail-----> null

Doubly Linked List node has two pointers: previous and next. The list has two pointers:

• head points to the first node.
• tail points to the last node of the list.

How to implement Doubly Linked List in java ?

public class DoublyLinkedList {
  private ListNode head;
  private ListNode tail;
  private int length;

  private class ListNode {
    private int data;
    private ListNode next;
    private ListNode previous;

    public ListNode(int data) {
       this.data = data;
    }
  }

  public DoublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  public boolean isEmpty() {
    return length == 0;    // head == null
  }

  public int length() {
    return length;
  }
}

This Java class DoublyLinkedList defines a doubly linked list. It includes inner class ListNode for representing each node in the list. The class provides methods to check if the list is empty and to get the length of the list. The constructor initializes the head and tail pointers to null and sets the length to 0.

Common Operations of Doubly Linked List in java

Here are some common operations performed on a doubly linked list:

1. Insertion: Elements can be inserted at the beginning, end, or at any specific position within the list.
2. Deletion: Elements can be deleted from the list based on their value or position.
3. Traversal: Traversing the list from the beginning to the end or vice versa.
4. Search: Searching for a specific element within the list.
5. Reverse: Reversing the order of elements in the list.

How to print elements of Doubly Linked List in java?

null<-----head------> 1 <-------> 10 <-------> 15 <-------> 25 <------tail------>null

Here, we use two algorithms to print data:

i) It will start from the head and print data until the end, i.e., Forward Direction.

ii) It will start from the tail and print data until the end, i.e., Backward Direction.

Forward Direction Print

ListNode temp = head;
while(temp != null)
{
   System.out.print(temp.data + "-->");
   temp = temp.next;
}
System.out.println("null");

Here, we use a temporary node for traversing purposes. We assign the head node to it, i.e., ListNode temp = head;. Next, we move until the end of the list from the head. While traversing, we print data, and when we reach the end, our while loop terminates. That’s why we need to print ‘null’ on the next line.

Output: 1–>10–>15–>25–>null

Code

public void displayForward() {
  if (head == null) {
    return;
  }
   
  ListNode temp = head;
  while (temp != null) {
    System.out.print(temp.data + "-->");
    temp = temp.next;
  }
  System.out.println("null");
}

This method displayForward is designed to print the elements of the doubly linked list in the forward direction. It starts from the head node and traverses the list, printing the data of each node followed by an arrow (-->). Finally, it prints null to indicate the end of the list. If the list is empty (i.e., head is null), the method simply returns without performing any operation.

Backward Direction Print

ListNode temp = tail;
while(temp != null)
{
  System.out.print(temp.data + "-->");
  temp = temp.previous;
}
System.out.println("null");

Here, we use a temporary node for traversing purposes. We assign the tail node to it, i.e., ListNode temp = tail;. Next, we move back until the end of the list from the tail. While traversing, we print data, and when we reach the end, our while loop terminates. That’s why we need to print ‘null’ on the next line.

Output: 25 –> 15 –> 10 –> 1 –> null

Code

public void displayBackward() {
   if (tail == null) {
      return;
   }

   ListNode temp = tail;
   while (temp != null) {
      System.out.print(temp.data + "-->");
      temp = temp.previous;
   }
   System.out.println("null");  
}

This method displayBackward is designed to print the elements of the doubly linked list in the backward direction. It starts from the tail node and traverses the list, printing the data of each node followed by an arrow (-->). Finally, it prints null to indicate the end of the list. If the list is empty (i.e., tail is null), the method simply returns without performing any operation.

How to insert node at the beginning of Doubly Linked List?

ListNode newNode = new ListNode(value);
if(isEmpty())
{
   tail = newNode;
}
else
{
   head.previous = newNode;
}

newNode.next = head;
head = newNode;
length++; // as we inserted node successfully increase the length by one

Here, the head node plays a major role, while the tail node is only considered when the list node is empty. At that time, both head and tail point to null. So when we insert a new node, we assign it to the tail. At that time, the new node’s previous and next pointers point to null, and both head and tail point to that new node. But the next time when our list contains nodes, how do we insert at the beginning?

Inserting at the beginning means we need to assign newNode to the head’s previous pointer so that the new node will be before the head node. Still, the new node’s next pointer needs to be assigned to the head so that a two-way connection is built between every node.

Finally, we have successfully inserted the new node at the beginning. Our head should point to the new node, so we update it accordingly. However, our tail remains the same at the last node only.

Output:

null<---|previous|10|next|<------->|previous|1|next|---->null // here head --> 10 and tail --> 1

Code

public void insertFirst(int value) {
   ListNode newNode = new ListNode(value);
   if (isEmpty()) {
      tail = newNode;
   } else {
      head.previous = newNode;
   }
   newNode.next = head;
   head = newNode;
   length++;
}

This method insertFirst is designed to insert a new node with the given value at the beginning of the doubly linked list. If the list is empty, the new node becomes both the head and the tail of the list. Otherwise, the new node is inserted before the current head node, and its next reference is updated to point to the current head node. Finally, the length of the list is incremented.

How to insert node at the end of a Doubly Linked List in Java?

ListNode newNode = new ListNode(value);
if(isEmpty())
{
  head = newNode;
}
else
{
  tail.next = newNode;
  newNode.previous = tail;
}
tail = newNode;

The logic is similar to the insertion at the beginning. Here, the tail pointer plays a major role as it points to the end of the list. When the list is empty, both head and tail will point to null. Now, we create a new node with the given value, but its previous and next pointers point to null. So, when the list is empty and we add a new node at the end of the list, it means we only need to point head and tail to the new node. But from the next insertion onward, adjacent nodes will point to each other, maintaining the two-way nature of the main doubly linked list. Therefore, we will add the new node to the tail node’s next pointer, and the new node’s previous pointer will point to the tail node. Here, the head remains the same, only the tail will change every time.

Finally, after every successful insertion, we need to increment the length by 1.

Output: 

null<-----|previous|1|next|<--------->|previous|10|next|------>null // here head --> 1 and newNode & tail --> 10

Code

public void insertLast(int value) {
   ListNode newNode = new ListNode(value);
   if (isEmpty()) {
      head = newNode;   // If the list is initially empty, assign the new node to the head
   } else {
      // Establish two-way connection between the new node and the current tail node
      tail.next = newNode;
      newNode.previous = tail;
   }
   tail = newNode;     // Update the tail to point to the new node
   length++;           // Increment the length of the list by 1
}

This method insertLast is designed to insert a new node with the given value at the end of the doubly linked list. If the list is initially empty, the new node becomes the head of the list. Otherwise, it establishes a two-way connection between the new node and the current tail node, and updates the tail pointer to point to the new node. Finally, it increments the length of the list by 1.

How to delete first node in doubly linked list in java ?

//Sample Input: 

null<---|previous|1|next|<------>|previous|10|next|<-------->|previous|15|next|--->null      // here head --> 1 and tail --> 15

if(isEmpty())
{
   throw new NoSuchElementException();
}
ListNode temp = head;
if(head == tail)
{
   tail = null;
}
else
{
   head.next.previous = null;
}
head = head.next;
temp.next = null;
length--;
return temp;

Here, the tail will not play any major role because it is at the end of the list, and we want to delete the first node. So, the head will play a major role in this case. We assign the head node to the temporary node ‘temp’ because we want to delete the first node.

If the list has only one node, which is also the last node, it means head and tail should point to the same value. In such cases, the tail will be assigned with null, and the head will move to the next pointer, which may also be null. Additionally, we assign null to the temp’s next node, and return the temp node. Furthermore, we need to reduce the length by 1.

If the list has more than one node, we first move to the head’s next node and then remove its previous node. Then, we change the head to the next node so that we remove the head node. Using the statement ‘temp.next = null;’, we remove the head node and return it. Additionally, we need to reduce the length by 1.

Code

public ListNode deleteFirst() {
     if (isEmpty()) {
         throw new NoSuchElementException();
     }
     ListNode temp = head;
     if (head == tail) {
       tail = null;
     } else {
       head.next.previous = null;
     }
     head = head.next;
     temp.next = null;
     length--;
     return temp;
}

This method deleteFirst is designed to delete the first node of the doubly linked list and return the deleted node. If the list is empty, it throws a NoSuchElementException. Otherwise, it removes the head node from the list. If the list contains only one node (head and tail are the same), it sets the tail to null. Otherwise, it updates the previous reference of the next node after the head to null. Finally, it updates the head pointer to the next node, decrements the length of the list, and returns the deleted node.

How to delete last node in Doubly Linked List in java ?

if(isEmpty())
{
  throw new NoSuchElementException();
}
ListNode temp = tail;
if(head == tail)
{
   head = null;
}
else
{
   tail.previous.next = null;
}
tail = tail.previous;
temp.previous = null;
length--;
return temp;

If the list is empty, we throw a NoSuchElementException.

When the list contains only one node, at that time, both head and tail point to the same node. Here, only head will play a major role; elsewhere, the tail plays an important role. To delete the last node in this case, we assign null to head, and the tail’s previous will become the new tail. Then, we delete the tail and return it.

When the list contains more than one node, we delete the connection between two adjacent nodes. We move to the tail’s previous node, then back to the next node and assign null to it. Next, we move our current tail to its previous node, and finally, we remove the connection between the tail and its previous node by setting temp.previous to null. We then return the last node.

Code

public ListNode deleteLast() {
    if (isEmpty()) {
        throw new NoSuchElementException();
    }
    ListNode temp = tail;
    if (head == tail) {
        head = null;
    } else {
        tail.previous.next = null;
    }
    tail = tail.previous;
    temp.previous = null;
    length--;
    return temp;
}

This method deleteLast is designed to delete the last node of the doubly linked list and return the deleted node. If the list is empty, it throws a NoSuchElementException. Otherwise, it removes the tail node from the list. If the list contains only one node (head and tail are the same), it sets the head to null. Otherwise, it updates the next reference of the previous node of the tail to null. Finally, it updates the tail pointer to the previous node, decrements the length of the list, and returns the deleted node.

Advantages of Doubly Linked Lists

Doubly linked lists offer several advantages over other data structures:

1. Bidirectional traversal: Unlike singly linked lists, where traversal is only possible in one direction, doubly linked lists allow traversal in both forward and backward directions.
2. Efficient insertion and deletion: Insertion and deletion operations can be performed more efficiently in doubly linked lists since only the adjacent nodes need to be updated.
3. Dynamic size: Doubly linked lists can grow or shrink dynamically, allowing for efficient memory utilization.

Conclusion

Doubly linked lists are a versatile data structure that provides efficient operations for dynamic storage and retrieval of data. Understanding their implementation and common operations is essential for any Java programmer. By utilizing the bidirectional traversal and efficient insertion/deletion capabilities, doubly linked lists offer an excellent alternative to arrays or singly linked lists in various programming scenarios.

Linked lists are a fundamental data structure in computer science, offering flexibility and efficiency in managing collections of data. Among the variations of linked lists, the circular linked list stands out for its unique structure and applications. In this blog post, we’ll delve into the concept of circular linked lists, explore their implementation in Java, and discuss their advantages and use cases.

Understanding Circular Linked Lists

A circular linked list is similar to a regular linked list, with the key distinction being that the last node points back to the first node, forming a circle. Unlike linear linked lists, which have a NULL pointer at the end, circular linked lists have no NULL pointers within the list itself. This circular structure allows for traversal from any node to any other node within the list.

The basic components of a circular linked list include:

• Node: A unit of data that contains both the data value and a reference (pointer) to the next node in the sequence.
• Head: A reference to the first node in the list. In a circular linked list, this node is connected to the last node, forming a circle.
• Tail: Although not always explicitly maintained, it refers to the last node in the list, which points back to the head.

How to represent a circular singly linked list in java?

A Circular Singly Linked List is similar to a singly linked list, with the difference that in a circular linked list, the last node points to the first node and not null. Instead of keeping track of the head, we keep track of the last node in the circular singly linked list.

For example:

In a Singly Linked List:

head –> 1 –> 8 –> 10 –> 16 –> null

In a Circular Singly Linked List:

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

last –> 16 –> 1 –> 8 –> 10 –> 16 // Please refer to the actual diagram for clarification.

We can insert nodes at both the end and beginning with constant time complexity.

How to implement a Circular Singly Linked List in a java ?

public class CircularSinglyLinkedList {

  private ListNode last;        // Keep track of the last node of the circular linked list   
  private int length;           // Hold the size of the circular singly list

  private class ListNode {
    private int data;
    private ListNode next;

    public ListNode(int data) {
       this.data = data;
    }
  }

  public CircularSinglyLinkedList() {
    last = null;       // When we initialize the circular singly linked list, we know the last points to null and that time the list is empty 
    length = 0;        // So the length is also 0;
  }

  // Gives the size of the circular singly linked list 
  public int length() {
    return length;
  }

  // Check whether the circular list is empty or not 
  public boolean isEmpty() {
    return length == 0;
  }


  public void createCircularLinkedList() {
    ListNode first = new ListNode(1);
    ListNode second = new ListNode(5);
    ListNode third = new ListNode(10);
    ListNode fourth = new ListNode(15);
 
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = first;      // Here we make the list in circular nature by assigning the first node 

    last = fourth;         // Last node points to the fourth node
  }


  public static void main(String[] args) {
     CircularSinglyLinkedList csll = new CircularSinglyLinkedList();
     csll.createCircularLinkedList();
  }
}

This Java class CircularSinglyLinkedList defines a circular singly linked list. It includes inner class ListNode for representing each node in the list. The class provides methods to create a circular linked list, check its length, and check whether it is empty. The main method demonstrates creating a circular linked list instance and initializing it.

How to traverse and print a circular linked list in java ?

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

Algorithm & Execution

if (last == null) {
    return;
}
ListNode first = last.next;
while (first != last) {
    System.out.println(first.data + "");
    first = first.next;
}
System.out.println(first.data + "");

The basic idea here is to find the first node using the last node, and then traverse the list from the first node to the last node. When the first node equals the last node, at that point, we are at the last node, but our while loop terminates, so we couldn’t print the last node’s data. That’s why we print it separately after the loop.

Code

public void display() {
   if (last == null) {
      return;
   }
   ListNode first = last.next;
   while (first != last) {
     System.out.println(first.data + "");
     first = first.next;
   }
   System.out.println(first.data + "");
}

This method display is designed to print the elements of the circular singly linked list. It starts from the first node, which is the node after the last node. Then, it traverses the list until it reaches the last node, printing the data of each node. Finally, it prints the data of the last node itself. If the list is empty (i.e., last is null), the method simply returns without performing any operation.

How to insert node at the beginning of a circular Singly Linked List in java ?

ListNode temp = new ListNode(data);
if (last == null) {
    last = temp;
} else {
    temp.next = last.next;
}
last.next = temp;
length++;

1. We create a temporary node (temp) which we will insert at the beginning of the circular list.
2. If the last node is null, it means our list is empty. In this case, we assign the temp node to be the last node. Both last and temp now point to the same new node we inserted. We update the last.next pointer to point to temp, forming the circular nature for the first node.
3. If the list is not empty (last is not null), we create a new temp node with the given data, and it points to null initially. Then, we update temp.next to point to last.next, so it will be added at the beginning of the last node. Even now, last and temp.next will point to the last node. We need to update the last node’s next pointer to temp so that the circular list nature remains intact.
4. Finally, we increment the length by 1 because every time we add a new node at the beginning of the last node.

Code

public void insertFirst(int data) {
  ListNode temp = new ListNode(data);
  if (last == null) {
      last = temp;
  } else {
      temp.next = last.next;
  }
  last.next = temp;
  length++;
}

This method insertFirst is designed to insert a new node with the given data at the beginning of the circular singly linked list. If the list is empty (i.e., last is null), the new node becomes both the first and last node. Otherwise, the new node is inserted after the last node, and its next reference is updated to point to the node originally after the last node. Finally, the length of the list is incremented.

How to insert node at the end of a circular singly linked list in Java?

ListNode temp = new ListNode(data);
if (last == null) {   // list is empty
   last = temp;
   last.next = last;
} else {              // if list is non-empty
   temp.next = last.next;
   last.next = temp;
   last = temp;
}
length++;

1. First, we create a new temporary node (temp) with the given data value.
2. Initially, the circular list is empty, so last will point to null, i.e., last --> null.
3. When we insert a new node, we check whether we are inserting into an empty list or a non-empty list.
4. If the list is empty, we point last to our temporary node, i.e., last = temp.
5. To create a circular structure, we need to make last.next point to last itself, i.e., last.next = last.
6. After that, we increment the length by 1 as we successfully inserted a new node into the list.
7. Now, let’s consider the scenario of a non-empty circular list. In this case, first, we assign last.next to the last node itself when there is only one node. If there is more than one node, then last.next will point to the first node, and temp.next will point to null.
8. Then, we attach the new temporary node to the end by assigning it as last.next. Previously, it pointed to itself because there was only one node. If there are more than one node, it will point to the temp node because the last node becomes the first, and temp will always become the last node to maintain the circular chain nature.
9. Finally, temp becomes our new last because it is added at the end.

So, the basic logic is to add the temporary node at the end and always make that newly inserted node the last one.

How to remove first node from a circular singly linked list in java ?

if (isEmpty()) {
   throw new NoSuchElementException();
}
ListNode temp = last.next;
if (last.next == last) {
   last = null;
} else {
   last.next = temp.next;
}
temp.next = null;
length--;
return temp;

1. If the list is empty, meaning there are no elements to remove, we throw a NoSuchElementException.
2. We create a temporary node temp which will store the node to be removed, i.e., the first node (last.next).
3. If last.next points to last itself, it means there is only one node in the list. In this case, we remove the last node by assigning null to last.
4. If last.next doesn’t point to last, it means there are multiple nodes in the list. We remove the first node by updating last.next to point to the second node (temp.next).
5. We then set temp.next to null to detach temp from the list.
6. We decrement the length of the list by 1 since we have successfully removed a node.
7. Finally, we return the removed node temp.

So, the main logic is to remove the first node by adjusting pointers and then returning the removed node.

Advantages of Circular Linked Lists

Circular linked lists offer several advantages over their linear counterparts:

1. Efficient Insertion and Deletion: Insertion and deletion operations can be performed quickly, especially at the beginning or end of the list, as there’s no need to traverse the entire list.
2. Circular Traversal: With a circular structure, traversal from any point in the list to any other point becomes straightforward.
3. Memory Efficiency: Circular linked lists save memory by eliminating the need for a NULL pointer at the end of the list.

Use Cases of Circular Linked Lists

Circular linked lists find applications in various scenarios, including:

• Round-Robin Scheduling: In operating systems, circular linked lists are used to implement round-robin scheduling algorithms, where tasks are executed in a circular order.
• Music and Video Playlists: Circular linked lists can be used to implement circular playlists, allowing seamless looping from the last item to the first.
• Resource Management: In resource allocation systems, circular linked lists can represent a pool of resources where allocation and deallocation operations are frequent.

Conclusion

Circular linked lists provide an elegant solution to certain problems by leveraging their circular structure and efficient operations. In Java, implementing a circular linked list involves managing node connections carefully to maintain the circular property. Understanding the strengths and applications of circular linked lists can aid in designing efficient algorithms and data structures for various computational tasks.

Singly linked lists are versatile data structures that offer efficient insertion, deletion, and traversal operations. However, beyond the basic CRUD (Create, Read, Update, Delete) operations, there lies a realm of logical operations that can be performed on singly linked lists. In this detailed blog, we’ll explore some of the most important logical operations that can be applied to singly linked lists in Java, providing insights into their implementation and usage.

How to search an element in a Singly Linked List in Java?

head –> 10 –> 8 –> 1 –> 11 –> null

ListNode current = head;
while(current != null)
{
  if(current.data == searchKey)
  {
    return true;
  }
  current = current.next;
}
return false;

As the main logic, we need to traverse the list node by node. While traversing, we check each node’s data. If it matches the search key, then we’ve found the key; otherwise, we haven’t found it.

1. We create a temporary node current to traverse the list until the end. Initially, it’s set to the head node, i.e., ListNode current = head.
2. Using a while loop, we traverse until the end of the list. If current becomes null, it means we’ve reached the end, and we terminate the loop. During traversal, we check each node’s data with the search key. If we find a match, we return true immediately and exit the loop.

while( current  != null )
{
  if(current.data == searchKey)
  {
   return true;
  }
  current = current.next;      // Move to the next node in each iteration 
}

1. Finally, if we haven’t found the exact search key after traversing the entire list, we return false.

Output:

• If the search key is 1, then it is found.
• If the search key is 12, then it is not found.

Code

public boolean find(ListNode head, int searchKey) {
  if (head == null) {
    return false;
  }

  ListNode current = head;
  while (current != null) {
    if (current.data == searchKey) {
      return true;
    }
    current = current.next; // Move to the next node
  }
  return false;
}