Chaînage XOR

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

On nomme chaînage XOR 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[modifier | modifier le code]

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.

Usage[modifier | modifier le code]

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.