Thx to @dardoro for the analysis, and @jens for the super-fast resolution!
Perhaps because linked lists are only created when using or - my guess is many Snap! users don’t apply those at all - and are subsequently converted to dynamic arrays by some other operations, so they often won’t survive very long.
In Snap!, a linked list is merely one of two implementations of the list data type (dynamic array being the other one). It’s all “under the hood”: ordinary users like you and I won’t notice the difference, except for manipulation of dynamic arrays being generally somewhat faster.
From what I’ve understood @bh, who is a trained mathematics educator, has been a proponent of linked lists - being a very elegant concept, quite memory-efficient, and supposed to pre-eminently support data insertion at the head of a list, such as applied in many recursive functions.
In practical use operations on dynamic arrays are nearly always as fast as on linked lists, or in several cases (e.g. COMBINE), much faster. Only when very large lists are involved (like 10,000 items or so) creating a linked list item-by-item through recursion may be a little faster than creating a dynamic array in similar fashion.
The linked list implementation is only reported by IN FRONT OF and ALL BUT FIRST OF. Some other operations subsequently manipulating the same list will report a list implemented as dynamic array.
Yes. Except for the memory-efficient part; a linked list takes ≈ twice the storage of an array (dynamic or otherwise) because of the pointers.
It's only when writing a recursive reporter that linked lists are more efficient than arrays. In practice nobody writes recursive reporters that traverse lists, and rightly so, because arrays+iteration is way faster. Recursion is important in practice only when traversing a tree or other branched structure.
But understanding recursion is important in education (which is really the business we're in) because you don't really understand procedure calling or scope of variables until you thoroughly understand recursion. And because it's beautiful, one control structure to rule them all.
IN FRONT OF always returns a linked list. LIST always returns an array. The others mostly return the same kind of list you give them as input.
The above paragraph, though, is complicated by the fact that a list can be mixed format, with linked pairs at the beginning of the list, but with a cdr (an ALL BUT FIRST) that points to an array. (This happens when you IN FRONT OF an array.)
At least in theory linked lists are memory efficient insofar as they may use multiple fragments of available memory ("leftovers"). On the other hand - again: theoretically - total memory requirement of a linked list is about twice the size of an array's, because of the pointers. But I'm not sure of either assumption as to how it is actually implemented in Snap! ... (to be completely honest: I had asked our mutual ai-cquantance ChatGPT for advantages of linked lists, and simply ~ed that)
I guess it varies, even though it's really hard to say because (linked list vs. dynamic array) is "under the hood" for us ordinary users. What a user can do is apply as a test tool, since with large lists execution is significantly faster if one is implemented as a dynamic array.
As far as I have been able to measure, and report (at least partially) linked lists. I thought I understood how other reporters implement output lists, but I tested some of these assumptions just now and I'm at a complete loss.
I suppose any branched structure must use at least as many pointers as there are branches. But I'm not even convinced a structure fully implemented through linked lists is more efficiently processed than the same logical structure implemented as dynamic arrays wherever possible and only necessary pointers.
that will check for you. (Technically it just checks whether the first item is linked to the second one, so it reports True for a mixed-format list as described above.
You're trading off testing for "necessary" on each node with following pointers. The latter is a trivial fixed cost, so you're not likely to come out ahead, except maybe in situations in which the analysis can be done ahead of time.