XOR linked list

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[modifica | modifica wikitesto]

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 trova il puntatore a valle a partire dall'indirizzo a monte e reciprocamente dell'altro.

Uso[modifica | modifica wikitesto]

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.

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica