Hacking on GraphHopper - a Java road routing engine. Peter has posted 62 posts at DZone. You can read more from them at their website. View Full User Profile

Constant Complexity For Reversing of a List

03.28.2010
| 5594 views |
  • submit to reddit

I am reading this question on stack overflow and it was irritating for me that the most people say: reversing a linked list is possible only in O(n). Okay, this is true for a single linked lists, but not for double linked lists like I will show you with my quick and dirty CarouselList:

The key point is the incrementer/decrementer:

static class Incrementer<T> {

Node<T> getNext(Node<T> node) {
return node.next;
}

Node<T> getStart(Node<T> head) {
return head;
}
}

static class Decrementer<T> extends Incrementer<T> {

@Override
Node<T> getNext(Node<T> node) {
return node.previous;
}

@Override
Node<T> getStart(Node<T> head) {
return head.next;
}
}

This way the ‘iteration order’ can be easily switched in O(1). Of course this comes to the cost of a bit more expensive iteration but this is another issue …

If the implementation could use an ArrayList (not a linked list) it would be more simple: return different iterators based on a ‘reverse’ attribute. Then either return an iterator with counter++ or return one with counter– if reverse == true

From http://karussell.wordpress.com/2010/03/27/constant-complexity-for-reversing-of-a-list/

 

Published at DZone with permission of its author, Peter Karussell.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Artur Biesiadowski replied on Sun, 2010/03/28 - 6:31am

Following this logic, sorting a list is a O(1) operation, as I can prove with my SortedButNotSorted list, which sorts the elements on insert, but keeps insertion order until you call 'sort' when it changed the order to prepared sorted one.

Almost any operation can be made 'instantaneous' if you want to spend time to prepare for it in advance. 

I think that you can surprise people more with O(n) sorting of integers (radix/bucket sort) rather than reversing double linked list in O(1)...

Peter Karussell replied on Sun, 2010/03/28 - 7:56am in response to: Artur Biesiadowski

Sorting on insertation costs time! Or how is e.g. TreeMap implemented? Also see the comments on the original post:  ... this post was only to show that reversing of a linked list could be done in O(1). I mean that it is possible, not that it should be done nor that this is fast. i didn't tested this. okay? :-)

Stefan Kendall replied on Sun, 2010/03/28 - 8:53pm in response to: Artur Biesiadowski

 

The key point is that the cost of iterating over the list in a reverse fashion is a constant time incursion, which lowers the combined complexity of iteration/reversal. This isn't precalculation or some dumb/non-practical trick. It's a real solution for applications which need very quick (rapid) reversal of large lists. This use case is probably unlikely, but it could happen.

Artur Biesiadowski replied on Mon, 2010/03/29 - 3:03am

It is a precalculation. You are storing backward pointers on each node, just in case somebody would like to traverse it in different order. It has both performance (very small) and memory (more considerable) cost. Only thing which is different here to my pre-sort example is that all operations on list stay with same O() complexity - but the constant is changing.

Please note that stack overflow thread is named "Reverse a singly linked list". Answering to this with "I have implemented 'single-linked list' with backward pointers" is not really on topic. Posting the discovery of double linked list on javalobby...

I'm soon expecting new answers following this reasoning:

"How to sort long file with numbers very fast" - Sort it in advance, save to different file and use it

"How to get from point A to B by car" - Take a plane

"How to implement wavelet compression" - You don't to it, there is a shareware program for ripping DVDs at http://xyz

All these answers are maybe proper, just not on topic. And posting on javalobby about how strange/stupid people are not to give points to you 'proper' answer is just plain wrong.

 

Peter Karussell replied on Mon, 2010/03/29 - 4:32am in response to: Artur Biesiadowski

@artur see my comment on dimitris comment

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.