Constant Complexity For Reversing of a List
Join the DZone community and get the full member experience.
Join For FreeI 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/
Opinions expressed by DZone contributors are their own.
Comments