python list handling and Lisp list handling

Daniel Stutzbach daniel at
Mon Apr 27 21:18:58 CEST 2009

On Fri, Apr 24, 2009 at 10:19 AM, Mark Tarver <dr.mtarver at>wrote:

> but also says that their representation is implementation dependent.
> As far as I see this should mean that element access in Python should
> run in constant time.  Now if so this is a boon, because generally

When I first learned Python, I too was confused by the fact that Python
lists are actually arrays (or vectors) under-the-hood, and it was some time
before I learned that element access is fast (O(1)) but inserts, deletes,
and taking a sublist are slow (O(n)).

Much later, I went on to write a drop-in replacement type called the "blist"
that has the same methods as a Python list, but has better asymptotic
performance for many operations.  That way I can write use the list in the
most natural way without having to worry about accidentally hitting a O(n)

Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Python-list mailing list