Like if I want to access an array element in C it's implemented like this: For example: If a = {0, 1, 2, 3} is an array if I want to access index number 2 I will write a[2] and the formula that is implemented internally is (a+2*sizeof(int)) to get the starting address of the index number 2.

But this can be done because we know the size of every element in array is fixed.

But this is not the case in python lists we can store variable sized objects in lists.

So my question is how does python get access to a particular index position in lists? Is the time complexity O(1) like in C??


Every Python value, be it an object, tuple, int, or None, is represented as a PyObject* in C. Because this is a pointer, all these values have the same size (even if the PyObject structure may have different sizes, depending on what it represents). (See: Include/object.h)

So a Python list internally holds a C array of type PyObject**, which allows O(1) access along the ordinary C rules. (See: Include/listobject.h, and PyList_GetItem() in Objects/listobject.c)

This technically only holds for the CPython reference implementation, but other implementations will be similar. The crucial point is that the Python language defines its own data model and type system that does not fit directly into the C type system.

Because using Python objects can be wasteful, the NumPy library provides densely packed arrays. But these now have an explicit type for all values. If you have a NumPy ndarray of type float, you cannot store ints in that array.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.