wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Need help keeping track of previous element in a list. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Need help keeping track of previous element in a list." Watch "Need help keeping track of previous element in a list." New topic
Author

Need help keeping track of previous element in a list.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
I am using the java.util.ListIterator interface. I need to sort a list by removing any element that is smaller than the previous element. (I will always keep the first element). For example given the following list this is what the list should look like after the method runs: {5,1,7,8,6} -> {5,7,8}

Here is what I have so far the problem is I am getting a result that looks like this {5,7,8,6}. I cannot figure out how to get rid of the 6! Please help, below is my code. Thanks a lot.

Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4456
    
    6

Sometimes it helps to try a totally opposite approach. Instead of removing elements, why not add valid items to a new list and return that instead?

One potentially bad thing about your current implementation is that it modifies the parameter -- that can lead to unpleasant surprises for the user of the method. It's generally better to leave the parameter alone and return a new object for the result.

Unless you have a specific requirement to use ListIterator in your code, you should also look into using the newer for-each loop, available since Java 5.

If you really want to keep going the way you're going, make sure you understand what happens to the iterator cursor for each of the operations you use: remove(), next(), previous() -- that's where the problem lies.


Junilu - [How to Ask Questions] [How to Answer Questions]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
Welcome to the Ranch
Don’t call that sorting; sorting retains all elements in a List.
I think you will have to get a pencil paper and eraser (the latter preferably large ‍) and go through your loop, always writing down the position in the List, the number of values in the List, and what previous is, at each iteration through that loop. Then you can see what is happening.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4456
    
    6

BTW, your current code will break on Line 3 if you have an empty list.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7700
    
  20

Junilu Lacar wrote:BTW, your current code will break on Line 3 if you have an empty list.

@William: BTW, that is a general rule for ALL Iterators.

Always, always, always check hasNext() before you call next() (or indeed hasPrevious() before you call previous()).

Your life will be a lot happier.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Hey thanks a bunch everyone!

I was able to pass all the test cases thanks to your thoughtful insight!

Here is my solution:



This is definitely a forum I will continue to visit for all my Java wants and needs.
Thanks again.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4456
    
    6

Just out of curiosity, what is the correct expected result of running the list {7, 4, 5, 6} through this "sorting" algorithm of yours? Should it be {7, 5, 6} or {7}?

What about the list {8, 1, 7, 9, 4, 5, 6, 3, 5}? Should it end up with {8, 7, 9, 5, 6, 5} or {8, 9}?
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
This is the problem our instructor gave us (this is for a Data Structures Class) I took intro to Computer Science course last year using Ada95 but now we just switched to a Data Structures using Java so I am still learning all the tools that are available with Java. But anyways here is what it is supposed to to.

So for you examples it would {7} and {8,9}

* Given a list of integers, "sort" it by removing elements that are out of
* order. Specifically, working from front to back 1. always keep the first
* item (if any) 2. remove any item that is < the previous kept item, and
* keep any item that is >= the previous kept item For example, -
* {1,2,3,4,5} -> {1,2,3,4,5} - {1,2,3,4,4} -> {1,2,3,4,4} - {5,1,2,3,4} ->
* {5} - {5,4,5,3,5} -> {5,5,5} - {5,1,7,8,6} -> {5,7,8}
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4456
    
    6

Ok, got it. Then it looks like your implementation works. Thanks for the clarification.

My comments from before still stand though and the algorithm I gave, when slightly tweaked, is more straightforward and doesn't require all that next(), previous() business. I'm not saying that your way is that much more complicated but it can be a bit harder to follow.

"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." -- C.A.R. Hoare

Here's my solution for comparison:
 
wood burning stoves
 
subject: Need help keeping track of previous element in a list.