Lists implemented as integer-hashed Dictionaries?

[Christian Heimes]

er schrieb:
> Somebody much more intelligent than I said today that someone told him that
> Python lists are just dictionaries with lists hashed by integers.  Since he
> said that someone else told him this, I piped up and said that I thought
> that wasn't true.  I looked at the source code for lists in python, and I
> did not expressly remember seeing dictionaries.  Unfortunately I am not
> somewhere where I can easily look at the code right now (I'm logged into
> Windows!), and I might not realize exactly what I'm looking at anyways, but
> I'd like to extend an apology to the guy soon if I was wrong.  So, can
> anyone tell me if lists are really just dictionaries?  Thanks!

I like to add some technical information to the topic.

In CPython (the most common implementation of Python in C89) lists are
implemented as arrays of PyObject* pointers with a non linear growth
rate. They are neither implemented as linked lists or as hash maps.

The array based implementation makes the most common operations as fast
as possible: creation of a list with a known size of elements,
iteration, item access, appending and popping from the tail of a list.
Iteration and item access (somelist[1]) is a O(1) op.
The internal array grows non linear and is usually over-allocated. This
makes appending to the end faster because the array doesn't need to be
copied with every append().

Uncommon operations like inserts at the head of the lists are slower and
require more memcopy ops. CPython has a deque implementation in the
collections module with is optimized for both changing both ends of a
list like object.

Christian