Over a million developers have joined DZone.
Platinum Partner

Constant Complexity For Reversing of a List

· Java Zone

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

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/

 

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

Topics:

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}