Qual è la misura di complessità dell'algoritmo per aggiungere un elemento all'inizio di una lista doppiamente collegata?

L'aggiunta di un elemento all'inizio di una lista doppiamente collegata viene eseguita in tempo costante, cioè con una complessità O(1).

Ciò è dovuto al fatto che una lista doppiamente collegata ha un puntatore al primo elemento (testa), e per inserire un nuovo elemento basta:

1. Creare un nuovo nodo.
2. Impostare il suo puntatore next sull'attuale primo elemento.
3. Impostare il puntatore prev dell'attuale primo elemento sul nuovo nodo.
4. Aggiornare il puntatore della testa della lista al nuovo nodo.

Tutte queste operazioni non dipendono dalla dimensione della lista, quindi la complessità è — O(1).