Stavros,
> Note that endcons, even if it didn't copy the whole list, would still have
> to *traverse* the whole list since Maxima uses singly-linked lists (as does
> Lisp) so you would still have the n^2 behavior.
Ah, so it must be this list traversal that is responsible for the
observed slowness.
In the Maxima manual the entry for cons says
Returns a new list constructed...
and for endcons,
Returns a new list consisting of ...
which agrees with what you said.
But in the Maxima Book, I read
list2:cons(element,list1) returns a (new) list2, ...
list1 and list2 have a common *shared* tail [emphasize in original]
endcons(element,list) returns an (unshared) list ...
which apparantley disagrees.
John