Why appending to a list in Scala should have O(n) time complexity?
- by Jubbat
I am learning Scala at the moment and I just read that the execution time of the append operation for a list (:+) grows linearly with the size of the list.
Appending to a list seems like a pretty common operation. Why should the idiomatic way to do this be prepending the components and then reversing the list? It can't also be a design failure as implementation could be changed at any point.
From my point of view, both prepending and appending should be O(1).
Is there any legitimate reason for this?