Pourquoi l'insertion au milieu d'une liste chaînée est-elle O(1) ?

Question

Selon la Article de Wikipédia sur les listes chaînées L'insertion au milieu d'une liste chaînée est considérée comme O(1). Je pense que ce serait O(n). N'auriez-vous pas besoin de localiser le nœud qui pourrait se trouver près de la fin de la liste ?

Cette analyse ne tient-elle pas compte de la recherche de l'opération de nœud (bien qu'elle soit nécessaire) et seulement de l'insertion elle-même ?

EDITAR :

Les listes chaînées présentent plusieurs avantages par rapport aux tableaux. L'insertion d'un élément en un point précis d'une liste est une opération à temps constant, alors que l'insertion dans un tableau peut nécessiter le déplacement de la moitié des éléments, voire davantage.

La déclaration ci-dessus me semble quelque peu trompeuse. Corrigez-moi si je me trompe, mais je pense que la conclusion devrait être :

Les tableaux :

• Trouver le point d'insertion/suppression O(1)
• Réalisation de l'insertion/suppression O(n)

Listes liées :

• Trouver le point d'insertion/suppression O(n)
• Réalisation de l'insertion/suppression O(1)

Je pense que le seul cas où vous n'auriez pas à trouver la position est celui où vous garderiez une sorte de pointeur vers elle (comme avec la tête et la queue dans certains cas). On ne peut donc pas affirmer catégoriquement que les listes chaînées l'emportent toujours sur les tableaux en ce qui concerne les options d'insertion/suppression.

Answer 1

Vous avez raison, l'article considère l'indexation comme une opération distincte. L'insertion est donc elle-même O(1), mais l'accès au nœud central est O(n).

Answer 2

L'insertion elle-même est O(1). La recherche de nœuds est O(n).

Answer 3

Non, lorsque vous décidez d'insérer, on suppose que vous êtes déjà en train de parcourir la liste.

Les opérations sur les listes chaînées sont souvent effectuées de telle sorte qu'elles ne sont pas vraiment traitées comme une "liste" générique, mais comme une collection de nœuds - considérez le nœud lui-même comme l'itérateur de votre boucle principale. Ainsi, lorsque vous parcourez la liste, vous remarquez, dans le cadre de votre logique commerciale, qu'un nouveau nœud doit être ajouté (ou qu'un ancien doit être supprimé) et vous le faites. Vous pouvez ajouter 50 nœuds en une seule itération et chacun de ces nœuds ne représente que O(1) le temps nécessaire pour dissocier deux nœuds adjacents et insérer le nouveau nœud.

Answer 4

Si l'on compare avec un tableau, ce que montre le graphique, c'est O(1) parce qu'il n'est pas nécessaire de déplacer tous les éléments après le nouveau nœud.

Donc oui, ils supposent que vous avez déjà le pointeur sur ce nœud, ou que l'obtention du pointeur est triviale. En d'autres termes, le problème est énoncé : " nœud donné à X Quel est le code à insérer après ce nœud ?" Vous devez commencer au point d'insertion.

Answer 5

L'insertion dans une liste chaînée est différente de l'itération sur cette liste. Il ne s'agit pas de localiser l'élément, mais de réinitialiser les pointeurs pour y placer l'élément. Peu importe que l'élément soit inséré à l'avant ou à l'arrière de la liste, l'insertion implique toujours la réaffectation des pointeurs. Cela dépend de la façon dont cela a été mis en œuvre, bien sûr, mais c'est la force des listes - vous pouvez les insérer facilement. L'accès par index est le point fort d'un tableau. Dans le cas d'une liste, cependant, la recherche du nième élément est généralement O(n). C'est du moins ce dont je me souviens à l'école.