Chaînage XOR

Liste chaînée 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 :

class element {
    public:
        int var;

        void régler_p(element * p2, element * p3){ p = p2 ^^ p3; }
        element * obtenir(element p2){ return p ^^ p2; }

    private:
        element * p;
};

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.

class index {
    protected:
        bool direction; // S'il avance direction = true
        element * p, p_prc;

    public:
        index():p(NULL){}

        int lire(){return p->var;}
        void modifier(int n){p->var = n;}

        void initialiser(element * d) {
            // Il s'initialise au début
            p_prc = NULL;
            direction = true;
            p = d;
        }

        void déplacer(bool d) {
            element * c = p;
            if(direction != d) {
                 p = p_prc;
                 p_prc = c;
                 direction = d;
            }
            p = p->obtenir_p(p_prc);
            if(p == NULL) p = c;
            else p_prc = c;
        }
};

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[1]. De plus, elle possède un index:

class chaine_xor {
    protected:
        element * début, fin;
        index i;

    public:
        chaîne_xor() {
            début = NULL;
            fin = NULL;
            i.index();
        }
};

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

void empiler(int var) {
    element * c = new element();
    c->var = var;
    c->régler_p(fin, NULL);
    fin = c;
    if(début == NULL) {
        // Si c'est le premier élément
        début = c;
        i.initialiser(c);
    }
}

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:

void déplacer_index(bool dir){i.déplacer(dir);}

int lire_index(){return i.lire;}

void modifier_index(int n){i.modifier(n);}

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.

Notes et références

1. Note: une chaîne xor peut fonctionner avec seule la classe index, mais il est plus efficace d'utiliser des pointeurs pour faire des insertions.