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

Advertisements

>Of course this comes to the cost of a bit more expensive iteration

that means, you shifted the cost of reversing the list from construction time to iteration time.

the whole point of any java implementation to reverse a list would be to work within the List interface.

see Iterators.reverse() in google-collections for an example on how to do it within the java api.

> that means, you shifted the cost of reversing the list from construction time to iteration time.

not really. it depends on your usecase. I needed a fast reverse algorithm and iterate only a few times over the edges.

> Iterators.reverse()

yes. that’s the point. But I only wanted to say in public that setReverse(false) is O(1) and not O(n) 🙂

Stating this on a thread titled “Reverse a *singly* linked list”, and getting irritated at people who are right? Fail. Plus a minor irritation for allowing things like “Incrementer incrementer = new Decrementer();”.

By the way, the method is Iterables.reverse().

@Dimitris yes, you are right. he says “what would be the best logic to reverse a singly linked list, in terms of time complexity?” I recognized the “Is there any other alternate to reverse the linked list?” as more important. Sorry for confusion. My fault.

Pingback: Tweets that mention Constant Complexity For Reversing of a List « Find Time for the Karussell -- Topsy.com