« Les opérations bit à bit/Les subtilités du XOR » : différence entre les versions

 

La propriété <math>a \oplus a = 0</math> est aussi utilisée pour créer des listes doublement chainées plus économes en mémoire que la normale, appelées '''listes chainées XOR'''. Une liste doublement chainée normale stocke deux pointeurs : un vers le nœud suivant, et un vers le nœud précédent. Les XOR linked list permettent de ne pas stocker les deux pointeurs : à la place ils stockent un seul pointeur. Celui-ci contient le XOR entre le pointeur vers le prochain nœud, et le pointeur vers le nœud précédent. Ainsi, on gagne un petit peu de mémoire : au lieu de stocker deux pointeurs, on n'en stocke plus qu'un seul. La consommation mémoire est aussi identique à celle d'une liste simplement chainée.

 

Dans ce qui suit, le pointeur sur le nœud précédent sera noté P (pour Précédent), le pointeur contenu dans le nœud actuellement visité est appelé Ptr et le pointeur vers le nœud suivant sera noté S (pour Suivant). Pour rappel, le pointeur stocké dans le nœud est égal au XOR entre P et S : <math>Ptr = P \oplus S</math>. Traverser cette liste ne se fait que dans un sens : soit on part du début pour arriver à la fin, soit on va dans l'autre sens. Dans ce qui suit, on étudiera un parcours commençant par le début de la liste vers la fin de celle-ci. Obtenir le pointeur vers le prochain élément demande de faire un XOR entre le pointeur vers l’élément précédent avec le pointeur stocké dans le nœud. En effet, <math>P \oplus Ptr = P \oplus (P \oplus S) = S</math>. Ce calcul donne l'adresse du prochain nœud dans la liste. Le même raisonnement peut s'adapter dans le cas où l'on parcours la liste dans l'autre sens., si ce n'est qu'il faut XORer le pointeur de l’élément précédemment visité (qui correspond alors à Next) avec le pointeur stocké dans le nœud.