Lista concatenata tramite XOR
procedimento che permette di percorrere una lista concatenata Da Wikipedia, l'enciclopedia libera
Si chiama lista concatenata tramite XOR un procedimento che permette di percorrere una lista concatenata in un senso come nell'altro utilizzando in ciascun blocco solo un puntatore invece di due.
La contropartita è dovuta al fatto che non si può percorre la lista che partendo da una delle due estremità, restrizione che non esiste nelle liste a doppio puntatore.
Principio
La lista concatenata tramite XOR consiste nel rimpiazzare il puntatore a valle di una lista concatenata con un or esclusivo tra l'indirizzo del blocco a valle e quello del blocco a monte.
La caratteristica dello XOR bit a bit tra due indirizzi sta nel fatto che se C = A xor B, allora B = C xor A e A = C xor B. Di conseguenza si individua il puntatore a valle a partire dall'indirizzo a monte e reciprocamente dell'altro.
Uso
L'abbassamento progressivo dei costi della memoria RAM nei computer ha portato ad oggi (2010) ad evitare questo procedimento, ad eccezione dei sistemi embedded dove la quantità scarsa di memoria è un grosso vincolo.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.