Liste liée insertion temps d'exécution de la confusion

Modifications à la liste liée implique deux opérations:

1. localiser le nœud à ajouter le nouveau nœud à
2. en fait en y ajoutant le nœud, en changeant le nœud pointeurs

Dans la Liste Liée, la seconde opération est un O(1) opération, c'est donc la question du coût des premières opérations.

Lors de l'ajout au dernier nœud de la naïveté des implémentations de la liste liée entraînerait O(n) itération de temps. Cependant, la bonne liste liée bibliothèques de compte pour la plupart des utilisations courantes, cas particulier de l'accès au dernier nœud. Cette optimisation entraînerait O(1) récupération du dernier élément, entraînant l'ensemble O(1) heure d'insertion à la fin.

Comme pour le milieu, votre analyse est correcte en ce que la localisation du nœud serait également prendre O(n). Cependant, certaines bibliothèques exposer une méthode qui permettrait de prendre un pointeur à l'endroit où le nouveau nœud doit être inséré plutôt que l'indice de référence (par exemple,C++ list). Ceci élimine le linéaire des coûts, résultant en plus de tous les O(1).

Tout d'insertion vers le milieu est généralement considéré comme O(n) opération, il peut être optimisé pour O(1) dans certains cas. C'est l'inverse de la matrice de liste, où l'insertion de l'opération elle-même (la deuxième opération) est O(n), comme tous les éléments dans des emplacements doivent être déplacés. Cette opération ne peut pas être optimisé.

Pour insertation
Une implémentation naïve d'une liste chaînée entraînerait O(n) moment de l'insertion. Cependant, la bonne liste, bibliothèque des écrivains permettrait d'optimiser pour la plupart des cas, afin qu'ils puissent garder une référence à la dernière éléments (ou qui ont une liste chaînée circulaire de mise en œuvre), résultant en une O(1) moment de l'insertion.

Comme pour l'insertion vers le milieu. Certaines bibliothèques, comme celle de C++, a un emplacement suggéré pour l'insertion. Ils prennent un pointeur vers le noeud de liste, où la nouvelle est d'être ajouté. De telles insertions coûterait O(1). Je ne pense pas que vous pouvez obtenir O(1) par numéro d'index.

C'est apposée à un tableau, une liste d'insertion vers le milieu des forces de la réorganisation de tous les éléments de plus qu'elle, donc elle doit être un O(n) opération.

OriginalL'auteur notnoop

Par la Java LinkedList code source, Java permet d'atteindre le O(1) pour LinkedList queue opérations, en donnant la header Entrée un lien vers la queue de l'élément via header.previous. Donc, si vous voulez le dernier élément, la classe peut toujours revenir header.previous, permettant à temps constant.

Je suppose que beaucoup d'autres langues utilisent la même stratégie de base.

OriginalL'auteur Kaleb Brasee

Je pense qu'une des raisons de votre confusion est le fait que vous pensez que si il y a un idéal/canoniques liste liée, ce qui a ou n'a pas certaines de la tête/queue de pointeurs. La réalité est que tout linéaire (pas de branchement) structure de données qui accède à des éléments en passant par des pointeurs à partir des éléments précédents est essentiellement une liste liée. Si vous gardez des pointeurs de la première à la dernière, k-ième etc. éléments est entièrement à vous. Donc, si vous avez besoin d'une liste où vous avez souvent besoin d'insérer/supprimer des éléments à la 10e position, vous pouvez simplement mettre en œuvre celui qui possède un pointeur vers le 9e élément et de le faire en O(1) fois.

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 courant (et juste avant qu'il s'agit d'une double liste chaînée) en O(1), parce que vous avez déjà un pointeur.

OriginalL'auteur MAK