cubes - 1 year ago 121
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)
{
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);
}

/**
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);
}
}
``````

Try this:

``````  public static void main(String[] args) {

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download