Question 1

Quelle est la différence entre une pile et une file ?

Accepted Answer

Une pile est LIFO — le dernier élément empilé est le premier dépilé, comme une pile d'assiettes. Une file est FIFO — le premier élément enfilé est le premier défilé, comme une file d'attente à la caisse. Les piles sont utilisées dans la récursion et les opérations d'annulation ; les files sont utilisées dans l'ordonnancement et le parcours en largeur (BFS) de graphes.

Question 2

Pourquoi les tables de hachage ont-elles une recherche moyenne en O(1) ?

Accepted Answer

Une fonction de hachage convertit la clé en un index entier, pointant directement vers l'emplacement mémoire. Tant que le facteur de charge (éléments ÷ compartiments) reste faible, les collisions sont rares et chaque recherche ne touche qu'un ou deux emplacements mémoire. Dans le pire cas avec de nombreuses collisions, la recherche se dégrade à O(n).

Question 3

Quand choisiriez-vous une liste chaînée plutôt qu'un tableau ?

Accepted Answer

Les listes chaînées excellent lorsque vous avez besoin d'insertions ou de suppressions fréquentes en tête ou au milieu de la liste sans décaler les éléments. Les tableaux offrent un accès aléatoire en O(1) par index, ce que les listes chaînées ne peuvent pas faire. Si vous lisez principalement par position, utilisez un tableau ; si vous insérez/supprimez principalement à des points arbitraires, une liste chaînée est plus efficace.

📦 Structures de données

Qu'avez-vous trouvé ?