Pourquoi les listes liées sont-elles considérées comme O (1) pour l'insertion / délétion dans le milieu alors que les tableaux dynamiques sont considérés comme O (n)?

Question

J'ai du mal à comprendre pourquoi les listes liées semblent être acceptées pour avoir de meilleures performances Big-O que les tableaux pour l'insertion / la suppression de Middle. Les différences de performances entre les listes et les tableaux pour les opérations de front et de fin des opérations ont du sens intuitivement, mais pour les opérations au milieu, pas tant.

Je vois pourquoi l'insert moyen est O (n) pour un tableau dynamique - la moitié des éléments doivent être décalés un par un.

Mais, en ce qui concerne les listes liées, la moitié des éléments ne doivent-ils pas être traversés un par un à partir de la tête pour trouver le point d'insertion? Et si oui, pourquoi cela ne fait-il pas également des listes liées O (n) pour l'insertion moyenne? Et si c'est le cas, pourquoi n'est-il pas représenté de cette façon dans l'article de Wikipedia?