Not just trees; any operation that involves mutating or manipulating list-like structures is more efficient than arrays.
Some examples:
Removing an element is delinking a single cons cell, vs either copying to a new array or shuffling all subsequent elements left. It also doesn’t break any references to list cells, even the removed cell.
Slicing, at minimum, only requires having the cons cell at the new head of the list; rather than either a special datastructure to represent a slice, or copying to a new array.
Filtering means pulling cons cells from a nursery on an ad-hoc basis, using them to collect filtered elements into a new list of unknown length. With an array, you need a pre-allocated buffer that either sets a limit on the size of the filtered set, or requires reallocation on resize with a O(n) copy.
Just, in general, you can be a lot more relaxed with flinging data around lists without having to think about the algorithmic overhead of allocating, reallocating, copying and shuffling arrays.
Not just trees; any operation that involves mutating or manipulating list-like structures is more efficient than arrays.
Some examples:
Removing an element is delinking a single cons cell, vs either copying to a new array or shuffling all subsequent elements left. It also doesn’t break any references to list cells, even the removed cell.
Slicing, at minimum, only requires having the cons cell at the new head of the list; rather than either a special datastructure to represent a slice, or copying to a new array.
Filtering means pulling cons cells from a nursery on an ad-hoc basis, using them to collect filtered elements into a new list of unknown length. With an array, you need a pre-allocated buffer that either sets a limit on the size of the filtered set, or requires reallocation on resize with a O(n) copy.
Just, in general, you can be a lot more relaxed with flinging data around lists without having to think about the algorithmic overhead of allocating, reallocating, copying and shuffling arrays.