Qual è la differenza tra un array e una lista?

L'array ha una dimensione fissa, determinata al momento della creazione. La lista modifica dinamicamente la sua dimensione aggiungendo o rimuovendo elementi.

L'accesso agli elementi dell'array avviene tramite indice in O(1). L'accesso agli elementi della lista può variare, ad esempio, una lista collegata semplice ha accesso tramite indice in O(n), mentre ArrayList in media in O(1).

In un array, gli elementi sono memorizzati in aree di memoria continue, garantendo un miglior performance della cache. Nella lista, gli elementi possono essere dispersi in memoria, collegati da puntatori.

Le operazioni di inserimento e rimozione nel mezzo dell'array richiedono di spostare tutti gli elementi successivi, il che può essere costoso (O(n)). Nelle liste, queste operazioni possono essere più efficienti (ad esempio, nelle liste collegate O(1) se si ha un puntatore all'elemento, altrimenti O(n) per la ricerca), ma richiedono l'aggiornamento dei puntatori.

Gli array possono memorizzare direttamente tipi primitivi. Le liste di solito memorizzano riferimenti a oggetti (wrapper per tipi primitivi).

// Esempio di array
int[] array = new int[5];
array[0] = 10; // Accesso O(1)

// Esempio di ArrayList (lista in Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Aggiunta O(1) in media
list.get(0); // Accesso O(1) in media

# Esempio di array (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Dimensione fissa

# Esempio di lista
dati_lista = [1, 2, 3]
lista_dati.append(4) # Dimensione dinamica

lista_dati[0] # Accesso O(1)

Confronto:

Caratteristica	Array	Lista
Dimensione	Fissa	Dinamica
Accesso per indice	O(1)	Variabile (spesso O(1) o O(n))
Memoria	Contigua	Può essere dispersa
Inserimento/Cancellazione	O(n) in mezzo	Variabile (può essere O(1))
Tipi di dati	Primitivi e oggetti	Di solito riferimenti a oggetti