My recursion find(T data) method is resizing my LinkedList..how do I stop that?

Question

I need to make some methods for a LinkedList that use recursion. I have some that are good but this is one of the ones that is giving me trouble:

public boolean find(T data){    
    if(head == null)
        return false;
    else{
        if(head.data == data)
            return true;
        else{
            head = head.next;
            return find(data);
        }
    }
}

It's supposed to find an element in the LinkedList but the problem is, the List shouldn't be appended, which obviously mine is with head's position increasing. The prototype is supposed to have 1 parameter, the data one. How can I get it to stop increasing the head position?

score 2 · Answer 1 · answered Mar 14 '12 at 02:58

2

You need to maintain a separate reference to the current node; do not use head. I would do this using a helper method.

public boolean find(T data){    
    return find(data, head);
}

private boolean find(T data, Node current) {
    if (current == null) return false;
    if (current.data.equals(data)) return true;
    current = current.next;
    return find(data, current);
}

Note the use of .equals() instead of == when comparing data values. I assumed that head is of class Node. If that's not the right guesss, fill in whatever the actual class is in your implementation.

answered Mar 14 '12 at 02:58

Matt Ball

354,903
100
647
710

Does equals() make a difference? – user1267952 Mar 14 '12 at 03:07
In general: yes. It does depend on what concrete type `T` is, though. If `T` is a class that does not override `.equals()`, then there is no difference. See http://stackoverflow.com/questions/7520432/java-vs-equals-confusion – Matt Ball Mar 14 '12 at 03:08
okay. also i'm not sure what the first method's relevance is. with that second one it looks like we don't even need the first one, right? – user1267952 Mar 14 '12 at 03:14
It's about the API you expose for the rest of the world to use. Correct - you _could_ get away with just the second method. But like you said: _"The prototype is supposed to have 1 parameter, the data one."_ And it's better API design to hide the `current` parameter from those who'd use your code. – Matt Ball Mar 14 '12 at 03:22
Oh I see, like abstraction. I hope that I can use that as a valid answer. XD Thank you for the help! I have more methods to write but I think I can use this to make it work. – user1267952 Mar 14 '12 at 03:24
1

Sounds like you understand it. `:)` If you consider your question solved, would you mind [accepting this answer](http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work)? – Matt Ball Mar 14 '12 at 03:26

score 0 · Answer 2 · edited Mar 14 '12 at 03:55

Unless your requirements are rigid in using recursion I suggest you use iteration to traverse a list. Recursion is inefficient in that it creates unnecessary function stack.

Recursion is useful in simplifying code for non-linear traversals or data structure.

Code for same using iteration would look as follows.

public boolean find(T data) {

    boolean found = false;
    T current = head;   

    while(current != null) {

        if(current.data.equals(data)) {

            found = true;
            break;
        }

        current = current.next;
    }

    return found;
}

My recursion find(T data) method is resizing my LinkedList..how do I stop that?

2 Answers2