Chaînage XOR
# Chaînage XOR

Le chaînage XOR est un procédé permettant de parcourir une liste chaînée dans un sens comme dans l'autre en ne gardant dans chaque bloc qu'un seul pointeur au lieu de deux.

La contrepartie est qu'on ne peut cheminer dans la liste qu'en partant de l'une de ses deux extrémités, restriction inexistante dans les listes à double pointeur.

## Principe

Le chaînage XOR consiste à remplacer le pointeur aval d'une liste chaînée par un ou exclusif entre l'adresse du bloc aval et celle du bloc amont.

La caractéristique du XOR bit à bit entre deux adresses est que si C = A xor B, alors B = C xor A et A = C xor B. En conséquence, on trouve le pointeur aval à partir de l'adresse amont (d'où l'on vient) dans un sens, et réciproquement de l'autre.

## Exemple

Voici un exemple d'implémentation complète en C++ en trois classes.

### Classe élément

Une classe élément compte une variable de type entier et un pointeur privé. Elle a comme méthodes régler_p pour régler son pointeur, et obtenir_p pour obtenir le pointeur suivant ou précédent :

### Classe index

Elle possède une méthode principale déplacer qui permet de le faire se déplacer. Pour cela, elle a trois champs: un bool pour savoir dans quelle direction va l'index, un pointeur p et un pointeur p_prc indiquent respectivement sa position actuelle et sa position précédente.

### Classe chaine_xor

Une classe chaîne_xor se charge de coordonner le tout. Elle a deux champs de type element *: début et fin. De plus, elle possède un index:

Une méthode empiler(int var) ajoute un élément à la fin:

Les méthodes déplacer_index(bool dir), lire_index et modifier_index(int n) se chargent de manipuler les données à l'intérieur de la chaîne:

## Usage

La baisse progressive des coûts de la mémoire vive des ordinateurs conduit aujourd'hui (2009) à négliger ce procédé, excepté sur les systèmes embarqués où la contrainte de place mémoire conserve une grande importance.

