On Mon, Nov 28, 2022 at 11:58:27PM +0100, Emanuel Berg wrote:
> Stefan Monnier via Users list for the GNU Emacs text editor wrote:
> 
> > Add them in the reverse order and finish with a simple
> > `reverse`. That's a very standard design pattern with
> > singly-linked lists (and in many/most cases the final
> > `reverse` can be an `nreverse`).
> 
> I thought about `nreverse' but if that changes all the CDRs
> then that's linear as well i.e. O(n), otherwise you could do
> nreverse, `push', and nreverse again ...

The pattern is push, push, push, push... nreverse.

Amortized costs, it's called. It makes O(n^2) into O(n).

Cheers
-- 
t