Array of HashMaps in Java

HashMap in Java is one of the common data structures used to store key-value pairs. HashMap can also be used as items of an ordinary array.

package util;

import java.util.HashMap;
import java.util.Map;

public class ArrayUtility {


    @SuppressWarnings("unchecked")
    public static HashMap<String,Object>[] createAndFillHashMapArray( final int size )
    {
        HashMap<String, Object>[] hashMapArray = (HashMap<String, Object>[])new HashMap[size];
        int i = 0;
        for (HashMap<String, Object> hashMap : hashMapArray) {
             hashMap = new HashMap<String, Object>();
             hashMap.put("key"+i, "value"); 
             hashMapArray[i] = hashMap;
             i++;
        }
        return hashMapArray;
    }
 
    public static void displayHashMapArrayContent( HashMap<String, Object>[] hashMapArray )
    {
        if( hashMapArray != null && hashMapArray.length > 0 )
        {
           for (HashMap<String, Object> hashMap : hashMapArray) {
              for (Map.Entry<String, Object> entry : hashMap.entrySet()) {
                  String key = entry.getKey();
                  Object value = entry.getValue();
                  System.out.println(key+" - "+value);
               }
           }
         }
    }
 
    public static void main(String[] args) {
  
         HashMap<String, Object>[] hashMapArray = createAndFillHashMapArray(5);
         displayHashMapArrayContent(hashMapArray);
    }
}

createAndFillHashMapArray method takes the size of the array and fills it with HashMaps.
displayHashMapArrayContent method takes the hashMap array and displays its content as follows :

key0 - value
key1 - value
key2 - value
key3 - value
key4 - value

Print Singly Linked List in Reverse Order Recursively in Java

Arrays have got constant size restriction when they are created so it is expensive to resize them dynamically in an application. Instead of using arrays for resizing dynamic structure requirements, singly linked list data structure can be used.

Singly linked list has got a node based structure where each node has got next and data fields.

Above is a singly linked list with 1-2-3-4-5 elements.

In order to print data elements of each node of a singly linked list data structure in Java following forwardPrint and reversePrint methods can be used.

reversePrint is a recursive method and assumes that the head node is not null.

package basics;

public class LinkedList {

 static class Node
 {
  Node next;
  int data;
 }

 private Node head;
 
 public LinkedList(Node pHead) {
  head = pHead; 
 } 
 
 public void forwardPrint()
 {
  forwardPrint(head);
 }
 
 private void forwardPrint( Node node )
 { 
  Node current = head;
  while( current!=null )
  {
   System.out.println(current.data);
   current = current.next;
  }
 }
 
 public void reversePrint()
 {
  reversePrint(head);
 }
 
 private void reversePrint( Node node )
 {
  if( node.next != null )
   reversePrint(node.next);
  
  System.out.println(node.data);
 }
 
 public static void main(String[] args) {
  
  Node node1 = new Node();
  node1.data = 1;
  Node node2 = new Node();
  node2.data = 2;
  Node node3 = new Node();
  node3.data = 3;
  Node node4 = new Node();
  node4.data = 4;
  Node node5 = new Node();
  node5.data = 5;
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = node5;
  node5.next = null;
  
  LinkedList list = new LinkedList(node1);
  System.out.println("Forward Print Linked List = ");
  list.forwardPrint();
  System.out.println("Backward Print Linked List = ");
  list.reversePrint();
 }
}

Node objects are created separately and node1 object sent as the head of the linked list. Create a LinkedList.java file in your workspace.

When the main method inside the LinkedList class executed it is going to print :

Forward Print Linked List =
1
2
3
4
5
Backward Print Linked List =
5
4
3
2
1

Generic Recursive Find Depth of Binary Tree in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth of a binary tree is defined as the maximum length of all paths.

If a binary tree has only one node, its depth is 1. Following sample binary tree can be used as a test input.

There is a detailed and helpful description also at this link. 

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public int depth() {
       return depth(root);
   }

   private int depth(Node<T> pNode) {
  
     if (pNode == null)
         return 0;

     int left = depth(pNode.getLeftChild());
     int right = depth(pNode.getRightChild());
       
     int result = (left>right) ? (left+1) : (right+1);
     return result;
   }
  
}

