[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Reverse pop, return value

From: LanX
Subject: Re: Reverse pop, return value
Date: Tue, 17 Nov 2009 09:33:27 -0800 (PST)
User-agent: G2/1.0


On 17 Nov., 17:53, David Kastrup <address@hidden> wrote:
> Reversing is O(n), popping from the front O(1), so working off the whole
> list is O(n).  Popping from the end is O(n), making work on the whole
> list O(n^2).

Thx David, good point!

I will keep it in mind for cases where I can't control that lists are

Anyway my motivation was more to learn basic things like (prog1)!

Personally I prefer to delay optimizations (and potential complication
of the code) to the point when profiling shows the need for it.

But just from curiosity, having a FIFO stack situation (without
clearly separated IN/OUT-phases where I can just reverse once) , whats
the optimized way to push and pop then?

Maybe always keeping a pointer to the end of the list?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]