Recursion on Linked List

Recursion allows us flexibility in printing out a list forwards or in reverse (by exchanging the order of the recursive call)
Recursion takes away looping and checking for special cases using dummy head or tails nodes , if you dont  believe me , try writing an iterating for or while loop recursive algos !

The classes required for Node and SinglyLinkedList object are  implemented here  - see -

Following function using recursion should be added to SinglyLinkedList class for implementation - 

Printing the elements of list - 


// Recursively prints the output of list
public void printList(Node n) {

if(n  == null)
{
return;
}

/*
*  to print in reverse order  just exchange the following statements ! ---
*  printList(n.getNext());
* if(n != null)
* System.out.println(n.getElement());
*/
if(n != null)
System.out.println(n.getElement());
printList(n.getNext());

}
}

Call -
SinglyLinkedList  sll =  new SinglyLinkedList();
sll.printList(sll.head);


Length of a linked list - 
public int length(Node n) {
if(n == null)
return  0;
else
return 1 + length(n.getNext());
}


//example call 
System.out.println(sll.length(sll.head));

Paradigm -  reconstruct the list

It is helpfull if we see insertion and deletion operations on linked list in terms of reconstruction  . Now u may say that  i have gone nuts because  i implemented  inserting a  node at head and tail in SinglyLinkedList class  without reconstrcution unlike as it is usually  an element is inserted in arrays . That is insane because this approach completely overwrites the dynamic nature of linked list.

But check out this silly function of reconstrcution ahead  which makes you trivially reconstruct all nodes of linked list by reassighning references to all nodes-

public Node reconstruct(Node p)
{
if(p ==  null)
{
return null;
}

               //silly part
p.setNext(reconstruct(p.getNext()));
return p;

}


}

Now what you do is exploit this reconstruct's silly part to do  anything you wish to do with the node reassgihned , suppose concate a "1" to every string - 

public Node concateOne(Node p)

{

if(p ==  null)

{

return null;

}

                

                // Silly really ? 

p.setElement(p.getElement().concat("1")) ;

p.setNext(concateOne(p.getNext()));

return p;

}

// example call

sll.head = sll.concateOne(sll.head);

sll.printList(sll.head);

Some more so called silly traversing based linked list function based on recursion - 

Copying a linked list -
// create copy of existing 
public Node copy(Node n) {
if(n ==  null)
return null ;
else
return new Node(n.getElement() ,copy(n.getNext()));
}

Example call


// add the new copy to newly created singly linked list
SinglyLinkedList newList = new  SinglyLinkedList();
                //create a copy
newList.head =  sll.copy(sll.head);
//print the new list

newList.printList(newList.head);

Let me repeat again for you that  we need NOT use any dummy header and check for special case of empty list or inserting at head leading to IllegalStateException or IllegalArgumentException , when using this recursive paradigm of  "reconstruct " .

Yup , i know , silly enough to grasp :P