Amol Pawar

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.

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;
}

This method find is designed to search for a specific key value (searchKey) within the linked list. It returns true if the key is found, and false otherwise. If the list is empty (i.e., head is null), it immediately returns false. Otherwise, it traverses the list, comparing the data value of each node (current.data) with the search key. If a match is found, it returns true. If the end of the list is reached without finding the key, it returns false.

How to reverse a singly linked list in java

Input:

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

Output:

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

ListNode current = head;
ListNode previous = null;
ListNode next = null;
while(current != null)
{
  next = current.next;
  current.next = previous;
  previous = current;
  current = next;
}
return previous;

The main logic is to traverse the list until the end and apply a logic that reverses the pointing of each node. Ultimately, we obtain the reversed list.

1. We create three temporary nodes:
   • current points to head.
   • previous initially points to null.
   • next also initially points to null.
2. We traverse the list node by node using a while loop. The loop iterates until current becomes null.
3. In each iteration of the while loop, we perform the following operations:

while(current != null)
{
   next = current.next;        // Store the reference to the next node
   current.next = previous;    // Reverse the pointing direction of the current node
   previous = current;         // Move forward: previous becomes current
   current = next;             // Move forward: current becomes next
}

1. • First, we move to the next node by assigning next to current.next.
   • Second, we reverse the reference of the current node to point to the previous node.
   • Third, we update previous to be the current node, preparing for the next iteration.
   • Finally, we move forward by assigning next to current.
   This process effectively reverses the pointing direction of each node in the list.
2. When the while loop terminates, we have reversed the entire list, and the last previous node becomes the new head of the list. So, we return previous.

Output: head --> 11 --> 1 --> 8 --> 10 --> null.

After the reversal, the list becomes reversed.

Code

public ListNode reverse(ListNode head)
{
   if(head == null)
   {
      return head;
   }
   
   ListNode current = head;
   ListNode previous = null;
   ListNode next = null;

   while(current != null)
   {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
   }
   return previous;
}

This method reverse is designed to reverse the linked list. If the list is empty (i.e., head is null), it immediately returns null. Otherwise, it iterates through the list, changing the next pointer of each node to point to the previous node. At the end of the iteration, it returns the last node encountered, which becomes the new head of the reversed list.

How to find middle node in singly linked list in java ?

To find the middle node in a singly linked list, we employ the same logic for two different cases.

Case 1: List having an even number of nodes:

For example, head –> 10 –> 8 –> 1 –> 11 –> null

In this case, the middle node is 1.

Case 2: List having an odd number of nodes:

For example, head –> 10 –> 8 –> 1 –> 11 –> 15 –> null

Here again, the middle node is 1.

ListNode slowPtr = head;
ListNode fastPtr = head;
while(fastPtr != null && fastPtr.next != null) {
    slowPtr = slowPtr.next;      // Move slow pointer to the next node
    fastPtr = fastPtr.next.next; // Move fast pointer to two nodes ahead
}
return slowPtr; // Return the slow pointer, which points to the middle node

The main logic involves using two different pointers: a slow pointer and a fast pointer. The slow pointer moves to the next node one by one, while the fast pointer moves two nodes ahead at a time. When the fast pointer reaches the end (either pointing to null or its next points to null), the while loop terminates, and we return the slow pointer, which represents the middle node in both cases.

Code

public ListNode getMiddleNode() {
    if (head == null) {
      return null;
    }
    
    ListNode slowPtr = head;
    ListNode fastPtr = head;
 
    while (fastPtr != null && fastPtr.next != null) {
       slowPtr = slowPtr.next;
       fastPtr = fastPtr.next.next;
    }
    return slowPtr;
}

This method getMiddleNode is designed to find and return the middle node of the linked list. It initializes two pointers, slowPtr and fastPtr, both starting at the head of the list. The slowPtr moves one node at a time while the fastPtr moves two nodes at a time. When the fastPtr reaches the end of the list (or null), the slowPtr will be at the middle node. If the list is empty (i.e., head is null), it returns null.

How to detect a loop in Singly Linked List in java ?

