PYTHON / 06 · EXPLICATION
Listes, chaînage et tableaux
Une liste Python n’est pas une liste chaînée. Dans CPython, elle repose sur un tableau de références aux objets.
FONCTIONNEMENT
L’accès l[-1] ou l[i] est en temps constant O(1). Dans une liste simplement chaînée sans raccourci vers la fin, atteindre le dernier élément nécessite un parcours O(n).
- Liste Python : les cases contiennent des références. Les objets peuvent être de types différents et situés ailleurs en mémoire.
- Liste chaînée : chaque nœud contient une valeur et une référence vers le suivant. C’est une autre structure de données.
- Tableau NumPy numérique : les valeurs de même dtype sont stockées dans un tampon ; les indices et les strides déterminent leur position.
- La différence d’efficacité concerne surtout le stockage et les calculs vectorisés ; elle ne vient pas d’un accès lent au dernier élément d’une liste Python.
Liste Python · accès direct
Un indice permet d’atteindre directement une case contenant une référence.
Liste chaînée · parcours des nœuds
Sans référence directe à la fin, les liens sont suivis successivement.
NumPy numérique · tampon de valeurs
Un tableau contigu stocke les valeurs ensemble ; une vue peut avoir des strides différents.