Types et structures de données abstraites

6.1 L'algorithme et sa structure vont ensemble

Le programme ouvre sa partie « Structures de données » par une phrase qui vaut programme à elle seule : « on insiste sur le fait que le développement d'un algorithme va de pair avec la conception d'une structure de données taillée à la mesure du problème que l'on cherche à résoudre et des opérations sur les données que l'on est amené à répéter ».

L'idée est simple et elle décide de tout. Chercher un élément coûte $O(n)$ dans un tableau non trié, $O(\log n)$ dans un tableau trié, $O(1)$ en moyenne dans une table de hachage. Ce n'est pas l'algorithme de recherche qui change : c'est la structure. Choisir sa structure, c'est déjà avoir écrit la moitié de son algorithme.

6.2 Les types du langage

6.2.1 Types prédéfinis, types composés, types paramétrés

6.2.2 Mutable ou immuable

let l1 = [1; 2; 3] in
let l2 = 0 :: l1 in ()      (* l1 est INTACTE : l2 partage sa queue, sans copie *)

let t1 = [| 1; 2; 3 |] in
let t2 = t1 in
t2.(0) <- 99                (* t1.(0) vaut 99 AUSSI : c'est le MÊME tableau *)