Perché gli elenchi collegati sono considerati O (1) per inserimento/eliminazione in medio mentre gli array dinamici sono considerati O (N)?

Question

Sto lottando per capire perché gli elenchi collegati sembrano essere accettati per avere prestazioni Big-O migliori rispetto agli array per l'inserimento/eliminazione in medio. Le differenze di prestazione tra elenchi e array per le operazioni front-o-of hanno senso intuitivamente, ma per le operazioni nel mezzo, non così tanto.

Vedo perché l'inserto medio è O (n) per un array dinamico - metà degli elementi devono essere spostati uno per uno.

Ma, quando si tratta di elenchi collegati, non metà degli elementi devono essere attraversati uno ad uno a partire dalla testa per trovare il punto di inserimento? E se è così, perché ciò non fa anche elenchi collegati O (n) per l'inserimento medio? E se lo fa, perché non è rappresentato in questo modo nell'articolo di Wikipedia?