I see doc’s about List write as: “fast at getting the tail”, so write to tail is also O(1)?
‘append’ is not ‘writing to the tail’. The ‘tail’ of a list is the list of elements excluding the first or ‘head’ element of the list.
If you want a performant ‘append’ operation you should probably be using an array, not a list.
5 Likes
If you’re trying to build a list of values one by one and want to keep elements in the order you added them, you could add the values to the head one at a time and reverse the whole thing at the end.
It’s more expensive than using an array but the whole thing would still be O(n) so it’s a useful trick if you need immutability for some reason.
1 Like