python list handling and Lisp list handling

[MRAB]

Mark Tarver wrote:
> This page says that Python lists are often flexible arrays
> 
> http://www.brpreiss.com/books/opus7/html/page82.html
> 
> 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
> 
> 'A list is a sequence of elements, but it is not a single primitive
> object; it is made of cons cells, one cell per element. Finding the
> nth element requires looking through n cons cells, so elements farther
> from the beginning of the list take longer to access. But it is
> possible to add elements to the list, or remove elements.'
> 
> (from http://www.chemie.fu-berlin.de/chemnet/use/info/elisp/elisp_7.html)
> 
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.  For example, can I modify a Python
> list non-destructively?  Are they equivalent to Lisp lists. Can CAR
> and CDR in Lisp be thought of as
> 
> def car (x):
>   return x[0]
> 
> def cdr (x):
>   return x[1:]
> 
> The idea of a list in which elements can be accessed in constant time
> is novel to me.
> 
They are usually implemented as resizable arrays. In CPython great care
has been taken to make appending average to constant time; however,
inserting requires the later elements to be shifted up.

In the way they are normally used they are fast.

There are also queues and deques for when you want efficient queue or
deque behaviour.