Complexity of List.reverse?

Question

In Scala, there is reverse method for lists. What is the complexity of this method? Is it better to simply use the original list and always remember that the list is the reverse of what we expect, or to explicitly use reverse before operating on it.

EDIT: What I am really interested in is to get the last two elements of the original list (or the first two of the reversed list).

So I would do something like:

val myList = origList.reverse
val a = myList(0)
val b = myList(1)

This is not in a loop, just a one-time thing in my library... but if someone else uses the library and puts it in a loop, it is not under my control.

`Is it better` isn't answerable without a goal, what to reach, and details of circumstances. — user unknown, Sep 02 '11 at 13:00
I am wondering why you write "always remember that the list is the reverse of what we expect". You should never have to "remember" something is different from expected. This is an error waiting to happen. So even if it hurts performance wise you should work with a list in its expected order. This leads to the question why the list is the reverse of what you expect. Maybe you should create the list in a different way from the start, or use something else then you won't have to reverse it. See http://stackoverflow.com/questions/1241166/preferred-way-to-create-a-scala-list — Ido Tamir, Sep 02 '11 at 16:31
@ user unknown. I agree. I had assumed implicitly that `better` implies efficient. But what I was really interested in was the complexity. I have edited the question. But the answer below may be useful for someone. — Jus12, Sep 02 '11 at 16:34
@Ido Tamir: I edited the question to describe what I do. Hope that answers your question. I think the suggestion to use reverse is a good idea, since the code is never called in a loop. — Jus12, Sep 05 '11 at 12:27

Andrzej Doyle · Accepted Answer · 2011-09-02T15:55:28.540

Looking at the source, it's O(n) as you might reasonably expect:

override def reverse: List[A] = {
  var result: List[A] = Nil
  var these = this
  while (!these.isEmpty) {
    result = these.head :: result
    these = these.tail
  }
  result
}

If in your code you're able to iterate through the list in reverse order at the same cost of iterating in forward order, then it would be more efficient to do this rather than reversing the List.

In fact, if your alternative operation which involves using the original list works in less than O(n) time, then there's a real argument for going with that. Making an algorithm asymptotically faster will make a huge difference if you ever rely on it more (especially if used inside other loops, as oxbow_lakes points out below).

On the whole though I'd expect that anything where you're reversing a list means that you care about the relative ordering of a non-trivial number of elements, and so whatever you're doing is inherently O(n) anyway. (This might not be true for other data structures such as a binary tree; but lists are linear, and in the extreme case even reverse . head can't be done in O(1) time with a singly-linked list.)

So if you're choosing between two O(n) options - for the vast majority of applications, shaving a few nanoseconds off the iteration time isn't going to really gain you anything. Hence it would be "best" to make your code as readable as possible - which means calling reverse and then iterating, if that's closest to your intention.

(And if your app is too slow, and profiling shows that this list manipulation is a hotspot, then you can think about how to make it more efficient. Which by that point may well involve a different option to both of your current candidates, given the extra context you'll have at that point.)

Thanks. I will do `reverse` to make the code more readable. The lists in my case are less than 100 elements. — Jus12, Sep 02 '11 at 12:00
True, but if you are calling `List.reverse` upon each iteration of some loop, you have a O(n^2) algorithm, which could be problematic — oxbow_lakes, Sep 02 '11 at 12:45
if performance is a concern, and you want to access the list multiple ways, you can use a different structure, like maybe immutable `Vector`, or for numerical code, `Array` to avoid boxing. — Kipton Barros, Sep 02 '11 at 13:41
@oxbow_lakes: In that situation, it's still O(n^2) whether you call reverse, just iterate through the list backwards, or do *anything* that involves an O(n) operation for each loop iteration. Based on the context of the question it seems fair to assume that whatever the alternative is that involves the original list, it would also be O(n). If not, and the alternative is O(1) or O(lg n), then it should likely be used in any case. — Andrzej Doyle, Sep 02 '11 at 15:19
@Andrzej - indeed, that is true. I was just saying that there is a difference between losing nanoseconds doing some re-computation (or boxing or whatever), and losing them because you have chosen a structure providing O(N) performance instead of O(1) for the operation you need. In my experience, O(N) can hurt, which is why `Set.++` is unusable (for certain algorithms) using scala 2.9.0 (fixed in 2.9.1) — oxbow_lakes, Sep 02 '11 at 15:25

Complexity of List.reverse?

1 Answers1