Mettre en œuvre la file d'attente avec une liste liée; pourquoi serait-il mauvais d'insérer à la tête et retirer à la queue?

Question

Dans mon manuel, les structures de données et algorithmes en Java, l'auteur dit lors de la mise en œuvre d'une file d'attente à l'aide d'une liste chaînée vous choisissez l'avant de la file d'attente pour être à la tête de la liste, et l'arrière de la file d'attente d'être à la queue de la liste. De cette façon, vous retirez de la tête et insertion à la queue.

L'auteur demande alors énigmatiquement: « Pourquoi serait-il mauvais d'insérer à la tête et enlever à la queue? » sans fournir une réponse.

Je ne peux pas voir ce que la différence est vraiment. En effet, « Tête » et « queue » ne sont que des noms arbitraires que nous définissons. Quelle serait si mauvais si à enqueue () on ajoute une tête et créer une référence à l'ancien chef, et dequeue (), nous prenons de la queue et passer la queue sur?

Quelle est la réponse à la question de l'auteur?

Answer 1

Dans une seule liste chaînée, chaque élément a un pointeur sur l'élément suivant. Si vous avez un pointeur supplémentaire à l'élément de queue, il vous prend un fonctionnement de nombre constant à ajouter à la liste à la queue: obtenir le pointeur de la queue, ajouter un élément après la queue, mettre cette nouvelle Elément nouvelle queue. Retrait de la tête prend également un nombre constant d'opérations:. Vous faire nouvel élément nouveau, la tête, pointez sur vieille tête

Cependant, suppression de la queue exige un pointeur vers le prédécesseur à la queue en cours. Cela vous prend autant d'opérations que il y a des éléments, à savoir de façon linéaire beaucoup.

Une autre solution consiste à utiliser une liste doublement chaînée, alors vous pouvez choisir ce que vous voulez, mais il utilise deux fois plus de mémoire.

Answer 2

Retrait de la tête et en insérant la queue sont à la fois des opérations de temps constants par une liste chaînée, en supposant que les pointeurs de tête et la queue. Insertion de la queue est aussi constante de temps. Mais la suppression des moyens de queue en déplaçant le pointeur de la queue vers la tête, et puisque vous ne disposez pas d'un pointeur arrière, vous ne pouvez pas le faire sans traverser toute la liste pour trouver l'élément précédent à la queue. Cela rend l'insertion d'un temps linéaire au lieu d'une opération à temps constant et c'est pourquoi il est pire.