In a given singly linked list, if there exists a loop, it can be identified by employing the following logic.

Consider the linked list: head –> 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 3

As it can be seen, the list loops back to the node with value 3.

The main logic remains the same as before: we use two different pointers, a slow pointer and a fast pointer. However, in this case, we move the fast pointer first, followed by the slow pointer. Due to the loop, these pointers will eventually meet at the same node. Once the slow and fast pointers are equal, pointing to the same node, we can conclude that there exists a loop in the linked list. If the pointers never meet, then the list does not contain any loop.

ListNode fastPtr = head;
ListNode slowPtr = head;
while(fastPtr != null && fastPtr.next != null) {
    fastPtr = fastPtr.next.next; // Move fast pointer two nodes ahead
    slowPtr = slowPtr.next;      // Move slow pointer one node ahead
    if(slowPtr == fastPtr) {     // If slow pointer meets fast pointer, it indicates a loop
        return true;
    }
}
return false; // If loop termination condition is met without meeting points, return false

The main logic is the same as before: we use two pointers, a slow pointer and a fast pointer, to traverse the list. However, in this case, we move the fast pointer two nodes ahead and the slow pointer one node ahead in each iteration. If the pointers meet at any point during traversal, it indicates the presence of a loop in the list, and we return true. If the loop termination condition is met without the pointers meeting, it means there is no loop in the list, and we return false.

Code

public boolean containsLoop() {
  ListNode fastPtr = head;
  ListNode slowPtr = head;

  while (fastPtr != null && fastPtr.next != null) {
    fastPtr = fastPtr.next.next;        // We need to move fast pointer fast so that it will catch the slow pointer if a loop is present   
    slowPtr = slowPtr.next;
   
    if (slowPtr == fastPtr) {
      return true;
    }
  }
  return false;
}

public void createALoopInLinkedList() {
  ListNode first = new ListNode(1);  
  ListNode second = new ListNode(2);
  ListNode third = new ListNode(3);
  ListNode fourth = new ListNode(4);
  ListNode fifth = new ListNode(5);
  ListNode sixth = new ListNode(6);

  head = first;
  first.next = second;
  second.next = third;
  third.next = fourth;
  fourth.next = fifth;
  fifth.next = sixth;
  sixth.next = third;
}

The method containsLoop checks whether a loop exists in the linked list using Floyd’s Cycle Detection Algorithm. It initializes two pointers, fastPtr and slowPtr, both starting at the head of the list. The fastPtr moves twice as fast as the slowPtr. If there is a loop in the list, eventually, the fastPtr will catch up with the slowPtr. If no loop is found, the method returns false.

The method createALoopInLinkedList is a helper method to create a loop in the linked list for testing purposes. It creates a linked list with six nodes and then creates a loop by making the next reference of the last node point to the third node.

How to find nth node from the end of a Singly Linked List in java?

Consider the singly linked list:

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

If we want to find the node that is “n” positions from the end of the list, where “n” is given as 2, then the node containing 11 would be that node.

ListNode mainPtr = head;  // It will move forward when the reference pointer covers the nth position forward from the head 
ListNode referencePtr = head;  // It will move twice: first, it covers the nth distance from the head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position
int count = 0;   // It is to track the number of nodes the reference pointer moved forward
while(count < n) {
    refPtr = refPtr.next;
    count++;
}
while(refPtr != null) {
    refPtr = refPtr.next;
    mainPtr = mainPtr.next;
}

return mainPtr;

The main logic involves using two pointers: a main pointer and a reference pointer. The reference pointer moves forward until it reaches the nth position from the head, while the main pointer remains stationary. After reaching the nth position, the reference pointer continues moving until it reaches the end of the list, while the main pointer moves along with it. When the reference pointer reaches the end of the list, the main pointer will be pointing to the nth node from the end of the list.

Code

