Linked List Traversal

Traversing from start to end

Traversal involves visiting every node in the list.
Printing the list requires this sort of traversal.
In a singly linked list we traverse from the head node to the end of the list.

 public void printList(Node head) {  
           while(head!=null)  
           {  
                System.out.print(head.data+",");  
                head=head.next;  
           }  
           System.out.println();  
      }  

This takes linear time O(N) since we need to visit each node in the list.

Traversing in Reverse Order

We can achieve this through recursion.  We basically traverse to the end of the list and then recursively print out till the head.

      public void reversePrint(Node head) {  
           if (head == null)  
                return;  
           reversePrint(head.next);  
           System.out.print(head.data + ", ");  
      }