[Tutor] C Implementation of data structures

[VanL]

Hello,

I was wondering about the underlying (C) implementation of tuples and
dictionaries.  I know that lists are dynamically sized arrays, and as
such are O(1) for retrieval and O(n) for search and insert operations.

What about tuples and dictionaries?  Dictionaries would seem to fit
naturally onto hash tables, but a note in Programming Python mentioned
that the __getattr__ method, which allows searching by key, works by
repeatedly indexing the object.  This would suggest another array.

In a similar vein, I don't know how user-defined data structures are
implemented either.  Conceivably, an (apparently) efficient structure
could be hampered by an inefficient (at least for the purpose)
underlying implementation.

I'm not trying to call Guido's experitise as a language designer into
question, I'm just trying to understand better how things fit together. 
Could anyone enlighten me on the underlying implementation of Python's
data structures?

Thanks,

V