• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Need help keeping track of previous element in a list.

 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7600
53
Android Eclipse IDE IntelliJ IDE Java Linux Mac Scala Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49812
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7600
53
Android Eclipse IDE IntelliJ IDE Java Linux Mac Scala Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
BTW, your current code will break on Line 3 if you have an empty list.
 
Winston Gutkowski
Bartender
Pie
Posts: 10508
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7600
53
Android Eclipse IDE IntelliJ IDE Java Linux Mac Scala Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7600
53
Android Eclipse IDE IntelliJ IDE Java Linux Mac Scala Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic