Structures de données dynamiques : vecteurs et listes liées

Cette séance de cours traite des différences entre les vecteurs et les listes liées en C++. Il commence par mettre en évidence les avantages des vecteurs, tels que l'accès en temps constant aux éléments en raison de leur allocation de mémoire contiguë. Cependant, il aborde également les limitations des vecteurs, en particulier lorsqu'il s'agit de maintenir l'ordre lors des insertions et des suppressions. L'instructeur présente les listes liées comme une alternative, expliquant leur structure et comment elles permettent une allocation de mémoire plus flexible. La séance de cours couvre la mise en œuvre de listes liées séparément, y compris l'utilisation de pointeurs pour gérer les éléments. Il détaille les coûts de calcul associés à l'accès, à l'ajout et à la suppression d'éléments dans les listes liées par rapport aux vecteurs. L'instructeur souligne que, bien que les listes liées aient des temps d'accès linéaires, elles offrent une complexité temporelle constante pour les insertions et les suppressions, en particulier lors du maintien de l'ordre. La séance de cours se termine en explorant des structures de données plus complexes, telles que les arbres binaires, qui peuvent être construites à l'aide de listes liées, améliorant ainsi la flexibilité et l'efficacité de la gestion des données dans la programmation.