La difference de base entre un tableau et une liste chainee, c'est que le tableau est une zone contigue de la memoire alloue une seule fois, a la creation du tableau, alors que dans une liste chainee on alloue la memoire quand on en a besoin.
Par consequent, si on veut l'element no 100 d'un tableau, on a juste a incrementer la valeur du pointeur de 100. On sait ou va se trouver l'element dans la memoire. A l'inverse, une liste chainee c'est un ensemble de paire (donnees, pointeur suivant). Donc on est oblige de suivre la liste du debut jusqu'a l'element voulu pour arriver jusqu'a l'element qu'on cherche.
Le probleme des tableaux, c'est que la taille est fixe. Forcement, vu que c'est une zone memoire contigue, si on ecrit des choses derriere on ne peut pas agrandir le tableau.
La solution hybride c'est les tables de hachage. Un gros, c'est un tableau de listes chainees.
Exemple: on veut classer des mots. On fait un tableau de 26 cases avec les lettres de l'alphabet (a, b, c, d, e...). A chaque lettre est associee une liste chainee. Et si on veut classer le mot "troll" (ou le rechercher), on va directement au "t" puis on parcours la liste chainee pour trouver le mot (ou l'inserer par ordre alphabetique).
Bien sur, une telle table de hachage n'est pas tres bonne parce qu'on va avoir beaucoup de collisions (cad: d'elements inseres dans la meme liste chainee). Dans l'ideal on ne doit avoir que quelques elements par liste, pour que l'acces soit plus rapide.
[^] # Re: autre optimisation
Posté par Erwan . En réponse au journal Vous trouvez GNOME lent ?. Évalué à 6.
Par consequent, si on veut l'element no 100 d'un tableau, on a juste a incrementer la valeur du pointeur de 100. On sait ou va se trouver l'element dans la memoire. A l'inverse, une liste chainee c'est un ensemble de paire (donnees, pointeur suivant). Donc on est oblige de suivre la liste du debut jusqu'a l'element voulu pour arriver jusqu'a l'element qu'on cherche.
Le probleme des tableaux, c'est que la taille est fixe. Forcement, vu que c'est une zone memoire contigue, si on ecrit des choses derriere on ne peut pas agrandir le tableau.
La solution hybride c'est les tables de hachage. Un gros, c'est un tableau de listes chainees.
Exemple: on veut classer des mots. On fait un tableau de 26 cases avec les lettres de l'alphabet (a, b, c, d, e...). A chaque lettre est associee une liste chainee. Et si on veut classer le mot "troll" (ou le rechercher), on va directement au "t" puis on parcours la liste chainee pour trouver le mot (ou l'inserer par ordre alphabetique).
Bien sur, une telle table de hachage n'est pas tres bonne parce qu'on va avoir beaucoup de collisions (cad: d'elements inseres dans la meme liste chainee). Dans l'ideal on ne doit avoir que quelques elements par liste, pour que l'acces soit plus rapide.