LINKED LISTS?

[Tim Peters]

[Courageous]
> ...
> I suspect that one of the reasons lists were left out is a certain
> problem I forsee with iterators and list mutatation...

No, Python already bristles with subtleties wrt iterating over a list (this
is c.l.py, so use unqualified "list" with the Python meaning here) while
mutating it (see the Language Reference Manual for details).  It's not links
that cause difficulties, it's the combo of simultaneous traversal and
mutation.

The real reason is that Guido previously worked on the implementation of the
ABC language, which strove for "theoretically optimal" compromises.  While
it wasn't exposed to the user as such, most data structures were implemented
via balanced trees under the covers.  So almost no operation had worst-case
cost worse than O(log n) -- or expected-case case better than that either.
The implementation was excruciating, and simple contiguous vectors ran much
faster in most cases anyway.  Python *generally* favors speeding the usual
case over minimizing the worst case, and for the same reasons a hash table
is almost always a better idea than a search tree.

some-data-structures-are-so-efficient-they've-never-been-
    implemented-ly y'rs  - van-emde tim