Qual è la complessità temporale dell'aggiunta di un elemento a una lista Python alla fine, all'inizio e nel mezzo?

In Python, le liste sono implementate come array dinamici, quindi la complessità temporale delle operazioni dipende dalla posizione di inserimento:

• Aggiunta alla fine (list.append(element)) — O(1) ammortizzato, poiché di solito c'è spazio, ma a volte si verifica una ridistribuzione della memoria.
• Aggiunta all'inizio (list.insert(0, element)) — O(n), perché tutti gli elementi vengono spostati a destra.
• Aggiunta a metà (list.insert(index, element)) — anche O(n), poiché gli elementi dopo l'indice vengono spostati.

Pertanto, per aggiunte efficienti all'inizio o a metà, è meglio usare altre strutture dati come collections.deque.