2.6 Une implantation tabulaire

Listes chainées contre tables

Tous les langages de programmation offrent des listes sous une forme ou une autre elles sont au coeur de nos algorithmes. Dans certains langages comme Python ou C, les listes sont naturellement implantées sous la forme de table dont la dimension est fixe. Une table est une séquence continue de cases mémoires dans lesquelles nos valeurs numériques ou autres sont rangées. Dans le cas de Python, cette table peut automatiquement s'étendre pour accepter de nouveaux éléments. Mais elle reste fondamentalement une table dans laquelle les éléments sont directement accessibles via leur index.

Lisp traditionnellement manipule des listes chainées. Au lieu d'un accès direct via un index, une liste chainée doit être parcourue élément par élément pour parvenir à la place précise qui nous intéresse.

Insertion

Lorsque l'on oppose les deux représentations, on met souvent en avant la facilité avec laquelle on peut insérer un élément dans une liste chainée, une opération qui consiste à manipuler un ou deux pointeurs en un temps fixe. Dans le cas d'une table, cette opération peut s'avérer très coûteuse, puisqu'il faut d'abord déplacer tous les éléments vers la droite pour libérer une case où ranger cet élément.