public ListNode getNthNodeFromEnd(int n) {

 if (head == null) {
    return null;
 }
 
 if (n <= 0) {
     throw new IllegalArgumentException("Invalid value: n = " + n);
 }

 ListNode mainPtr = head;  // It will move forward when the reference pointer covers the nth position forward from the head  
 ListNode refPtr = head;   // It will move twice: first, it covers nth distance from head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position.

 int count = 0;   // It is to track the number of nodes refPtr moved forward

 while (count < n) {
  if (refPtr == null) {
      throw new IllegalArgumentException(n + " is greater than the number of nodes in the list");
  }

  refPtr = refPtr.next;
  count++;
 }

 while (refPtr != null) {
  refPtr = refPtr.next;
  mainPtr = mainPtr.next;
 }

 return mainPtr;    // The returned mainPtr will be at the nth position from the end of the list
}

This method getNthNodeFromEnd is designed to find and return the nth node from the end of the linked list. It initializes two pointers, mainPtr and refPtr, both starting at the head of the list. The refPtr moves forward n positions from the head. Then, both pointers move forward simultaneously until the refPtr reaches the end of the list. At this point, the mainPtr will be at the nth node from the end. If the list is empty or if the value of n is less than or equal to 0, the method throws an IllegalArgumentException.

How to remove duplicates from sorted Singly Linked List in java?

For the given input of a sorted linked list:

head –> 1 –> 1 –> 2 –> 3 –> 3 –> null

The desired output is a sorted linked list with duplicates removed:

head –> 1 –> 2 –> 3 –> null

ListNode current = head;
while(current != null && current.next != null) {
    if(current.data == current.next.data) {
        current.next = current.next.next; // Connect current to the next next node to remove the duplicate node
    } else {
        current = current.next; // Move to the next node if no duplicate is found
    }
}

The main logic involves traversing the list node by node using a current pointer. While traversing, we check whether the data of the current node is equal to the data of the next node. If they are equal, it means a duplicate node is found, so we connect the current node to the next next node, effectively removing the duplicate node between them. If no duplicate is found, we simply move to the next node. This process continues until we reach the end of the list or the current node becomes null.

Code

public void removeDuplicates() {
  
  if (head == null) {
    return;
  }

  ListNode current = head;

  while (current != null && current.next != null) {
     if (current.data == current.next.data) {
       current.next = current.next.next;
     } else {
       current = current.next;
     }
  }
}

This method removeDuplicates is designed to remove duplicates from a sorted linked list. It iterates through the list using the current pointer. If the current node’s data is equal to the data of the next node, it skips the next node by updating the next reference of the current node to skip the duplicate node. Otherwise, it moves the current pointer to the next node in the list. If the list is empty (i.e., head is null), the method returns without performing any operation.

Now, How to insert a node in a sorted Singly Linked List in java?

Given the sorted linked list:

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

And a new node:

newNode –> 11 –> null

We want to insert the new node (11) into the sorted list such that the sorting order remains the same.

After insertion, the updated list would be:

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

ListNode current = head;
ListNode previous = null;
while(current != null && current.data < newNode.data) {
    previous = current;
    current = current.next;
}
// When we reach the insertion point, we have references to current, previous, and newNode.
// Now, we rearrange the pointers so that previous points to newNode and newNode points to current.
newNode.next = current;
if (previous != null) {
    previous.next = newNode;
} else {
    // If previous is null, it means the newNode should become the new head.
    head = newNode;
}
return head;

The main logic involves traversing the sorted linked list until we find the appropriate position to insert the new node while maintaining the sorting order. We traverse the list node by node, comparing the data of each node with the data of the new node. We continue this process until we find a node whose data is greater than or equal to the data of the new node, or until we reach the end of the list.

When we reach the insertion point, we have references to three nodes: the current node, the previous node (the node before the insertion point), and the new node. To insert the new node into the list, we rearrange the pointers so that the previous node points to the new node, and the new node points to the current node.

If the previous node is null, it means that the new node should become the new head of the list. In this case, we update the head pointer to point to the new node.

Code

public ListNode insertInSortedList(int value) {
  ListNode newNode = new ListNode(value);
 
  if (head == null) {
    return newNode;
  }

  ListNode current = head;
  ListNode previous = null;

  while (current != null && current.data < newNode.data) {   // Will go till the end while checking the sorting order between the current node and the new node data 
     previous = current;
     current = current.next;
  }
  
  // When we reach the insertion point, we have our current, previous, and newNode references so we only need to arrange pointers.
  // So that previous will point to newNode and newNode will point to current.
 
  newNode.next = current;
  if (previous == null) { // If the new node is to be inserted at the beginning
    head = newNode;
  } else {
    previous.next = newNode;
  }
  
  return head;    
}

