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

Question

Selon l’article article de Wikipedia sur les listes chaînées , inséré au milieu de une liste chaînée est considérée comme O (1). Je penserais que ce serait O (n). Ne devriez-vous pas 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 noeud (bien qu'elle soit requise) et de l'insertion elle-même?

MODIFIER :

  

Les listes chaînées présentent plusieurs avantages par rapport aux tableaux. L'insertion d'un élément en un point spécifique d'une liste est une opération à temps constant, tandis 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 est un peu trompeuse pour moi. Corrigez-moi si je me trompe, mais je pense que la conclusion devrait être:

Tableaux:

• Recherche du point d'insertion / suppression O (1)
• Exécution de l'insertion / suppression O (n)

Listes liées:

• Recherche du point d'insertion / suppression O (n)
• Exécution de l'insertion / suppression O (1)

Je pense que la seule fois où vous n'auriez pas à trouver la position, c'est si vous gardiez une sorte de pointeur sur celle-ci (comme dans le cas de la tête et de la queue dans certains cas). Nous ne pouvons donc pas dire carrément que les listes chaînées battent toujours les tableaux pour les options d’insertion / suppression.

Answer 1

Vous avez raison, l'article considère "Indexation". en tant qu'opération séparée. Donc, l'insertion est elle-même O (1), mais pour arriver à ce nœud central est O (n).

Answer 2

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

Answer 3

Non, lorsque vous décidez d'insérer, il est supposé 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 manière à ne pas être traitées comme une "liste" générique, mais comme une collection de nœuds. Pensez au nœud lui-même en tant qu'itérateur de votre boucle principale. Ainsi, lorsque vous parcourez la liste, vous remarquez, dans le cadre de votre logique métier, qu’un nouveau noeud doit être ajouté (ou un ancien supprimé) et vous le faites. Vous pouvez ajouter 50 nœuds en une seule itération et chacun de ces nœuds correspond à O (1) le temps nécessaire pour dissocier deux nœuds adjacents et insérer votre nouveau nœud.

Éditer: mec, vous tapez un deuxième paragraphe et tout à coup, au lieu d’être le premier intervenant, vous êtes le cinquième à dire la même chose que le premier 4!

Answer 4

Aux fins de comparaison avec un tableau, comme le montre ce graphique, c’est O (1), car 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 le suivant: " noeud donné sur X , quel est le code à insérer après ce noeud?" Vous commencez au point d'insertion.

Answer 5

L'insertion dans une liste chaînée est différente de celle effectuée par itération. Vous ne localisez pas l'élément, vous réinitialisez les pointeurs pour y placer l'élément. Peu importe qu'il soit inséré près de l'extrémité avant ou près de l'extrémité, l'insertion implique toujours que des pointeurs soient réaffectés. Cela dépend évidemment de la manière dont elle a été mise en œuvre, mais c’est la force des listes: vous pouvez les insérer facilement. L'accès via index est l'endroit où un tableau brille. Pour une liste, cependant, ce sera typiquement O (n) de trouver le nième élément. Du moins, c’est ce dont je me souviens à l’école.

Answer 6

Parce que cela n'implique aucune boucle.

L'insertion est comme:

• insérer un élément
• lien vers le précédent
• lien vers le suivant
• terminé

dans tous les cas, le temps est constant.

Par conséquent, insérer n éléments l'un après l'autre correspond à O (n).

Answer 7

  

Cette analyse ne tient-elle pas compte de la recherche de l'opération de noeud (bien qu'elle soit requise) et de l'insertion elle-même?

Vous l'avez. L’insertion à un moment donné suppose que vous tenez déjà un pointeur sur l’élément que vous souhaitez insérer après:

InsertItem(item * newItem, item * afterItem)

Answer 8

L'insertion est O (1) une fois que vous savez où vous allez le mettre.

Answer 9

Non, cela ne prend pas en compte la recherche. Mais si vous avez déjà un pointeur sur un élément au milieu de la liste, insérer à ce moment-là est O (1).

Si vous devez le rechercher, vous devez ajouter le temps de recherche, qui devrait être O (n).

Answer 10

Cet article concerne la comparaison de tableaux avec des listes. Trouver la position d'insertion pour les tableaux et les listes est O (N), l'article l'ignore donc.

Answer 11

O (1) dépend de ce fait que vous avez un élément dans lequel vous allez insérer le nouvel élément. (avant ou après). Si vous ne le faites pas, c’est O (n) parce que vous devez le trouver.

Answer 12

Je pense que c'est juste un cas de ce que vous choisissez de compter pour la notation O (). Dans le cas de l'insertion de l'opération normale à compter, il s'agit d'opérations de copie. Avec un tableau, insérer au milieu implique de copier tout ce qui se trouve au-dessus de l’emplacement dans la mémoire. Avec une liste chaînée, cela devient paramétrer deux pointeurs. Vous devez trouver l'emplacement, peu importe le contenu à insérer.

Answer 13

Si vous avez la référence du nœud à insérer après l'opération, il s'agit de O (1) pour une liste chaînée.
Pour un tableau, il reste toujours O (n) puisque vous devez déplacer tous les noeuds consécutifs.

Answer 14

Les cas les plus fréquents sont probablement l'insertion au début ou à la fin de la liste (et la fin de la liste peut ne pas prendre longtemps pour être trouvée).

Comparez cela avec l'insertion d'éléments au début ou à la fin d'un tableau (ce qui nécessite de redimensionner le tableau s'il est à la fin, ou de redimensionner et de déplacer tous les éléments s'il est au début).