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

[Tim Peters]

...

[Tim Peters]
>> I'm sure he did ;-)  Consider a very simple graph, a skinny tree
>> rooted at `A` that branches once "at the end", represented by a dict
>> of adjacency lists:

[Josiah Carlson]
> Are you sure?

Of what?

> ...

> But one doesn't _need_ to use flat lists.

Of course not.  You didn't mention that in the message of yours to
which Martin replied, and neither did James mention it in his message
to which I replied, and you shouldn't feel put upon that people
respond to what's actually written ;-)

[Tim, to James]
>> You seem to be ignoring possiblities for sharing across lists, and
>> such sharing is natural in many graph algorithms.

> Not necessarily so as I have pointed out above.

Gimme a break.  James didn't mention any such thing, and I was replying to him.

> You said yourself; practicality beats purity.  While using cons cells are pure, as
> us using only flat lists are pure, flat lists are practically smaller than cons
> cells in certain cases (by a factor of ~4), and non-flat lists can be
> smaller than cons cells in the rest of the cases.

Yes.  Nevertheless, most people are going to use flats lists or pure
two-tuples in practice, simply because the coding for each is very
simple, and the idea that using flat lists "is better" was worth
opposing (because it isn't always true, and isn't even commonly true
in many graph algorithms, but was so strongly advanced in the message
to which I replied that using two-tuples instead was characterized as
"pretty crazy").