First, array is different from list. https://pt.stackoverflow.com/q/171023/5878 In many cases, commonly more information, the nomenclature error will not be an aggravating and will not harm the communication, but since we will be analyzing the internal functioning of the language I think it is interesting to stick to the correct terms. Given the questions, it became clear that the doubt is about the functioning of lists, not of arrays.The guy list is native to Python and was implemented in C under the structure PyListObject.typedef struct {
PyVarObject ob_base;
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
Where we have:ob_base, an object representing variable size structures, implements the field ob_size;ob_item, a pointer for pointer PyObject;allocated, an object Py_ssize_t which represents the allocated size;As you can see - including commented on the code - the items that make up the list in Python will be managed from ob_item. It, because it is a pointer, possesses the dynamism of being relocated according to the need for growth of the list, in which each position will point to another pointer PyObject which represents the item of the list. It is worth remembering here that all the structures that Python implements inherit from PyObject, then there will be no restrictions of the type that can be stored on the list.Whenever the size of a list needs to be changed, the function list_resize is invoked; it is responsible for implementing the relocation algorithm of a list. https://pt.stackoverflow.com/q/319164/5878 The source code of this function is:/* Ensure ob_item has room for at least newsize elements, and set
ob_size to newsize. If newsize > ob_size on entry, the content
of the new slots at exit is undefined heap trash; it's the caller's
responsibility to overwrite them with sane values.
The number of allocated elements may grow, shrink, or stay the same.
Failure is impossible if newsize <= self.allocated on entry, although
that partly relies on an assumption that the system realloc() never
fails when passed a number of bytes <= the number of bytes last
allocated (the C standard doesn't guarantee this, but it's hard to
imagine a realloc implementation where it wouldn't be true).
Note that self->ob_item may change, and even if newsize is less
than ob_size on entry.
*/
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
/* This over-allocates proportional to the list size, making room
for additional growth. The over-allocation is mild, but is
enough to give linear-time amortized behavior over a long
sequence of appends() in the presence of a poorly-performing
system realloc().
The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
if (newsize == 0)
new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
PyMem_RESIZE(items, PyObject *, new_allocated);
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}
Just as Maniero commented in his response, Python basically allocates a new memory space already considering the new size of the list and considering plenty of spaces to then copy the content to that space in memory. Note that the space added to the size of the list will be proportional to the current size and it is done precisely to seek a linear amortization in the relocation time. That is, it's easier to relocate a larger space once and insert multiple elements than relocating whenever you enter. Also note that all relocation is made on the object items and not directly on self->ob_item:items = self->ob_item;
if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
PyMem_RESIZE(items, PyObject *, new_allocated);
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
PyMem_RESIZE is a macro defined by:#define PyMem_RESIZE(p, type, n)
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL :
(type *) PyMem_REALLOC((p), (n) * sizeof(type)) )
That basically makes memory relocation on the specified pointer.
