Primeiro, array é diferente de lista.
Em muitos casos, comumente mais informações, o erro de nomenclatura não será um agravante e não prejudicará a comunicação, mas dado que estaremos analisando o funcionamento interno da linguagem julgo ser interessante se ater aos termos corretos. Dadas as perguntas, ficou claro que a dúvida é sobre o funcionamento de listas, não de arrays.
O tipo list
é nativo do Python e foi implementado em C sob a estrutura 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;
Onde temos:
ob_base
, um objeto que representa estruturas de tamanho variável, implementa o campo ob_size
;
ob_item
, um ponteiro para ponteiro de PyObject
;
allocated
, um objeto Py_ssize_t
que representa o tamanho alocado;
Como pode ver - inclusive comentado no código - os itens que compõem a lista no Python serão gerenciados a partir de ob_item
. Ele, por ser um ponteiro, possui a dinamicidade de ser realocado conforme a necessidade de crescimento da lista, em que cada posição apontará para um outro ponteiro PyObject
que representa o item da lista. Vale lembrar aqui que todas as estruturas que o Python implementa herdam de PyObject
, então não haverá restrições do tipo que poderá ser armazenado na lista.
Sempre que o tamanho de uma lista precisa ser alterado, a função list_resize
é invocada; ela que é responsável pela implementação do algoritmo de realocação de uma lista.
O código fonte desta função é:
/* 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;
}
Assim como o Maniero comentou em sua resposta, basicamente o Python aloca um novo espaço de memória já considerando o novo tamanho da lista e considerando espaços de sobra para depois copiar o conteúdo para esse espaço na memória. Perceba que o espaço adicionado ao tamanho da lista será proporcional ao tamanho atual e é feito isso justamente para buscar uma amortização linear no tempo de realocação. Isto é, é mais fácil realocar um espaço maior uma vez e inserir vários elementos do que realocar sempre que for inserir. Perceba também que toda a realocação é feita sobre o objeto items
e não diretamente sobre 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
é uma macro definida por:
#define PyMem_RESIZE(p, type, n) \
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_REALLOC((p), (n) * sizeof(type)) )
Que basicamente faz a realocação de memória no ponteiro especificado.