How does list() work in Python?

Question

Python

I got into an argument with a teacher. It says list in Python is a list.

I say that this is not so, if only because there is a function for taking an element by index. He said that the [] operator could be overloaded (he's not sure about that himself). Indeed, it is possible. Then I told him that the elements of list() are stored sequentially in memory (due to which there is access by index), but to this he sent me to understand the Python memory device, arguing that if it were an array, all elements would be similar (quite logically).

In the Python code, I found the following structure.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

As you can see from the code, ob_item is a dynamic array of pointers to stored objects, allocated is the amount of allocated memory.

Do I understand correctly what listexactly this structure represents in memory?
Whether I can assert on the basis of representation of the given structure that elements listlie in memory sequentially?
Can I conclude that list is still a normal dynamic array whose objects are of type PyObject, and the PyObject fields already define the type of the specific stored object?

Answer 1

https://docs.python.org/2/faq/design.html#how-are-...

How are lists implemented in CPython?¶
CPython's lists are really variable-length arrays, not Lisp-style linked lists. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array and the array's length in a list head structure.
This makes indexing a list a[i] an operation whose cost is independent of the size of the list or the value of the index.
When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don't require an actual resize.

In short, a dynamic array. A contiguous array of pointers to objects

Answer 2

When you are programming in python, it doesn't matter how the list is implemented inside, the main thing is that it does what is required of it.
It could well be implemented as a linked list. Such an implementation does not cancel the operation of taking an element by index.
Taking an element by index in python is not at all taking an element by index in a C array.
All operations in python (including taking an element by index) simply call the corresponding handler functions. In functions, there can be any kind of logic from Sish's taking an element by index, to passing the list to the desired element, etc.
The Python implementation of each type fills in the structure of function pointers that implement the Python operations for that type. You will reach this structure if you continue to dig PyObject_VAR_HEAD.
PS: Your conclusions based on the python list structure are correct.
Not bad for a 1st year student!