Qual é a diferença entre um array e uma lista?

O array tem um tamanho fixo, determinado na sua criação. A lista ajusta dinamicamente o seu tamanho ao adicionar ou remover elementos.

O acesso aos elementos do array é feito por índice em O(1). O acesso aos elementos da lista pode variar, por exemplo, uma lista ligada simples tem acesso por índice em O(n), enquanto o ArrayList em média em O(1).

Num array, os elementos são armazenados em áreas contínuas de memória, o que garante um melhor desempenho de cache. Num lista, os elementos podem estar dispersos na memória, ligados por ponteiros.

Operações de inserção e remoção no meio do array requerem deslocar todos os elementos seguintes, o que pode ser dispendioso (O(n)). Nas listas, estas operações podem ser mais eficientes (por exemplo, em listas ligadas O(1) se houver um ponteiro para o elemento, caso contrário O(n) para procurar), mas requerem atualização dos ponteiros.

Os arrays podem armazenar tipos primitivos diretamente. As listas normalmente armazenam referências a objetos (envoltórios para tipos primitivos).

// Exemplo de array
int[] array = new int[5];
array[0] = 10; // Acesso O(1)

// Exemplo de ArrayList (lista em Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Adicionar O(1) em média
list.get(0); // Acesso O(1) em média

# Exemplo de array (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Tamanho fixo

# Exemplo de lista
dados_lista = [1, 2, 3]
lista_dados.append(4) # Tamanho dinâmico

lista_dados[0] # Acesso O(1)

Comparação:

Característica	Array	Lista
Tamanho	Fixo	Dinâmico
Acesso por índice	O(1)	Varia (frequentemente O(1) ou O(n))
Memória	Contígua	Pode estar dispersa
Inserção/Remoção	O(n) no meio	Varia (pode ser O(1))
Tipos de dados	Primitivos e objetos	Normalmente referências a objetos