[Python-Dev] deque alternative (was: Linked lists)

[Martin Blais]

On 12/25/05, Josiah Carlson <jcarlson at uci.edu> wrote:
>
> Tim Peters <tim.peters at gmail.com> wrote:
> > Like Phillip Eby, I use 2-tuples for this when I feel the need
> > (usually during a backtracking graph search, to keep track of paths
> > back to the root in a space-efficient way), and am happy with that.
>
> Then there's the whole Python list with append() and pop().  It takes a
> method resolution and function call, but at least in Python 2.3, it is a
> hair faster...

Josiah, that's beside the point, because it is not space-efficient,
the list is actually an dynamic array/vector, and I would expect an
efficient array implementation to grow exponentially.  One of the
reasons we're talking about lists is to avoid exactly this problem...