How does list indexing work under the hood in Python3?

Question

Let's say we have

a = [1, 2, 3]

Whenever I use index in list like 0, 1, 2 in this case, How does python3 retrieve element by knowing the index? Is there any specific address for each element inside the list under the hood other than index?

Answer 1

the arrays (list in python) technically store pointers rather than the objects themselves, which allows the array to contain only elements of a specific size even with mixed types list in python.

from python docs:

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.

source: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython

more explanation :

---

what is a pointer?

A pointer is a variable that stores a memory address. Pointers are used to store the addresses of other variables or memory items.

and how indexing work ?

a[i] means the same as (p + i) when p represents pointer to the first element of an array: *(a + i) so if a pointer p points to an element of an array, then adding n to the pointer makes it point at the nth element following the original one. this involved adding or subtracting the correct offset (based on the size of a reference) in bytes between objects.

the size of a reference same as word size for the CPU 4 bytes on a 32bit system, and 8 bytes on a 64bit system

memory representation of array of pointers

hope this clear things to you .. this is my first answer for me in stackoverflow, vote up if it is helpful. thank you.