December 29, 2018

Write a utility function to create linked list from a sequence of items – using iteration and recursion

While working on linked data-structures, we have to create linked lists regularly. To ease that process, we can create a utility function, which creates linked list from given data and returns head of the new linked list.

Our functions will accept a variable argument and it will return a Node. We are using Node class definition from here .

Algorithm :- 

    1. Create a New Node
    2. if head node is null
      1. then set the head reference to the new Node
      2. stpre the new node reference to a temp variable
  1. If head reference is not null
    1. set the next instance variable of temp to point to the new Node
    2. make the temp variable to point to the new node.

 

Iterative Implementation :-

 @SuppressWarnings("unchecked")                                                                                                                                                                          
    private static Node createLinkedListIterative(String ... data) {                                                                                                                                        
        Node head = null;                                                                                                                                                                                   
        Node temp = null;                                                                                                                                                                                   
                                                                                                                                                                                                            
     for(String val : data) {                                                                                                                                                                            
         Node newNode = new Node(val);                                                                                                                                                                   
         if(head == null) {                                                                                                                                                                              
              head = newNode;                                                                                                                                                                             
             temp = head;                                                                                                                                                                                
         } else {                                                                                                                                                                                        
             temp.next = newNode;                                                                                                                                                                        
             temp = temp.next;                                                                                                                                                                           
        }                                                                                                                                                                                               
    }                                                                                                                                                                                                   
    return head;
}

Recursive Method 1 :-

We can also use recursion to achieve this.

@SuppressWarnings("unchecked")                                                                                                                                                                          
    private static Node createLinkedListRecursive(int currentIndex,                                                                                                                                         
                                                  int lengthOfDataArray,                                                                                                                                    
                                                  String ... dataArray) {                                                                                                                                   
    if(currentIndex == lengthOfDataArray) return null;                                                                                                                                                  
                                                                                                                                                                                                            
    String data = dataArray[currentIndex];                                                                                                                                                              
    Node newNode = new Node(data);                                                                                                                                                                      
    //Recurse to get the next node;                                                                                                                                                                     
    Node next = createLinkedListRecursive(++currentIndex,                                                                                                                                               
                                              lengthOfDataArray,                                                                                                                                            
                                              dataArray);                                                                                                                                                   
    newNode.next = next;                                                                                                                                                                                
    return newNode;                                                                                                                                                                                     
}

Recursive Method 2 :-

We can make this recursive function smaller. It is not going to be readable, and I won’t recommend writing code like this, because it is hard to read and maintain. But, it is fun to write 🙂

@SuppressWarnings("unchecked")                                                                                                                                                                          
    private static Node createLinkedListRecursive_Smaller(int currentIndex, int lengthOfDataArray,                                                                                                          
                                         String ... dataArray) {                                                                                                                
           return (currentIndex == lengthOfDataArray) ? null :                                                                                                                                                 
                                                  ((new Node(dataArray[currentIndex])).next = createLinkedListRecursive_Smaller(                                                                                                                  
                                                                                                                   ++currentIndex,                                                                                                                                         
                                                                                                                   lengthOfDataArray,                                                                                                                             
                                                                                                                    dataArray));
}

In terms of functionality, both of the recursive functions are the same. But, the second one is less readable.