3 Made title
source | link

Why does appending to a listList in Scala should have O(n) time complexity?

I am learning Scala at the moment and I just read that the execution time of the append operation for a list List (:+) grows linearly with the size of the listList.

Appending to a listList 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?

Why appending to a list in Scala should have O(n) time complexity?

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?

Why does appending to a List in Scala have O(n) time complexity?

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?

    Tweeted twitter.com/#!/StackProgrammer/status/398161606770954240
2 edited tags
| link
1
source | link

Why appending to a list in Scala should have O(n) time complexity?

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?