Comment compter le nombre de nœuds dans une liste chaînée sans la parcourir?

On m’a demandé dans une interview comment compter le nombre de nœuds dans une liste chaînée sans parcourir la liste? Y’a-t-il une quelconque façon de réussir cela?

Le seul moyen auquel je puisse penser est d’append un compteur du nombre de nœuds incrémenté à chaque fois que les méthodes d’ ajout ou d’ insertion sont invoquées et décrémenté lors de l’invocation de la suppression . Vous ne pouvez pas supposer que la mémoire est occupée car, étant une liste chaînée, vous ne pouvez pas garantir que tous les nœuds seront dans le même bloc de mémoire (en effet, cela est hautement improbable).

Si vous faites une allocation dynamic avec quelque chose comme malloc, il n’ya pas d’autre moyen que de mettre à jour un compteur chaque fois que vous insérez / supprimez. Si vous n’effectuez pas l’allocation de manière dynamic, vous n’avez probablement pas implémenté de liste chaînée.

Ce que ces autres gars disent est totalement juste. Comment pouvez-vous savoir combien d’éléments sont dans quelque chose avant de les regarder?

Vous allez avoir besoin de maintenir un compte et de l’incrémenter / le décrémenter lors des insertions / suppressions. C’est le moyen le plus fiable.

Ajoutez un compteur à votre structure et faites la liste liée circulaire au lieu de individuellement. Au lieu de parcourir toute la liste, accédez au nœud prev du nœud initial.