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

105

Selon l'article de Wikipédia sur les listes liées , 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 près de la fin de la liste?

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

MODIFIER :

Les listes liées présentent plusieurs avantages par rapport aux tableaux. L'insertion d'un élément à un point spécifique 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, 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:

  • Recherche du point d'insertion / suppression O (1)
  • Effectuer l'insertion / la suppression O (n)

Listes liées:

  • Recherche du point d'insertion / suppression O (n)
  • Effectuer l'insertion / la suppression O (1)

Je pense que la seule fois où vous n'auriez pas à trouver la position, c'est si vous gardez une sorte de pointeur vers elle (comme avec la tête et la queue dans certains cas). Nous ne pouvons donc pas dire catégoriquement que les listes liées battent toujours les tableaux pour les options d'insertion / suppression.

Rob Sobers
la source

Réponses:

113

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

CookieOfFortune
la source
3
Ce qui fait une plus grande différence lors de l'insertion de plus d'un objet à la même position ...
A QUITTER - Anony-Mousse
@ Anony-Mousse pouvez-vous l'expliquer un peu plus? c'est-à-dire que nous devons trouver la position d'insertion une seule fois lors de l'insertion de plusieurs objets?
MyTitle
2
C'est O (n) dans la taille de la liste existante, pas le nombre d'insertions que vous prévoyez d'y faire.
A QUIT - Anony-Mousse
28

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

Evansbee
la source
25

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 manière 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 métier qu'un nouveau nœud 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 est juste O (1) le temps de dissocier deux nœuds adjacents et d'insérer votre nouveau.

Edit: Mec, vous tapez un deuxième paragraphe et tout d'un coup au lieu d'être le premier répondant, vous êtes le 5ème en disant la même chose que les 4 premiers!

Bill K
la source
1
Ha ouais ça craint ... J'ai +1 sur le vôtre parce qu'il vaut la peine de dire que la complexité de l'insertion de listes liées est considérée dans le contexte du fait d'être déjà au pointeur souhaité.
Daniel Macias
6

À des fins de comparaison avec un tableau, ce que montre ce graphique, c'est O (1) car vous n'avez pas à déplacer tous les éléments après le nouveau nœud.

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

Joel Coehoorn
la source
5

L'insertion dans une liste liée est différente de l'itération à travers elle. Vous ne localisez pas l'élément, vous réinitialisez les pointeurs pour y placer l'élément. Peu importe s'il va être inséré près de l'extrémité avant ou près de l'extrémité, 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 les insérer facilement. L'accès via index est l'endroit où un tableau brille. Pour une liste, cependant, ce sera généralement O (n) pour trouver le nième élément. Du moins c'est ce dont je me souviens de l'école.

itsmatt
la source
3

Parce qu'il n'implique aucune boucle.

L'insertion est comme:

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

c'est du temps constant dans tous les cas.

Par conséquent, l'insertion de n éléments les uns après les autres est O (n).

Tomalak
la source
3

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

Tu l'as eu. L'insertion à un point donné suppose que vous maintenez déjà un pointeur vers l'élément que vous souhaitez insérer après:

InsertItem(item * newItem, item * afterItem)
e.James
la source
2

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

Lance Richardson
la source
2

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 devrez ajouter le temps de recherche, qui devrait être O (n).

TED
la source
0

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


la source
1
La recherche du point d'insertion d'un tableau ne serait-elle pas O (1)? Puisque les tableaux sont stockés dans une mémoire contiguë, il suffit d'ajouter le décalage.
Rob Sobers
@ vg1890 - Vous devez d'abord trouver le décalage.
0

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 élément.

Glenn
la source
0

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, l'opération normale pour compter est les opérations de copie. Avec un tableau, l'insertion au milieu consiste à copier tout ce qui se trouve au-dessus de l'emplacement en mémoire. Avec une liste liée, cela devient la définition de deux pointeurs. Vous devez trouver l'emplacement, peu importe ce que vous souhaitez insérer.

workmad3
la source
0

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

Sani Singh Huttunen
la source
0

Les cas les plus courants sont probablement l'insertion au début ou à la fin de la liste (et les fins de la liste peuvent ne pas prendre de temps à trouver).

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).

ChrisW
la source
Il est possible de faire en sorte que l'insertion d'éléments à la fin d'un tableau soit O (1) si vous conservez un tampon d'éléments vides à la fin, bien que les insertions soient parfois toujours O (1). La plupart des collections le font. Il est également possible de rendre les éléments d'inertage au début d'un tableau O (1) en changeant votre opérateur d'index pour renvoyer le numéro d'élément (n + x)% len, où x est le nombre de fois où vous avez inséré des éléments au début de la liste. Deques sont parfois implémentés comme ça (mais sont aussi parfois implémentés avec des listes à double chaînage.
Brian