Lista concatenata tramite XOR
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.
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |