ansaurus

Question

Java - "Rotating" Objects in A LinkedList - Is LinkedList.addLast(LinkedList.removeFirst()) Good Or Bad Programming?

Answer 1

+2 A:

Seems fine to me. If you had a truly circular buffer which was full you could just move the "start/end" index, but I think the linked list approach will work pretty well. In particular it's still O(1).

Jon Skeet 2010-07-21 21:47:43

This is pretty close to what `ArrayDeque` does.

finnw 2010-07-21 22:01:03

Thanks Jon, the "start\end" index is a good idea which I'll look into using. The code I posted is part of the logic behind a sliding-block puzzle I developed in Swing.

The Thing 2010-07-21 22:08:01

Answer 2

+1 A:

I suggest using Collections.rotate.

Tom Hawtin - tackline 2010-07-21 21:49:32

`Collections.rotate` takes O(N) time. `removeFirst`/`addLast` is O(1).

finnw 2010-07-21 21:54:28

This makes the intent clear, but performance wise its much worse. Accessing the first/last element of a linked list and appending/prepending is possible in constant time, while Collections.rotate needs time linear to the list size. Someone should probably create a feature request for a special case for LinkedList.

Jörn Horstmann 2010-07-21 21:57:27

The question doesn't have performance as a requirement. Premature optimisation is the root of all evil, etc. If I was looking to improve performance, there is probably other things that are much more important, like using an array-based structure. So I prefer the better, more robust, less error-prone way of doing the same.

Tom Hawtin - tackline 2010-07-21 22:48:17

@Tom, deciding between O(n) and O(1) algorithms is not premature optimization in my opinion.

Jörn Horstmann 2010-07-22 06:31:53

@Jörn Horstmann I still prefer using the library method. The context we are given is revolves around avoiding errors. O(n) for small n, if another at least O(n) step is going to be performed, if the code is not hot, etc. More likely, something else is going to change to make the funky optimisation bad.

Tom Hawtin - tackline 2010-07-22 11:42:30

Answer 3

+1 A:

I would implement it exactly as you have.

myLinkedList.addLast(myLinkedList.removeFirst());

The only way I can see this being "bad programming" is if the list is shared between threads and your method rotates an element from one end to the other without holding a lock (I am not aware of any concurrent Queue implementation that can rotate atomically.)

finnw 2010-07-21 22:07:08

Thanks for your input, finnw. Even though I'm not a professional coder I always strive to do things correctly, hence my "good \ bad programming?" query.

The Thing 2010-07-21 22:16:47

And the m in front of the variable name.

Steve Kuo 2010-07-21 22:26:39

@Steve Kuo, I suspect that name was made up for the question and is not the real variable name as used in the program

finnw 2010-07-22 10:09:01

@finnw, You are correct regarding the variable name.

The Thing 2010-07-22 20:30:14

ansaurus

tags:

views:

answers:

Java - "Rotating" Objects in A LinkedList - Is LinkedList.addLast(LinkedList.removeFirst()) Good Or Bad Programming?

related questions