public class BinaryTreeOperations {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    System.out.println("Depth of Binary Tree = "+binaryTree.depth()); 
 }

}

Create a BinaryTreeOperations.java file in your workspace.

When the main method inside the BinaryTreeOperations class executed it is going to print :

Depth of Binary Tree = 3

Generic Iterative Depth-First Binary Tree Traversal with Stack in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS requires the use of a data structure called Stack, which is a Last In First Out (LIFO) structure.

                                       Depth-First Traversal Sequence: 1 - 2 - 4 - 5 - 3 - 6

package interviewquestions;

import java.util.Stack;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void depthFirst()
   {
     depthFirst( root );   
   }
 
   private void depthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Stack<Node<T>> stack = new Stack<Node<T>>();
     stack.add(pNode);

     while (!stack.isEmpty()) {
         Node<T> node = stack.pop();

         if (node.getRightChild() != null)
             stack.add(node.getRightChild());
         if (node.getLeftChild() != null)
             stack.add(node.getLeftChild());
         System.out.print(node.getData());
     }

   }
  
}

public class DepthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.depthFirst();  
 }

}

Create a DepthFirstTraversal.java file in your workspace.

When the main method inside the DepthFirstTraversal class executed it is going to print :

1
2
4
5
3
6

Generic Iterative Breadth-First Binary Tree Traversal with Queue in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors. 

Breadth-first traversal is also known as level-order traversal. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure.

                                         Breadth-First Traversal Sequence: 1 - 2 - 3 - 4 - 5 - 6

package interviewquestions;

import java.util.LinkedList;
import java.util.Queue;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void breadthFirst()
   {
     breadthFirst( root );   
   }
 
   private void breadthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Queue<Node<T>> queue = new LinkedList<Node<T>>();
     queue.add((Node<T>) pNode);
  
     while (!queue.isEmpty()) {
          Node<T> node = (Node<T>) queue.remove();
          System.out.print(" " + node.getData());
   
          if (node.getLeftChild()!= null)
              queue.add(node.getLeftChild());
          if ( node.getRightChild() != null)
              queue.add(node.getRightChild());
     }      

   }
  
}

public class BreadthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.breadthFirst();  
 }

}

Create a BreadthFirstTraversal.java file in your workspace.

When the main method inside the BreadthFirstTraversal class executed it is going to print :

1
2
3
4
5
6

Generic Recursive Inorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Inorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Visit root node (output this)
3. Traverse right subtree

Recursive inorder binary tree traversal algorithm can use a generic node class.

                                                 Inorder Traversal Sequence: 4 - 2 - 5 - 1 - 3 - 6

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void inOrder()
   {
     inOrder( root );   
   }
 
   private void inOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     inOrder( pNode.getLeftChild() );
     System.out.println( pNode.getData() );
     inOrder( pNode.getRightChild() );       

   }
  
}

public class InOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.inOrder();  
 }

}

Create a InOrderTraversal.java file in your workspace.

When the main method inside the InOrderTraversal class executed it is going to print :

4
2
5
1
3
6

Generic Recursive Postorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Postorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Traverse right subtree
3. Visit root node (output this)

Recursive postorder binary tree traversal algorithm can use a generic node class.

Postorder Traversal Sequence: 4 - 5 - 2 - 6 - 3 - 1

package interviewquestions;


class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void postOrder()
   {
     postOrder( root );   
   }
 
   private void postOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     postOrder( pNode.getLeftChild() );
     postOrder( pNode.getRightChild() );

     System.out.println( pNode.getData() );  

   }
  
}

public class PostOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.postOrder();  
 }

}

Create a PostOrderTraversal.java file in your workspace.

When the main method inside the PostOrderTraversal class executed it is going to print :

4
5
2
6
3
1

Generic Recursive Preorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Preorder traversal allows all the nodes of the binary tree to be visited by starting from the root node.

Recursive preorder binary tree traversal algorithm can use a generic node class.

                                                         Preorder Traversal Sequence: 1 - 2 - 4 - 5 - 3 - 6

package interviewquestions;


class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }
}

class BinaryTree<T>
{

   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void preOrder()
   {
     preOrder( root );   
   }
 
