True lists in python?

[TomF]

On 2010-12-18 22:18:07 -0800, Dmitry Groshev said:

> Is there any way to use a true lists (with O(c) insertion/deletion and
> O(n) search) in python? For example, to make things like reversing
> part of the list with a constant time.

I assume you mean a C extension that implements doubly linked lists 
(reversing part of a list is only constant time if the list is 
doubly-linked).  I'm not aware of one.

A longer answer is that many high level languages (Python, Perl, Ruby) 
don't bother implementing simple linked lists because they're not very 
useful.  Instead they use hybrid data structures that can operate as 
lists and arrays with flexibility and acceptable costs.  And if you 
need greater speed you usually go to special purpose arrays (for 
constant time access) rather than lists.

-Tom