La complexité de l'algorithme de l'insertion d'un élément dans une liste liée circulaire à l'extrémité avant

Question

Dans une liste chaînée circulaire, si un des éléments doit être inséré à l'avant [juste avant le noeud fait par la tête], peut être fait en O (1) (voir la réponse )

Mais dans un livre actuellement, je l'ai, il est mentionné qu'il est fait en O (n) (la méthode habituelle). J'ai vu aussi quelques ppts de cours, ils mentionnent tous la méthode habituelle de parcourir la liste et l'ajout d'un élément.

Ma question est:

1. Dans les scénarios pratiques méthode utilisée?

2. Je suis sur le point d'assister à un examen, qui se compose de QCM, si la question ci-dessus est demandé doit je marque O (n), puisque c'est la réponse standard?

Answer 1

La méthode utilisée dans des scénarios pratiques dépend du scénario (et le programmeur). Il y a plusieurs problèmes possibles qui influent sur le choix de la mise en œuvre:

1. Que l'algorithme est connu pour le programmeur.
2. Facilité de codage (il est plus facile si elle est déjà mis en œuvre dans une bibliothèque, vous pouvez utiliser).
3. Vitesse -. Qui dépend de la façon dont la structure de données est utilisé
4. Espace frais généraux pris par la structure de données.

Un programmeur intelligente devrait prendre tous ces éléments en compte, et essayer de se faire mieux connaître des divers algorithmes et structures de données.