1

Ok so say I have a function that looks for a specific word in a custom LinkedList class:

public LinkedList find(String word) {
    if (this.word.equals(word))
        return this;
    if (next==null)
        return null;
    if (next.find(word)==next)
        return next;
    return null;
}

This code works fine, however it returns the FIRST found object that matches the criteria. What if I wanted to return the LAST object found that matches the paramater? I'm having a hard time figuring this out. Keep in mind I want to use recursion.

EDIT: What would be wrong with this code:

public LinkedList findLast(String word) {
    LinkedList temp=new LinkedList(word, null);
    if (next==null && next.word.equals(word))
        return next;
    if (next==null && !next.word.equals(word))
        temp=next.findLast(word);
    return temp;
}
Improve this question
7
  • 8
    Smells like homework :) Commented Nov 2, 2010 at 19:23
  • This code does work? It seems to me it would only return the first, second or null node. Commented Nov 2, 2010 at 19:36
  • @ILMTitan: It looks like it should work to me... the first line returns the current node, the second line return null, and the third line recursively calls itself over and over (thus returning currentNode+1). Commented Nov 2, 2010 at 19:38
  • 1
    @Bane But it doesn't return next.find(word). It returns next if next.find(word) == next. It only ever returns this, null or next, never an arbitrary value returned from next.find(word). Commented Nov 2, 2010 at 19:41
  • Search from the back of the list? Being that this is a linked list just start from the back and work your way to the front, first found is last relevant instead of first if you leave searching/matching criteria the same. Commented Nov 2, 2010 at 19:44

7 Answers 7

Reset to default
8

Well, think of it this way: you need to recurse right to the end of the list, and then let the return value bubble up.

So the start of your method should either be a recursive call to look further down the list, or noting that we're at the end of the list - which is equivalent to the "further" result being null.

Now when you're returning, there are three options:

  • You've already found a match later than the current point - so return that reference
  • You've not found a match (so the return value of the recursive call was null) and:
    • The current point's word matches - so return the current point
    • The current point doesn't match - so return null

Hopefully that should be enough to get you to an implementation - if not, please ask more questions. I'd rather not give a full implementation when this is presumably homework.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Ya I dont want a full answer anyway, those only make me more confused. I just need someone to explain it. Im trying to understand what youre saying but I dont think its helping me much. Honestly when playing with recursion I find myself getting lucky most of the time.
Can you check edits please, and tell me what would be wrong with that code?
@fprime: Well for one thing, why on earth would you be creating a new linked list when you're trying to find entries? You shouldn't need to be building anything here.
It was a temp list to store the latest found entry
@fprime: But why would you need that? Just use the return value from the recursive call. You don't need to start building extra lists.
|
3

Store a reference to the latest one found and keep on calling itself until it returns null -- then return the latest-reference.

Note, for clarification: you're going to have to iterate through your entire linked-list (unless you have a doubly-linked-list) to achieve this -- store a reference every time you find a match (but just overwrite the same reference each time) -- then return whatever the reference holds once you reach the end of this list.

public class LinkedList {

  private static int uniqueIdCounter = 0;

  private final String word;
  private int uniqueId;
  private LinkedList next = null;

  public LinkedList( String word ) {

    this.word = word;
    this.uniqueId = uniqueIdCounter++;
  }

  @Override
  public String toString() {

    return this.word + "(" + this.uniqueId + ")";
  }



  public void setNext( LinkedList next ) {

    this.next = next;
  }

  public LinkedList find( String word ) {

    return this.find( word, null );
  }

  public LinkedList find( String word, LinkedList result ) {

    if( this.word.equals( word ) ) {
        result = this;
    }

    if( this.next != null ) {

        result = this.next.find(word, result);
    }

    return result;
  }

  public static void main(String[] args) {

    LinkedList head = new LinkedList( "A");
    System.out.println( "Head is: " + head );

    LinkedList B = new LinkedList( "B" );
    head.setNext( B );
    System.out.println( "B is: " + B );

    LinkedList A2 = new LinkedList( "A" );
    B.setNext( A2 );
    System.out.println( "A2 is: " + A2 );

    LinkedList last = head.find( "A" );
    System.out.println( "Last is: " + last );
  }

}

And here's the output:

Head is: A(0)

B is: B(1)

A2 is: A(2)

Last is: A(2)

Improve this answer

4 Comments

Peter Knego's reply contains the code I desribed. Good job Peter!
Can you check edits please, and tell me what would be wrong with that code?
@fprime: no, the new method you added ('findLast') will most definitely not work -- it will blow up on you! You can't call a method on a null-object -- ie: 'if(next==null && next.word...' isn't going to work. Again, Peter's code should work -- it certainly looks correct.
Just to make things nice and clear, I went ahead and wrote the entire class, along with main to test things out -- I used Peter's code with minor modifications. His code works perfectly -- see the complete code in my answer (above).
2

Every straight recursive function has two places for some useful actions: before further method call and after:

  function(n){
    doBefore(n);
    function(n+1)
    doAfter(n)
  }

doBefore() is executed "on the way forward", doAfter() is executed "on the way back". Now your algorithm checks word equality on the way forward. You have to modify your algorithm so that this check is performed on the way back.

Improve this answer

Comments

1 
public LinkedList find(String word, LinkedList result) {
   if (this.word.equals(word))
        result = this;
   if (next != null )
        return next.find(word, result)
   return result;

Two-liner:

public LinkedList find(String word, LinkedList result) {
     result = this.word.equals(word) ? this : result;
     return next == null ? result : next.find(word, result);

@fprime: Ya, explanation: remember the result, replace it with later result, return when at the end.

Method with one argument:

public LinkedList find(String word){
   result = this.word.equals(word) ? this : null;
   if(next != null)
      previous = next.find(word);
      return (previous != null) ? previous : result 
   else 
      return result;
Improve this answer

9 Comments

The method Im supposed to write should only take 1 parameter, word. You seem to be on to something, but I'd rather have an explanation rather than some code, so I can learn whats going on..
This will work just fine, but you do the compare on every node. You should be able to short circuit the compares so you only do 1 if the last node has the word.
Ya, you are a bit late to tell us about one argument restriction!
You would use a starter method public LinkedList find(String word) { return find(word, null);}
Can you check edits please, and tell me what would be wrong with that code?
|
0

Just run it backwards from the tail.

public LinkedList find(String word) {
        if (this.word.equals(word))
            return this;
        if (prev==null)
            return null;
        if (prev.find(word)==prev)
            return prev;
        return null;
}
Improve this answer

2 Comments

You're making an assumption that this is a doubly-linked list. I would at least imagine that the OP really wants to see the different way of using recursion, rather than effectively just imagining a reversed list.
Even if it had a prev, it is wrong for the same reason that fprime's forward find is wrong.
0

To start with, you initial find(String word) does not work correctly.

Your first if statement is perfect. It is you success base case.

Your second if statement is also perfect. It is your failure base case.

Your third is where you go off the rails. You have handled all (in this case both) base cases, now all that is left is the recursive case. You don't need to check anything here. next.find(word) will return the correct answer, success or fail.

For findLast(String word), I can't add much to what Jon Skeet said. About the only advice I can add it to never have the a node check its neighbor. Each node should only ever check itself. You should see plenty of this.word.equals(word) but never next.word.equals(word).

Improve this answer

Comments

0 

public LinkedList find(String word) {
  if(this.word.equals(word)) return this;
  return next==null?null:next.find(word);
}



public LinkedList rfind(String word) {
  if(next != null) {
    LinkedList res = next.rfind(word);
    if(res != null) return res;
  }
  return this.word.equals(word)?this:null;
}

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.