J'ai essayé de confirmer la durée de fonctionnement de l'insertion pour la liste liée et il semble qu'il y ait deux réponses différentes.
Pour l'insertion d'un élément à la fin d'une liste liée, je penserais que cela prendrait O (n) car il doit traverser la fin de la liste afin d'accéder à la queue. Mais certaines des réponses que j'ai vues dit O (1)? Supposons-ils que toutes les listes liées de la mise en œuvre d'un pointeur sur la queue? Si oui, est-ce une hypothèse acceptable?
Deuxièmement, certains endroits suggèrent également que l'insertion d'un élément au milieu d'une liste liée est O (1) que je suis confondue en raison du même raisonnement de traverser au milieu de la liste pour l'insérer.
Quelqu'un pourrait-il s'il vous plaît clarifier? Merci.
7 Réponses :
L'insertion à une liste liée est O (1) si vous avez un pointeur sur le nœud où vous souhaitez insérer l'élément. Recherche Ce nœud peut être O (n) en fonction de ce que vous voulez faire.
Si vous gardez un pointeur à la queue de la liste, vous n'avez pas besoin de le rechercher, puis d'insertion est O (1).
et non, toutes les implémentations de la liste liée n'ont pas un pointeur à la fin de la liste.
exemple
Supposons que vous ayez une liste vide à laquelle vous ajoutez un seul nœud, x . Ensuite, vous ajoutez n nœuds sur la liste avant et après x . Vous pouvez toujours insérer un seul nœud après x en mettant simplement à jour son Suivant Pointeur (et le nouveau noeud), quel que soit le nombre de nœuds étant la liste.
Modifications à la liste liée implique deux opérations:
Dans la liste liée, la deuxième opération est une opération Lorsque vous admettez au dernier nœud, les implémentations naïves de la liste liée entraîneraient une heure Quant au milieu, votre analyse est correcte dans laquelle la localisation du nœud prendrait également tandis que l'insertion au milieu est généralement considérée comme une opération pour l'insertion
Une implémentation naïve d'une liste liée entraînerait une heure comme pour l'insertion au milieu. Certaines bibliothèques comme celle de Ceci est affecté à une liste de matrices, où l'insertion à la réorganisation des forces du milieu de tous les éléments est supérieure à celle-ci, il doit donc s'agir d'une opération O (1) , il s'agit donc d'un coût du coût des premières opérations.
O (n) heure d'itération. Cependant, de bonnes bibliothèques de liste liées représenteraient les utilisations les plus courantes et l'accès spécial à l'accès au dernier nœud. Cette optimisation entraînerait une récupération O (1) du dernier élément, ce qui entraînait une entrée globale O (1) heure d'insertion à la fin.
O (n) . Cependant, certaines bibliothèques exposent une méthode qui prendrait un pointeur sur l'endroit où le nouveau nœud doit être inséré plutôt que l'index (E.G. C ++ Liste ). Ceci élimine le coût linéaire, entraînant sur tout O (1) .
O (n) , il peut être optimisé pour O (1) dans certains cas. Ceci est l'opposé de la liste des array, où l'opération d'insertion elle-même (la deuxième opération) est O (n) , car tous les éléments des emplacements plus élevés doivent être déplacés. Cette opération ne peut pas être optimisée.
O (n) heure d'insertion. Cependant, de bonnes rédacteurs de bibliothèque de liste liés optimiseraient pour les cas communs. Ils conservent donc une référence aux derniers éléments (ou ayant une implémentation de la liste liée circulaire), ce qui entraînerait un O (1) heure d'insertion .
C ++ ont un emplacement suggéré pour l'insertion. Ils prendraient un pointeur sur le nœud de la liste, où le nouveau est annexé. Ces insertions coûteraient O (1) . Je ne pense pas que vous puissiez atteindre O (1) par numéro d'index.
O (n) .
par le code source LinkedList Java , Java atteint le O (1) pour Je suppose que beaucoup d'autres langues utilisent la même stratégie de base. LinkedList Opérations de la queue en donnant à l'en-tête Entrée d'entrée sur l'élément de la queue via Header.Previous . Donc, si vous voulez le dernier élément, la classe peut toujours retourner en-tête.Previous , permettant une durée constante.
Évidemment, vous avez probablement examiné l'entrée Wikipedia http://fr.wikipedia.org/wiki / Linked_List . Je vois la table où ils spécifient que les deux insertion / la suppression de la fin et au milieu de la liste ont des performances O (1), mais ne parviennent pas à élaborer comment ils ont déterminé cela.
Il y a des réponses intéressantes à une question similaire ici sur Stackoverflow à Pourquoi insère-t-on au milieu d'une liste liée o (1)? . L'affiche originale de cette question a été modifiée son poste et a fait valoir qu'il croit que lorsqu'il est dit que l'insertion / la suppression est O (1), ils parlent de l'opération d'insertion réelle et non de la découverte de l'endroit où insérer. Cela a du sens mais je n'ai pas vu cela formellement déclaré dans aucun des articles que j'ai trouvés à ce stade.
Si vous ne mutez pas les nœuds de votre liste liée (simplement) liée, vous avez besoin de O (n) heure d'insérer à une position arbitraire dans la liste (car vous devez copier tous les nœuds du début de la liste. À la position du nouvel élément. C'est O (1) pour une liste mutable si vous avez déjà un pointeur sur le nœud où vous souhaitez insérer un élément et O (n) si vous devez le chercher. Dans les deux cas, vous n'avez besoin que de O (1) fois pour insérer un élément au début de la liste. Si vous avez souvent besoin d'insérer un élément au milieu de la liste (O (n) cas), vous devez utiliser une autre structure de données.
Je pense qu'une raison de votre confusion est le fait que vous pensez comme s'il y a une liste liée à la liaison idéale / canonique, qui a ou n'a pas de certains pointeurs de tête / queue. La réalité est que toute structure de données linéaire (i.e. sans ramification) qui accède aux éléments en passant par des pointeurs d'éléments précédents est essentiellement une liste liée. Que vous gardiez les pointeurs au premier, dernier, K-th, etc. Elements est entièrement à vous. Donc, si vous avez besoin d'une liste dans laquelle vous avez souvent besoin d'insérer / supprimer des éléments à la 10ème position, vous pouvez simplement implémenter une qui a un pointeur supplémentaire sur le 9ème élément et le faire dans O (1) heure.
Une autre chose est que lors de l'itération sur les éléments d'une liste liée, vous pouvez insérer un nouvel élément juste après l'élément actuel (et juste avant-la seule une liste à double liaison) dans O (1), parce que vous avoir un pointeur à cela.
Comme @kaleb Brase souligne, l'insertion à la queue de Java est O (1) car Java utilise une liste doublement liée comme mise en œuvre linkedlist . Je pense que c'est un choix assez commun pour de nombreuses implémentations de SDK. Par exemple, la liste STL Liste est doublement liée ( Source < / a>).
Si l'insertion au milieu de la liste était O (1), nous n'aurions plus besoin de tableaux :).
LI0LIQ: L'un des avantages des listes liées est que vous pouvez insérer des éléments au milieu en temps constant, où dans les matrices, vous devez déplacer tous les éléments suivants.
@ Li0liq: Qu'en est-il de l'indexation de temps constante?