cubes cubes - 18 days ago 6
Java Question

recursive size method linked list

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);
}
}

Answer

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")

Comments