Erik Vesterlund - 9 months ago 51

Java Question

I am given a class List (here: http://pastebin.com/ZCi3q7LQ) and have to write some methods for it, including a method that finds the index for a specified integer.

Indices start at zero, the method must return -1 if the specified integer is not in the list, the method must work recursively and run in $O(n)$ time.

My problem is making the method return -1 when calling indexOf for an integer that's not in the nontrivial list. I've tried just about every possible combination as well as read some similar looking questions here but they didn't help. This is what I made:

`public int indexOf(int x) {`

return indexOf(x, first);

}

private static int indexOf(int x, Node n) {

if (n==null) {

return -1;

}

else if (n.data==x) {

return 0;

}

else return 1+indexOf(x, n.next);

}

If x isn't in the list and the list is nonempty this will return the index of the last element, which was not intended. Like I said I'm at a complete loss how to make this work, I'd appreciate any help I can get.

(If it matters, yes this is homework.)

Answer

The problem was when it returned back up the stack it **always** added one to the returned value, including negative one. While it would be easy to add a check to see if the return is `-1`

there is an easier solution.

```
public int indexOf(int x) {
return indexOf(x, first, 0);
}
private static int indexOf(int x, Node n, int depth) {
if (n==null) {
return -1;
}
else if (n.data==x) {
return depth;
}
else return indexOf(x, n.next, depth + 1);
}
```