Mesurer le piège de la file-liste

Dans un graphe en étoile, le sommet central est relié à l'ensemble des $n$ feuilles.

• Avec collections.deque : Enfiler et défiler chaque feuille prend un temps constant $O(1)$. La complexité est bien linéaire en $O(n)$.
• Avec une liste et pop(0) : Dès la première étape, les $n$ voisins entrent dans la liste. Chaque retrait d'un élément en tête force la translation en mémoire des $n$ éléments restants. Le coût total de défilement est en ${\sum }_{i=1}^n(n-i)=O(n^2)$. L'implémentation de la file par liste rend ainsi le parcours quadratique.