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

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.

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

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

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!

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

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.

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

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)

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

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

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.

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.

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.

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.

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