This method insertInSortedList is designed to insert a new node with the provided value into a sorted linked list. If the list is empty (i.e., head is null), the new node becomes the head of the list. Otherwise, it traverses the list to find the correct position to insert the new node while maintaining the sorted order. Once the insertion point is found, it updates the pointers to insert the new node. Finally, it returns the head of the list.

How to remove a given key from singly linked list in java?

Given the linked list:

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

Suppose our key is 11, and we want to remove it from the list.

After removal, the updated list would be:

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

ListNode current = head;
ListNode previous = null;

// Traverse the list to find the node with the key value
while(current != null && current.data != key) {
   previous = current;
   current = current.next;
}

// If we reached the end of the list without finding the key, return
if(current == null) {
  return;
}

// If we found the key, remove the node by adjusting the previous node's next reference
if(previous != null) {
  previous.next = current.next;
} else {
  // If the key is found at the head, update the head pointer to skip the current node
  head = current.next;
}

The main logic involves traversing the linked list until we find the node with the specified key value. While traversing, we keep track of the previous node as well.

If we reach the end of the list without finding the key, it means the key doesn’t exist in the list, so we return without performing any removal.

If we find the node with the key value, we remove it from the list by adjusting the next reference of the previous node to skip over the current node. However, if the key is found at the head of the list, we update the head pointer to skip over the current node.

Code

public void deleteNode(int key) {
 
  ListNode current = head;
  ListNode previous = null;

  // If we find our key at the first node that is head, just update head to point to the next node.
  if (current != null && current.data == key) {
     head = current.next;
     return;
  }

  while (current != null && current.data != key) {
    previous = current;
    current = current.next;
  }
 
  // If we reached the end of the list (current == null), the key was not found, so return without performing any operation.
  if (current == null) {
    return;
  }

  // If we found the key, update the next reference of the previous node to point to the next node of the current node, effectively removing the current node.
  previous.next = current.next;
}

This method deleteNode is designed to delete a node with the given key value from the linked list. It iterates through the list using the current pointer to find the node with the specified key value while keeping track of the previous node using the previous pointer. If the key is found at the first node (head), it updates the head to point to the next node. If the key is found in the middle of the list, it updates the next reference of the previous node to skip the current node. If the key is not found in the list, the method simply returns without performing any operation.

Bonus: Two Sum Problem in java

Problem: Given an array of integers, return the indices of the two numbers such that they add up to a specific target.

Example: Given array of integers: {2, 11, 5, 10, 7, 8}, and target = 9.

Solution: Since arr[0] + arr[4] = 2 + 7 = 9, we return {0, 4} as the indices.

The main logic involves using a map for fast lookup of stored values to find the exact sum of the target. We require one map for lookup purposes and one result array to store the indices of the two numbers that add up to the target sum from the given array. Here’s how it works:

1. We iterate through the array, examining each element.
2. At each element, we calculate the difference between the target and the current element.
3. We check if this difference exists in the map. If it does, it means we have found the two numbers that add up to the target.
4. We return the indices of the current element and the element with the required difference.
5. If the difference is not found in the map, we store the current element’s value along with its index in the map for future lookups.

Algorithm & Executions

int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();

for(int i = 0; i < numbers.length; i++) {
    int complement = target - numbers[i];
    if(map.containsKey(complement)) {
        result[0] = map.get(complement);
        result[1] = i;
        return result;
    }
    map.put(numbers[i], i);
}

return result;

The main logic involves using a hash map to store the indices of elements in the array. We traverse the array and, for each element, check if its complement (target – current number) exists in the hash map. If it does, it means we have found two numbers that add up to the target, so we return their indices. If not, we add the current number and its index to the hash map for future reference.

Code

