Scala List.updated

I am curious about List.updated. What is it's runtime? And how does it compare to just changing one element in an ArrayBuffer? In the background, how does it deal with copying all of the list? Is this 开发者_如何学运维an O(n) procedure? If so, is there an immutable data structure that has an updated like method without being so slow?

An example is:

val list = List(1,2,3)
val list2 = list.updated(2, 5) --> # list2 = (1,5,3)
var abuf = ArrayBuffer(1,2,3)
abuf(2) = 5 --> # abuf = (1,5,3)

---

1. The time and memory complexity of the updated(index, value) method is linear in terms of index (not in terms of the size of the list). The first index cells are recreated.

2. Changing an element in an ArrayBuffer has constant time and memory complexity. The backing array is updated in place, no copying occurs.

3. This updated method is not slow if you update elements near the beginning of the list. For larger sequences, Vector has a different way to share common parts of the list and will probably do less copying.

---

List.updated is an O(n) operation (linear).

It calls the linear List.splitAt operation to split the list at the index to get two list (before, rest), then builds a new list by appending the elements in before, the updated element and then the elements in rest.tail.

I'm not sure - this would have to be tested, but it seems that if the updated element was at the start of the list, it may be pretty efficient as in theory getting rest and appending rest.tail could be done in constant time.

---

I suppose performance would be O(n) since list doesn't store index to each element and implemented as links to next el -> el2 -> el3` so only list.head operation are O(1) as fast. You should use IndexedSeq for that purpose with most common implmentation Vector.

Although it doesn't copy any data so only 1 value are actually updated in memory. In general all scala immutable collections dosn't copy all data on modification or creation of updated new instance. It is key difference with Java collections.