• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Collections.reverse under the hood

 
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi All.

Does anyone know what approach Collections.reverse() uses to reverse list?
My task is to implement and compare reverse methods from list and i already did reveres with Recursion, Swap, Reading backward with creating reversed copy.
Does Collections.reverse() use different approach from those i already did?

Thank you.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Daniel Gurianov wrote:Does anyone know what approach Collections.reverse() uses to reverse list?
My task is to implement and compare reverse methods from list and i already did reveres with Recursion, Swap, Reading backward with creating reversed copy.
Does Collections.reverse() use different approach from those i already did?


The answer to your first question: Nope.
The answer to your last one: Probably not; but since we don't know the details of your various implementations, again we can't know.

The fact is that there aren't that many ways to "reverse" a collection; and the method you choose will almost certainly depend on whether you need to reverse it "in place" or not.

One possibility that might be worth considering is a "reversed wrapper" - ie, a List that "wraps" an existing one, but has methods that convert all supplied indexes to "reversed" ones, and returns an Iterator that traverses in reverse order. That way, you don't need to "change" anything to get a "reversed" version of an existing List.

HIH

Winston
 
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can see the implementation of the OpenJDK Collections.reverse(List). There's no guarantee that the same implementation will be used in the Oracle Java JDK, or any other JDK for that matter, but in the case of OpenJDK it's highly likely (as far as I understand it, the Oracle JDK developers are the primary contributors to OpenJDK)
 
Marshal
Posts: 79177
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote: . . .
One possibility that might be worth considering is a "reversed wrapper" - . . .

Since Collections#reverse has void return type, it cannot produce a wrapper.

The method does not reverse a Collection, but a List, because Lists encapsulate an order which Collections might not specify. Is mentions the set method in the documentation, so it obviously uses set. The correct answer is:

You don't need to know that

… but there is a file in your Java® installation folder called src.zip. If you unzip that, you can find the source code and read it.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Since Collections#reverse has void return type, it cannot produce a wrapper.


True, but that's not what Daniel said his task was. If the "methods" that he's been asked to implement must return void, then plainly they must do the "reversal" in-place, but I didn't see anything about that in the OP.

Winston
 
Sheriff
Posts: 7125
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's a good article about reversing in place.
 
Daniel Gurianov
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you all for the replies.

Tim Cooke, thanks for OpenJDK link. I do not think there is a high chances that Oracle would change reverse in their JDK to something else.
Yes, from OpenJDK it looks that for Collections.reverse() , in any case, it finally boils down to swap elements.


Knute Snortum, thanks for in-place link. It is actually what i ment by "swap reverse", except i did one additional step to control for loop . Now i see that it is actually rudimental and i can get rid from it. Also i will know that it should be called in-place reverse.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not an in‑place technique, but have you ever tried a stack?
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Not an in‑place technique, but have you ever tried a stack?


Oh yer, I'd forgotten about that one. Good thinking, Batman.

Winston
 
Daniel Gurianov
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Not an in‑place technique, but have you ever tried a stack?



As i understood , recursive reverse is kinda stack approach, cause you put elemtns in memory one by one in forward order , and the put them back into object in reverse order, when you reached end of the object.
Also i`m trying to avoid involvement other data structures , assuming that unnecesarry allocating and deallocating will degrade overall performance.
In case stack , i need +1 stack object where to put elements and then get it back as soon as i hit the bottom of Array- or LinkedList.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A recursion actually creates a sort of stack. It uses the standard JVM stack.
No, you will not find using a stack at all slow. You may do well to give the stack a predefined size (same as the List) for quicker execution. You can create a stack object with a capacity of 100000000 if you wish whereas most recursions run out of stack space between 5000 and 10000 levels. And avoid this. Use an implementation of this (e.g. this) (or write your own stack class). You only need one stack object.
 
reply
    Bookmark Topic Watch Topic
  • New Topic