public static int[] twoSum(int[] numbers, int target) {
  int[] result = new int[2];
  Map<Integer, Integer> map = new HashMap<>();
 
  for (int i = 0; i < numbers.length; i++) {
    if (!map.containsKey(target - numbers[i])) {
      map.put(numbers[i], i);
    } else {
      result[1] = i;
      result[0] = map.get(target - numbers[i]);
      return result;
    }     
  }

  throw new IllegalArgumentException("Two numbers not found");
}

This method twoSum is designed to find and return the indices of the two numbers in the numbers array that add up to the target value. It utilizes a hashmap to store the difference between the target and each element of the array along with its index. It iterates through the array, checking if the hashmap contains the difference between the target and the current element. If not, it adds the current element and its index to the hashmap. If it finds the difference in the hashmap, it retrieves the index of the other number and returns the indices as the result. If no such pair of numbers is found, it throws an IllegalArgumentException.

Note: Why is this Array Manipulation problem being discussed here?

While the problem of finding two numbers in an array that add up to a specific target is not directly related to singly linked list operations, the underlying logic and problem-solving techniques used in solving array manipulation problems can indeed be helpful in solving problems related to singly linked lists.

Many problem-solving techniques and algorithms used in array manipulation, such as iterating over elements, using hash maps for fast lookups, or employing two-pointer approaches, can also be applied to singly linked list problems. Additionally, understanding how to efficiently manipulate data structures and analyze patterns in data is a fundamental skill that can be transferred across various problem domains.

In the context of computer science and algorithmic problem-solving, building a strong foundation in problem-solving techniques through various types of problems, including those involving arrays, linked lists, trees, graphs, and more, can enhance your ability to tackle a wide range of problems effectively.

So, while the specific problem discussed may not directly relate to singly linked lists, the problem-solving skills and techniques learned from array manipulation problems can certainly be beneficial in solving problems related to singly linked lists and other data structures.

Conclusion

By mastering the logical operations of singly linked list in Java, programmers can unlock the full potential of this versatile data structure. Whether it’s searching, reversing, merging, or detecting loops, understanding these operations equips developers with powerful tools for solving complex problems and building efficient algorithms. With the insights provided in this blog, programmers can elevate their skills and become more proficient in leveraging singly linked lists for various applications.

Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and efficient insertion and deletion operations. In Java, linked lists are commonly used for various applications due to their flexibility and versatility. In this blog post, we will explore linked lists in Java in detail, covering their definition, types, operations, and implementation.

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: the data, which holds the value of the element, and a reference (or link) to the next node in the sequence. Unlike arrays, which have fixed sizes, linked lists can dynamically grow and shrink as elements are added or removed.

Key Concepts

• Node: The fundamental building block of a linked list. Each node consists of:
  • Data: The actual information you store (e.g., integer, string).
  • Next pointer: References the next node in the list.
  • Previous pointer (for doubly-linked lists): References the preceding node, enabling bidirectional traversal.
• Head: The starting point of the list, pointing to the first node.
• Tail: In singly-linked lists, points to the last node. In doubly-linked lists, points to the last node for forward traversal and the first node for backward traversal.

Types of Linked Lists

1. Singly Linked List

In a singly linked list, each node has only one link, which points to the next node in the sequence. Traversal in a singly linked list can only be done in one direction, typically from the head (start) to the tail (end) of the list. Singly-linked lists are relatively simple and efficient in terms of memory usage.

2. Doubly Linked List

In a doubly linked list, each node has two links: one points to the next node, and the other points to the previous node. This bidirectional linking allows traversal in both forward and backward directions. Doubly linked lists typically require more memory per node due to the additional reference for the previous node.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circular structure. Circular linked lists can be either singly or doubly linked and are useful in scenarios where continuous looping is required.

How to represent a LinkedList in Java ?

Now we know that, A linked list is a data structure used for storing a collection of elements, objects, or nodes, possessing the following properties:

1. It consists of a sequence of nodes.
2. Each node contains data and a reference to the next node.
3. The first node is called the head node.
4. The last node contains data and points to null.

| data | next | ===> | data | next | ===> | data | next | ===> null

Implementation Of a Node in a linked list

Generic Type Implementation

