How to create a Nested List upto any level of nesting

Points To Remember

  • The Correct Datatype for creating a Nested List will be List<Object>, because we have to store either a integer number or a list inside the list.
  • We can not have a nested list like List<List<Integer>> because it will not be able to hold the integer values. It can only hold a list.
  • The List we create can be nested to any level.

Program : Create A nested list upto any level

Here we suppose that we get a String input of the list that we have to create. The following program accepts the list as a String and returns after converting the list to a nested list up to any level.
import java.util.*;
import java.util.LinkedList;
import java.util.Scanner;

public class CreateList{

 public static void main(String args[]){
    CreateList obj = new CreateList();
    System.out.println(obj.createNestedList());
 }

  public List<Object> createNestedList(){

     Scanner sc = new Scanner(System.in);
     System.out.println("Enter the Nested List");

     // Take input from the user
     String inputString = sc.next(); 

     List<Object> nestedList = new LinkedList<Object>();
     String num=""; // Strore the number as String
     for(int itr=1; itr<inputString.length()-1;itr++){
       char c = inputString.charAt(itr);
       if(c == ','){ // If the char is , then add the number to list
         if(!num.equals("")) // Check if the number is not null or ""
            nestedList.add(Integer.parseInt(num));
         num= "";
       }
       else if(c != '[' && c != ']') // If the character is a digit add it to number
          num += c;  
       else if(c == '[') // If [ is encountered, add it to list
          nestedList.add(c);   
       else if(c == ']'){ // If ] is encountered, pop all elements till last [ and add to list.
         if(!num.equals(""))
            nestedList.add(Integer.parseInt(num));
         num= "";
         List<Object> temp = new LinkedList<Object>(nestedList.subList(nestedList.lastIndexOf('[')+1,nestedList.size()));
         nestedList = nestedList.subList(0,nestedList.lastIndexOf('['));
         nestedList.add(temp);
       }
     }
   if(!num.equals("")) // If last digit is not added to list, add it
       nestedList.add(Integer.parseInt(num));
   return nestedList;
  }
}
The above program gives the following output.
Enter the Nested List
[1,2,3,[4,5],6,[7,[8,9]],10]
[1, 2, 3, [4, 5], 6, [7, [8, 9]], 10]
If we add a print statement just before the end of the for loop we will see the following output.
[]
[1]
[1]
[1, 2]
[1, 2]
[1, 2, 3]
[1, 2, 3, []
[1, 2, 3, []
[1, 2, 3, [, 4]
[1, 2, 3, [, 4]
[1, 2, 3, [4, 5]]
[1, 2, 3, [4, 5]]
[1, 2, 3, [4, 5]]
[1, 2, 3, [4, 5], 6]
[1, 2, 3, [4, 5], 6, []
[1, 2, 3, [4, 5], 6, []
[1, 2, 3, [4, 5], 6, [, 7]
[1, 2, 3, [4, 5], 6, [, 7, []
[1, 2, 3, [4, 5], 6, [, 7, []
[1, 2, 3, [4, 5], 6, [, 7, [, 8]
[1, 2, 3, [4, 5], 6, [, 7, [, 8]
[1, 2, 3, [4, 5], 6, [, 7, [8, 9]]
[1, 2, 3, [4, 5], 6, [7, [8, 9]]]
[1, 2, 3, [4, 5], 6, [7, [8, 9]]]
[1, 2, 3, [4, 5], 6, [7, [8, 9]]]
[1, 2, 3, [4, 5], 6, [7, [8, 9]]]
[1, 2, 3, [4, 5], 6, [7, [8, 9]], 10]

Algorithm Followed

  • Step 1 : Iterate over the String , you can encounter digit, comma, or brackets [ and ].
    • If a digit is encountered add it to String number, this is used to store digits that are greater than 10.
    • If  , is encountered add the number to list and reset value of number.
    • If [ is encountered add it to the list.
    • if ] is encountered
      • Add number to list if it is not null.
      • Pop all elements till [ is encountered and add it to a temp list
      • Add temp list to the list.


No comments :

Post a Comment