3

I am trying to understand the output I am receiving from my rercusive linked list size method.

private int size(Node list)
{
   if (list == null)   
       return 0;
   else 
   {
      int results = size(list.next) + 1; 
      System.out.println(results);
      return results;
   }             
}

The output I receive as it runs is this:

1 2 1 2 3 1 2 3 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5

It calculates the right answer, but it produces more recursive calls than I was expecting. I was expecting an output that would look like this.

1 2 3 4 5

Why is this?

I noticed when I add elements this way ll.add("Amy"); ll.add("Bob") I receive the output I was expecting, but when I add elements this way ll.add(0, "Al"), ll.add(2, "Beth"), ll.add(4, "Carol") it produces the output I wasn't expecting. I am trying to figure out why the output looks like this, any ideas?

 public static void main(String [] args)
 {
    RLinkedList ll = new RLinkedList();
    ll.add("Amy");
    ll.add("Bob");
    ll.add(0, "Al");
    ll.add(2, "Beth");
   ll.add(4, "Carol");
    System.out.println(ll.size());

This is the recursive add methods I am using.

public void add(String e)
{
   // Replace first with result of adding e to first 
   first = add(e, first);
}

/**
   This recursive private add method adds
   an element e to the end of a list.
   @param e The element to add to the list.
   @param list The list to add e to.
   @return The list resulting from adding e to its end.
*/

private Node add(String e, Node list)
{
   if (list == null)
   {
       // Base case
       return new Node(e);
   }
   else
   {
       // Add e to the end of the tail and use
       // the result to replace the tail
       list.next = add(e, list.next);
       return list;
   }        
}

/**
   The add method adds an element e at place index
   in this linked list.
   @param index The place in the list to add an element.
   @param e The element to add this the linked list.
     @exception IndexOutOfBoundsException When index is 
              out of bounds.  
*/

public void add(int index, String e)
{
   // Replace first with the result of adding
   // e at index in first
   first = add(index, e, first);        
}    

/**
   This add method adds an element at an index in a list.
   @param e The element to add to the list.
   @param index The index at which to add the element.
   @param list The list to add e to.
   @return The list resulting from adding e.
   @exception IndexOutOfBoundsException When index is 
              out of bounds.  
*/

private Node add(int index, String e, Node list)
{
    if (index < 0  || index > size()) 
    {
         String message = String.valueOf(index);
         throw new IndexOutOfBoundsException(message);
    }         
    if (index == 0)        
         return new Node(e, list);        

    // 0 < index and index <= size so list is not empty
    // Replace the tail with result of adding e at index - 1
    // in the tail

    list.next = add(index-1, e, list.next);        
    return list;     

This is the Node class

private class Node
{
    String value;   
    Node next;      

    /**
       Constructor.            
       @param val The element to store in the node.
       @param n The reference to the successor node.
    */

    Node(String val, Node n)
    {
        value = val;
        next = n;
    } 

    /**
       Constructor. 
       @param val The element to be stored in the node.
    */

    Node(String val)
    {
       // Just call the other (sister) constructor
       this(val, null);            
    }
}   
1
  • could you post also Node class? Nov 13, 2016 at 18:23

2 Answers 2

0

Try this:

  public static void main(String[] args) {
    RLinkedList ll = new RLinkedList();
    ll.add("Amy");
    ll.add("Bob");
    ll.add(0, "Al");
    ll.add(2, "Beth");
    ll.add(4, "Carol");

    System.out.println("SIZE");
    System.out.println(ll.size());
  }

You'll see that you get

1 2 1 2 3 1 2 3 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
SIZE: 
1
2
3
4
5
5

All of the extra output is coming from your if (index < 0 || index > size()) conditional when you call add(index, "string")

0

It's just the System.out.println(results);in your size method. In fact the method it's called in the add function and, since you output start from "1, 2", you can see that the problem is on the third call to the add method in your main. Try to remove you System.out.println(results); from the size function and write in your main System.out.println(ll.size()) and the output will be 5.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.