Risposta.

Storia del problema

Le liste (list) sono uno dei tipi di dati incorporati di base in Python fin dalle prime versioni del linguaggio. Nel tempo, la loro struttura interna è stata migliorata, in particolare per aumentare le prestazioni e la facilità di programmazione.

Problema

È importante capire che le liste in Python non sono implementate come collegate, ma come array dinamici. Un'erronea interpretazione porta a codice inefficiente o al calcolo errato della complessità delle operazioni.

Soluzione

Le liste sono implementate come array dinamici che aumentano la dimensione della memoria allocata "a scatti" (espandendosi) quando necessario, per evitare costi continui durante l'aggiunta di elementi. Ciò consente di inserire ed eliminare elementi alla fine della lista in tempo ammortizzato O(1). L'inserimento o l'eliminazione all'inizio o in mezzo richiede lo spostamento degli elementi, il che richiede tempo O(n).

Esempio di codice:

my_list = [1, 2, 3]
my_list.append(4)      # Aggiunta alla fine
my_list.insert(1, 'a') # Inserimento per indice
print(my_list)

Caratteristiche principali:

Modifica dinamica delle dimensioni senza allocazione / deallocazione esplicita della memoria da parte dell'utente.
Inserimento ed eliminazione dalla fine — operazione veloce, dall'inizio / dal mezzo — lenta.
La lista può contenere elementi di qualsiasi tipo (eterogeneità).

Domande ingannevoli.

Si può considerare la list in Python un'analogia dell'array in C? Qual è la differenza?

No, l'array in C contiene elementi di tipo fisso, disposti consecutivamente in memoria. La lista di Python è un array di puntatori verso oggetti, ognuno dei quali punta a un oggetto autonomo di tipo arbitrario nella heap.

Cosa succede se si inseriscono elementi all'inizio della lista in un ciclo? È veloce?

No, è lento: all'inserimento all'inizio (position 0), tutti gli elementi esistenti vengono spostati a destra ogni volta. La complessità ammortizzata è O(n) per operazione, per liste grandi porta a un degrado delle prestazioni.

Qual è la differenza tra gli operatori + e append/extend per le liste?

crea una nuova lista, senza modificare le vecchie. append aggiunge un elemento alla fine della lista originale. extend aggiunge alla lista tutti gli elementi da un'altra sequenza, modificando l'oggetto stesso.

lst1 = [1, 2]
lst2 = [3, 4]
lst3 = lst1 + lst2     # lst3 è una nuova lista
lst1.append(lst2)      # lst1 diventerà [1, 2, [3, 4]]
lst1.extend(lst2)      # lst1 diventerà [1, 2, 3, 4], se lst1 non è resettato dopo la precedente append

Errori comuni e anti-pattern

Utilizzare la list per frequenti inserimenti / eliminazioni all'inizio della lista (meglio usare collections.deque)
Aspettarsi erroneamente che la list occupi poca memoria e contenga dati "densi", come gli array C/Java
Inserimento accidentale di una lista dentro se stessa (append lista in se stessa)

Esempio della vita reale

Caso negativo

In un progetto per memorizzare e eliminare continuamente i primi elementi veniva utilizzata la list. È stata notata una notevole lentezza con un grande volume di dati.

Vantaggi:

Facile da iniziare, molti metodi incorporati.

Svantaggi:

Le prestazioni sono diventate scadenti, errori di memoria con un grande volume.

Caso positivo

Dopo aver identificato il problema, abbiamo sostituito la list con collections.deque, che è ottimizzato per tali operazioni.