Come si determina la complessità temporale della rimozione di un elemento che si trova nel mezzo di una lista collegata?

La complessità temporale di rimuovere un elemento dal mezzo di una lista collegata dipende dal fatto che si abbia un accesso diretto a quell'elemento e al suo nodo precedente.

• Se si dispone di un puntatore all'elemento stesso e al nodo precedente (ad esempio, in una lista doppiamente collegata), la rimozione avviene in O(1), poiché è sufficiente riconfigurare i collegamenti.
• Se si ha solo il valore o un puntatore all'elemento senza accesso al precedente, è necessario prima attraversare la lista dall'inizio fino a quell'elemento, il che richiede O(n), dove n è il numero di elementi prima di quello da rimuovere.

Pertanto, in generale, la rimozione dal mezzo di una lista collegata è considerata un'operazione con complessità temporale di O(n), se non si ha un accesso diretto al nodo precedente.