   private void preOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   
     System.out.println( pNode.getData() );  
  
     preOrder( pNode.getLeftChild() );
     preOrder( pNode.getRightChild() );
   }
  
}

public class PreOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.preOrder();  
 }

}

Create a PreOrderTraversal.java file in your workspace.

When the main method inside the PreOrderTraversal class executed it is going to print :

1
2
4
5
3
6

Reverse Array Using Stack in Java

Stack can be used to reverse an array.

import java.util.Arrays;
import java.util.Stack;

public class ReverseArrayUsingStack {

 public static int[] reverse(int[] data) {

  Stack<Integer> stack = new Stack<Integer>();

  for (int i = 0; i < data.length; i++)
   stack.push(data[i]);

  for (int i = 0; i < data.length; i++)
   data[i] = stack.pop();

  return data;
 }

 public static void main(String[] args) {

  int[] a = { 41, 2, 151, 13, 43, 12 };

  System.out.println(Arrays.toString(a));

  System.out.println(Arrays.toString(reverse(a)));

 }
}

Initially push all the elements in the array onto the Stack. Stack is now full of items. Then pop all the elements from Stack back into original array.

In this solution, algorithm is not very efficient in terms of space because it uses an extra data structure to hold the items.

Compare Two Singly Linked Lists in Java

Singly linked list is a very common data structure which consists of different nodes.

There are some basic operations can be performed on singly linked lists such as add, insert, delete, remove from tail or head.

In addition to above operations a comparison method for two different singly linked lists can be implemented.

In the following sample there two different singly linked lists which are SinglyLinkedList1 and SinglyLinkedList2.

SinglyLinkedList1 consists of nodes node1, node2, node3 and node4 with a head node of headA.

SinglyLinkedList2 consists of nodes node11, node21, node31 and a head node of headB.

For this CompareLists method implementation, following design restrictions applied :

1-) Method takes just the head references for different singly linked lists.
2-) In order to be equal number of nodes in singly linked lists must be the same.
3-) In order to be equal data in each node for different singly linked lists must be the same.
4-) In order to be equal order of nodes in each singly linked lists must be the same.

If the above conditions apply then CompareLists method returns 1 otherwise returns 0.

Package contains following classes.

SinglyLinkedList.java contains Node and SinglyLinkedList classes.

package datastructures.linkedlists;

class Node
{
 int data;
 Node next;
}

public class SinglyLinkedList {

 Node head; 
 public SinglyLinkedList() {
  head = null;
 }
}

SinglyLinkedListUtility.java contains CompareLists method.

package datastructures.linkedlists;


public class SinglyLinkedListUtility {

 public int CompareLists(Node headA, Node headB) {

     if( headA == null || headB == null ) return 0;
     Node walkA = headA;
     Node walkB = headB;
     while( walkA != null )
     {
      if( walkA.data != walkB.data ) return 0;
         walkA = walkA.next;
         walkB = walkB.next;
         if( walkA==null && walkB!=null ) return 0;
         if( walkA!=null && walkB==null ) return 0;
     }
     return 1;
 }
 
}

TestSinglyLinkedListUtility is the unit test class including testCompareLists unit test method.

package datastructures.linkedlists;

import static org.junit.Assert.*;
import org.junit.Test;

public class TestSinglyLinkedListUtility {

 @Test
 public void testCompareLists() {
  
  Node node4 = new Node();
  node4.data = 4;
  
  Node node3 = new Node();
  node3.data = 3;
  node3.next = node4;
  
  Node node2 = new Node();
  node2.data = 2;
  node2.next = node3;
  
  Node node1 = new Node();
  node1.data = 1;
  node1.next = node2;
  
  Node headA = node1;
  
  Node node31 = new Node();
  node31.data = 3;
  node31.next = null;
  
  Node node21 = new Node();
  node21.data = 2;
  node21.next = node31;
  
  Node node11 = new Node();
  node11.data = 1;
  node11.next = node21;
  
  Node headB = node11;

  SinglyLinkedListUtility linkedListUtility = new SinglyLinkedListUtility();
  assertEquals( linkedListUtility.CompareLists(headA, headB), 0 );

 }

}

JUnit execution result is :