Internals and complexity of types, containers and algorithms

[Harald Luessen]

Hi, I am new to python and I miss some understanding of the internals 
of some types and containers. With my C/C++ background I hope to get 
some hints to chose the best data structure for my programs. Here are 
some questions:

- Is there a brief description (not source) how the types tuple, 
string, list and dict are represented internally. Is a list behind 
the scenes just a double linked list or an array or a mixture of 
these things? Is a dict a tree or a hash array and what is the 
collision mechanism? Is the string an array with some header info?

- What is the big-O complexity of the most common algorithms for 
these types and containers? Is it O(n), O(n*log(n)) or O(n**2)? 
I mean inserting, appending (front or back), finding something 
and so on.

- The same questions for important and common library containers 
if you can name some.

- Is this information somewhere in the web? Why is it not written 
in the documentation?

- When I want to use a representation of a game board like chess 
in C/C++ I use an array[64] or bigger of int or char for the pieces. 
What data structure or type would be useful in Python when the 
performance ist most important? Is it list or string or an array 
from a library or what else?

Harald