lists and sequences

[Manuel M. Garcia]

On Tue, 15 Oct 2002 14:29:47 +0200, Michal Vitecek <fuf at mageo.cz>
wrote:

(edited)
>> What is a python list? Is it a linked list or a random access structure
>> in contiguous memory?
>> E.g. when does n^2 time happen using it?
>>
>>alist.insert(0, newthing) physically moves len(alist) elements.  Ditto
>>alist.pop(0).
>
> why ditto for alist.pop(0)? is it because there can be multiple
> references to the same list/address?

No, because all those references that are the elements of the list
have to be all shifted down 1.

In the Vaults of Parnassus, I found an implementation of a linked list
'linked.py' (written in Python)

http://py.vaults.ca/apyllo.py?find=linked+list

Boy howdy, the list would have to be massive before you would get any
speed gain from this implementation, and a penalty of memory lost with
3 pointers stored for each item.

Some basic list operations in Python technically take n^2 time, but
are implemented in C with very tight loops, so the lists would have to
get very large before the time spent was even measurable.  And the
speed lost in doing insertions in this manner is gained back by making
element access so darn fast.

I don't know of a C extension implementation of a linked list.
Probably because the built-in Python dictionary type works so well.
What other languages would do with a linked list, Python probably
would do with a dictionary.