Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Generalites sur les listes chainees

Généralités sur les listes chainées Lorsque vous créez un algorithme utilisant des conteneurs il existe di ?érentes manières de les implémenter la façon la plus courante étant les tableaux que vous connaissez tous Lorsque vous créez un tableau les éléments de celui-ci sont placés de façon contigu? en mémoire Pour pouvoir le créer il vous faut conna? tre sa taille Si vous voulez supprimer un élément au milieu du tableau il vous faut recopier les éléments temporairement ré-allouer de la mémoire pour le tableau puis le remplir à partir de l'élément supprimé En bref ce sont beaucoup de manipulations coûteuses en ressources Une liste cha? née est di ?érente dans le sens o? les éléments de votre liste sont répartis dans la mémoire et reliés entre eux par des pointeurs Vous pouvez ajouter et enlever des éléments d'une liste cha? née à n'importe quel endroit à n'importe quel instant sans devoir recréer la liste entière Nous allons essayer de voir ceci plus en détail sur ces schémas Vous avez sur ce schéma la représentation que l'on pourrait faire d'un tableau et d'une liste cha? née Chacune de ces représentations possède ses avantages et inconvénients C'est lors de l'écriture de votre programme que vous devez vous poser la question de savoir laquelle des deux méthodes est la plus intéressante Dans un tableau la taille est connue l'adresse du premier élément aussi Lorsque vous déclarez un tableau la variable contiendra l'adresse du premier élément de votre tableau Comme le stockage est contigu et la taille de chacun des éléments connue il est possible d'atteindre directement la case i d'un tableau Pour déclarer un tableau il faut conna? tre sa taille Pour supprimer ou ajouter un élément à un tableau il faut créer un nouveau tableau et supprimer l'ancien Ce n'est en général pas visible par l'utilisateur mais c'est ce que realloc va souvent faire L'adresse du premier élément d'un tableau peut changer après un realloc ce qui est tout à fait logique puisque realloc n'aura pas forcement la possibilité de trouver en mémoire la place nécessaire et contigu? pour allouer votre nouveau tableau realloc va donc chercher une place su ?sante recopier votre tableau et supprimer l'ancien C Dans une liste cha? née la taille est inconnue au départ la liste peut avoir autant d'éléments que votre mémoire le permet Il est en revanche impossible d'accéder directement à l'élément i de la liste chainée Pour ce faire il vous faudra traverser les i- éléments précédents de la liste Pour déclarer une liste cha? née il su ?t de créer le pointeur qui va pointer sur le premier élément de votre liste cha? née aucune taille n'est donc à spéci ?er Il est possible d'ajouter de supprimer d'intervertir des éléments d'une liste cha? née sans avoir à recréer la liste en entier mais en manipulant simplement leurs pointeurs Chaque élément d'une liste cha? née est composé de deux parties la valeur que vous voulez stocker l'adresse de l'élément suivant s'il existe S'il n'y