public class ListNode<T> {
    private T data;
    private ListNode<T> next;
}

In the generic type implementation, the class ListNode<T> represents a node in a linked list that can hold data of any type. The line public class ListNode<T> declares a generic class ListNode with a placeholder type T, allowing flexibility for storing different data types. The private member variable data of type T holds the actual data stored in the node, while the next member variable is a reference to the next node in the linked list, indicated by ListNode<T> next. This design enables the creation of linked lists capable of storing elements of various types, offering versatility and reusability.

Integer Type Implementation

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

In contrast to the generic type, the integer type implementation, represented by the class ListNode, is tailored specifically for storing integer data. The class ListNode does not use generics and defines a private member variable data of type int to hold integer values within each node. Similarly, the next member variable is a reference to the next node in the linked list, indicated by ListNode next. This implementation is more specialized and optimized for scenarios where the linked list exclusively stores integer values, potentially offering improved efficiency due to reduced overhead from generics.

Node Diagram

| data | next |===>

This node diagram depicts the structure of each node in the linked list. Each node consists of two components: data, representing the value stored in the node, and next, a pointer/reference to the next node in the sequence. The notation | data | next |===> illustrates this structure, where data holds the value of the node, and next points to the subsequent node in the linked list. The arrow (===>) signifies the connection between nodes, indicating the direction of traversal from one node to another within the linked list.

Representation of Linked List

head ===> |10| ===> |8| ===> |9| ===> |11| ===> null

The representation of the linked list illustrates a sequence of nodes starting from the head node. Each node contains its respective data value, with arrows (===>) indicating the connections between nodes. The notation head ===> |10| ===> |8| ===> |9| ===> |11| ===> null shows the linked list structure, where head denotes the starting point of the list. The data values (10, 8, 9, 11) are enclosed within nodes, and null signifies the end of the linked list. This representation visually demonstrates the organization and connectivity of nodes within the linked list data structure.

Code Implementation

public class LinkedList
{

  private ListNode head; // head node to hold the list
  
  // It contains a static inner class ListNode
  private static class ListNode
  {
     private int data;
     private ListNode next;

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

  public static void main(String[] args)
  {
   
  }
}

The above code snippet outlines the structure of a linked list in Java. The LinkedList class serves as the main container for the linked list, featuring a private member variable head that points to the first node. Within this class, there exists a static inner class named ListNode, which defines the blueprint for individual nodes. Each ListNode comprises an integer data field and a reference to the next node. The constructor of ListNode initializes a node with the given data and sets the next reference to null by default. The main method, though currently empty, signifies the program’s entry point where execution begins. It provides a foundational structure for implementing linked lists, enabling the creation and manipulation of dynamic data structures in Java programs.

Common Operations on Linked Lists

We will see each operation in much detail in the next article, where we will discuss Singly Linked Lists in more detail. Right now, let’s see a brief overview of each operation:

1. Insertion

Insertion in a linked list involves adding a new node at a specified position or at the end of the list. Depending on the type of linked list, insertion can be performed efficiently by updating the references of adjacent nodes.

2. Deletion

Deletion involves removing a node from the linked list. Similar to insertion, deletion operations need to update the references of adjacent nodes to maintain the integrity of the list structure.

3. Traversal

Traversal refers to visiting each node in the linked list sequentially. Traversal is essential for accessing and processing the elements stored in the list.

4. Searching

Searching involves finding a specific element within the linked list. Linear search is commonly used for searching in linked lists, where each node is checked sequentially until the desired element is found.

5. Reversing

Reversing a linked list means changing the direction of pointers to create a new list with elements in the opposite order. Reversing can be done iteratively or recursively and is useful in various algorithms and problem-solving scenarios.

Conclusion

Linked lists are powerful data structures in Java that offer dynamic memory allocation and efficient operations for managing collections of elements. Understanding the types of linked lists, their operations, and their implementation in Java is essential for building robust applications and solving complex problems efficiently. Whether you’re a beginner or an experienced Java developer, mastering linked lists will enhance your programming skills and enable you to tackle a wide range of programming challenges effectively. Happy coding!