CODEWITHSUNDEEP
javarecursiondata-structureslastindexof
Pansock
Pansock

Reputation: 3

getLastIndexOf(int item) LinkedList

I'm currently a freshman comp sci student working on learning data structures both through my class and also online.

I'm new to stack too but it has helped me a lot in the past.

My current problem is searching through a LinkedList to return the last index of which the number appears in the list.

I feel like this has to do somewhat with recursion and continually searching until you can somehow check for sure that that is the last occurrence of that item, then return its index.

However my first semester Java course did not cover recursion at all and I'm sort of at a loss.

Being in these courses I'm not asking for the flat out answer, I just need some direction. Or reassure me that I'm on the right path with looking into recursion at all?

Also, here is what I have attempted so far. Thanks for the help!

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable 
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
            //check rest of the list for if that number exists beyond
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
    return -1;
}

Upvotes: 0

Views: 588

Answers (3)

S Raghav
S Raghav

Reputation: 1526

If you want to do it by recursion

This tutorial from Topcoder might be useful here.

My 2 cents follow:

Recursion and iteration (looping, like for, while etc.) can be used to solve your current problem.

Your current code is not recursive, it is iterative. Recursion happens when you call the same function again and again till some end condition.

A recursive function has two parts:

  1. the base condition - tells you when to stop the recursion
  2. the recursive condition - tells you when to do recursion

Let's see this with an example. Say you want to print "Hello World" 10 times. Here's how you would do it iteratively

for(int i = 0; i < 10; i++){
   System.out.println("Hello World");
}

And here is how you do it recursively

void helloWorldPrinter(int index){
   //This is the base condition, tells us to stop when we've reached 10
   if(index == 10){
      return;
   }
   else{
      //Print for the n th hello world
      System.out.println("Hello World");
      //call the same function for printing the next (n+1 th) hello world
      helloWorldPrinter(index+1); //Looks similar to the i++ in the loop right?
   }
}

Recursion is incredibly useful in Binary Trees which are data structures that look like upside down trees. A concept that you can keep in mind while writing iterative vs recursive code is that iteration is like looking at the data structure as an observer and doing actions on it.Recursion proceeds as if you are an element in the data structure - you do your job and pass the responsibility to the next element (next recursive call)

Now I believe you can extend this logic to finding the last item in the Linked List. Though an iterative solution for this would be much easier than a recursive one.

The logic is:

Loop over list (iterative or recursive)
  If element is found, note down the index
End Loop if list has been traversed completely
return the element index

Upvotes: 0

weston
weston

Reputation: 54811

Consider the list to be a node followed by another list, called the tail. This is pseudocode, note you need two methods, the private one takes a node, this is the sub list.

public int getLastIndexOf(value) {
    return getLastIndexOf(head, value);
}

private int getLastIndexOf(sublist, value) {
    //check the tail first (because we want last index)
    if (sublist.tail != null) {//list has a tail
        int lastIndexInTail = getLastIndexOf(sublist.tail, value); //recursion
        if(lastIndexInTail != -1)
          return lastIndexInTail + 1; //it's in the sub list, the sub list starts at idx 1
    }

    // it's not in the tail, check this head
    if (sublist.data == value){
      return 0; //it's at the front of this list
    }

    return -1; //it's not in the head or in the tail of sublist
}

Upvotes: 0

samson
samson

Reputation: 82

You could just save and overwrite the index when you have a match like so:

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable
    int lastIndex = 0;
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
                lastIndex = count;
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
return lastIndex;

So you will save the position of the match in lastIndex, and if theres more than one match, you will just overwrite it with the "latest" value.

Upvotes: 1

Related Questions