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.

Answer 1

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.)