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

Question

Selon le Wikipedia article on linked lists, l'insertion au milieu d'une liste lié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 être proche de la fin de la liste?

Est-ce que cette analyse ne tient pas compte de la découverte de l'opération du nœud (bien que cela soit obligatoire) et de l'insertion elle-même?

EDIT:

listes chaînées ont plusieurs avantages sur les tableaux. L'insertion d'un élément à 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, ou plus.

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:

• Trouver le point d'insertion/suppression O (1)
• Effectuer l'insertion/suppression O (n)

listes chaînées:

• Trouver le point d'insertion/suppression O (n)
• Effectuer l'insertion/suppression O (1)

Je pense que la seule fois que vous ne devez trouver la position est si vous avez gardé quelques-uns sorte de pointeur vers lui (comme avec la tête et la queue dans certains cas). Nous ne pouvons donc pas affirmer catégoriquement que les listes liées battent toujours les tableaux pour les options d'insertion/suppression.

Answer 1

Vous avez raison, l'article considère l'indexation comme une opération distincte. Donc, l'insertion est elle-même O (1), mais O (n) arrive à ce nœud intermédiaire.

Answer 2

Parce qu'il n'implique aucune boucle.

Insertion est comme:

• élément d'insertion
lien
• au précédent
• lien suivant
• fait

cette constante de temps est dans tous les cas.

Par conséquent, l'insertion de n éléments l'un après l'autre est O (n).

Answer 3

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

Answer 4

Non, lorsque vous décidez que vous souhaitez insérer, il est supposé que vous êtes déjà en train d'itérer dans la liste.Les opérations sur les listes lié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 - pensez au nœud lui-même comme itérateur pour 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. Edit: Man, vous tapez un deuxième paragraphe et tout d'un coup au lieu d'être le premier répondeur, vous êtes le 5ème dire la même chose que le premier 4!

Answer 5

Est-ce que cette analyse ne tient pas compte de la découverte de l'opération du nœud (bien que cela soit obligatoire) et de l'insertion elle-même?

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

InsertItem(item * newItem, item * afterItem) 

Answer 6

L'insertion lui-même est O (1). La découverte du nœud est O (n).

Answer 7

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

Answer 8

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 trouver cet article.

Answer 9

Non, cela ne tient pas compte de la recherche. Mais si vous avez déjà un pointeur sur un élément au milieu de la liste, l'insertion à ce point est O (1).

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

Answer 10

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 est des opérations de copie. Avec un tableau, l'insertion au milieu implique de tout copier au-dessus de l'emplacement en mémoire. Avec une liste liée, cela devient la configuration de deux pointeurs. Vous devez trouver l'emplacement, peu importe ce qu'il faut insérer.

Answer 11

A des fins de comparaison avec un tableau, ce que montre ce graphique, c'est O (1) car vous n'avez pas besoin 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 indiqué: "noeud donné à X, quel est le code à insérer après ce noeud?" Vous commencez au point d'insertion.

Answer 12

Si vous avez la référence du noeud à insérer après l'opération est O (1) pour une liste chaînée.
Pour un tableau, c'est toujours O (n) car vous devez déplacer tous les nœuds consécutifs.

Answer 13

Les cas les plus courants sont probablement l'insertion au début ou à la fin de la liste (et les extrémités de la liste peuvent prendre pas de temps à trouver). Contraste 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).

Answer 14

L'insertion dans une liste liée est différente de l'itérer dans cette liste.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 la fin, l'insertion implique toujours la réaffectation des pointeurs. Cela dépendra de la façon dont il a été mis en œuvre, bien sûr, mais c'est la force des listes - vous pouvez insérer facilement. L'accès via index est l'endroit où un tableau brille. Pour une liste, cependant, ce sera typiquement O (n) pour trouver le nième élément. Au moins c'est ce dont je me souviens de l'école.