[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Easy to add with push but not to the end of a list
|
From: |
tomas |
|
Subject: |
Re: Easy to add with push but not to the end of a list |
|
Date: |
Wed, 30 Nov 2022 15:10:51 +0100 |
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
signature.asc
Description: PGP signature
- RE: [External] : Easy to add with push but not to the end of a list, (continued)
- Re: Easy to add with push but not to the end of a list, tomas, 2022/11/29
- Re: Easy to add with push but not to the end of a list, Heime, 2022/11/29
- Re: Easy to add with push but not to the end of a list, Marcin Borkowski, 2022/11/29
- Re: Easy to add with push but not to the end of a list, Heime, 2022/11/29
- Re: Easy to add with push but not to the end of a list, Emanuel Berg, 2022/11/30
- Re: Easy to add with push but not to the end of a list, Emanuel Berg, 2022/11/30
- Re: Easy to add with push but not to the end of a list, tomas, 2022/11/29
- Re: Easy to add with push but not to the end of a list, Emanuel Berg, 2022/11/30
- Re: Easy to add with push but not to the end of a list, Marcin Borkowski, 2022/11/29
- Re: Easy to add with push but not to the end of a list, tomas, 2022/11/29