Reputation: 3
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
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:
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
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
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