Cum funcționează mai exact o listă XOR Linked? (Programare, Algoritm)

căutător a intrebat.

Următoarele link explică acest lucru.
Se spune că implementarea funcționează prin stocarea XOR-ului adresei anterioare și următoare (să zicem nxp), în loc să le stocheze pe amândouă (adresa anterioară și următoarea) separat.Cu toate acestea, mai departe se spune că implementarea funcționează prin xor-ing adresa anterioară și nxp, pentru a obține adresa următoare.

Dar, practic, acest lucru nu înseamnă că se utilizează același spațiu ca și cum ar avea indicatoare anterioare și următoare?

Comentarii

  • Comparați implementarea normală de 2 pointeri pe nod și 1 pointer pe nod pentru lista legată XOR și veți vedea diferența. (Rețineți că aceasta este o listă dublu legată) –  > Por nhahtdh.
5 răspunsuri
Patashu

Într-o listă dublu legată, se stochează doi pointeri pe nod: prev și next. Într-o listă legată XOR, stocați un „pointer” per nod, care este XOR-ul dintre prev și next (sau dacă unul dintre ele este absent, doar celălalt (la fel ca XOR-ul cu 0)). Motivul pentru care se poate parcurge o listă legată XOR în ambele direcții se bazează pe proprietățile XOR și pe redundanța informațiilor inerente unei liste legate dublu.


Imaginați-vă că aveți trei noduri în lista legată XOR.

A este capul de listă și are un pointer nebifuit către B (B XOR 0, doar următorul).

B este elementul din mijloc și are XOR-ul indicatorilor către A și C.

C este coada și are un pointer neobscurizat către B (0 XOR B, numai anterior).

Atunci când iterăm peste această listă, încep de la A. Notez poziția lui A în memorie pe măsură ce mă deplasez spre B. Când doresc să mă deplasez spre C, fac XOR între pointerul lui B și A, ceea ce îmi acordă pointerul spre C. Apoi notez poziția lui B în memorie și mă deplasez spre C.

Acest lucru funcționează deoarece XOR are proprietatea de a se anula pe sine dacă este aplicat de două ori: C XOR A XOR A == C. Un alt mod de a gândi este că lista dublu legată nu stochează nicio informație suplimentară pe care o listă legată simplu nu o stochează (deoarece stochează doar toți indicatorii anteriori ca copii ale indicatorilor următori în altă parte în memorie), astfel încât, prin exploatarea acestei redundanțe, putem avea proprietăți de listă dublu legată cu doar atâtea legături câte sunt necesare. Cu toate acestea, acest lucru funcționează numai dacă începem parcurgerea listei noastre legate XOR de la început sau de la sfârșit – deoarece dacă pur și simplu sărim într-un nod aleatoriu din mijloc, nu avem informațiile necesare pentru a începe parcurgerea.


În timp ce o listă legată XOR are avantajul unei utilizări mai mici a memoriei, aceasta are și dezavantaje – va deruta compilatorul, instrumentele de depanare și de analiză statică, deoarece XOR-ul a doi pointeri nu va fi recunoscut corect ca fiind un pointer de nimic altceva decât de codul dumneavoastră. De asemenea, încetinește accesul la pointer pentru că trebuie să se facă mai întâi operația XOR pentru a recupera adevăratul pointer. De asemenea, nu poate fi utilizat în codul gestionat – indicatorii XOR ofuscați nu vor fi recunoscuți de către garbage collector.

Comentarii

  • @nhahtdhh Răspund la întrebarea „Dar acest lucru nu folosește practic același spațiu ca și cum ar avea pointeri precedenți și următori?”, explicând cum o listă legată XOR poate găzdui atât pointeri precedenți, cât și următori în același spațiu în memorie. Ce mi-a scăpat? 🙂 –  > Por Patashu.
  • @nhahtdhh Explic că puteți parcurge o listă legată XOR în ambele direcții, dar cu aceeași cantitate de spațiu de stocare în memorie ca o listă legată simplu, exploatând redundanța informațiilor inerente unei liste dublu legate. Cum de nu răspunde la întrebare? –  > Por Patashu.
  • Cred că vă puteți îmbunătăți răspunsul prin adăugarea punctului an XOR linked list fits both previous and next pointers in the same space in memory. în răspunsul dumneavoastră. În prezent, nu văd relația dintre răspunsul dvs. și întrebare. –  > Por nhahtdh.
  • Cred că nu înțelegi ideea; probabil că OP nu înțelege greșit XOR (sau cel puțin ar putea avea oricum aceeași întrebare). Probabil că lui OP îi scapă faptul că DLL stochează p/n pentru fiecare nod, în timp ce XLL stochează x(p/n) pentru fiecare nod și last_traversed o singură dată, mai degrabă decât pentru fiecare nod. –  > Por Joe.
G. Stoynev

Dar acest lucru nu utilizează practic același spațiu ca și cum ar avea pointeri precedenți și următori?

Nu – utilizează aproximativ jumătate din spațiu, deoarece dimensiunea rezultatului XOR-ing „prev” și „next” este egală cu dimensiunea celui mai mare dintre cei doi.

user2246674

XOR are o proprietate foarte specială în ceea ce-l privește, și anume, având în vedere a XOR b = c, , doar două (oricare două) dintre variabile sunt necesare pentru a o calcula pe cea de-a treia, cu unele restricții. A se vedea Algoritmul de schimb XOR pentru a afla de ce funcționează acest lucru.

În acest caz, pointerul anterior (sau următor) trebuie să fie încă transportat, dar numai prin calculele de traversare și nu ca un membru separat.

Comentarii

  • Ar fi frumos dacă ați cita un fragment relevant din linkul dvs. –  > Por Anish Ramaswamy.
SK17

Să luăm în considerare următoarea listă XOR

A->B->C->D

Să presupunem că ați creat noduri în formatul de mai jos

Cheie|Link|

A|0^addr(B)| ->  B|addr(A)^addr(C)|  ->  C|addr(B)^addr(D)| -> D|addr(C)^0|

CASE #1:[Forward Traversal] Să presupunem că vă aflați în B (current_node=>B) și doriți să vizitați C , deci aveți nevoie de adresa lui C . Cum veți obține?

Addressof(Next_node) = addressof(Prev_node) ^ Current_node(Link)

addr(A)^ ( addr(A)^ addr(C) )
=>(addr(A) ^ addr(A)) ^ addr(C) 
=> 0 ^ addr(C)
=>addr(C)

Cazul nr. 2: [Traversare inversă] Acum, să presupunem că vă aflați în C (current_node=> C) și doriți să vizitați B , deci aveți nevoie de adresa lui B . Cum veți obține?

Addressof(Prev_node) = addressof(Next_node) ^ Current_node(Link)

addr(D) ^ ((addr(B) ^ addr(D)) 
=> (addr(D)^ addr(D)) ^ addr(B)
=> 0^addr(B)
=> addr(B)

Traversare:Pentru a parcurge întreaga listă, aveți nevoie de 3 pointeri. prevPtr , currPtr , nextPtr pentru a stoca adresele relative ale nodului curent, anterior și următor, începând cu head.Apoi, la fiecare iterație, acești pointeri trebuie mutați cu o poziție înainte.

struct Node *currPtr = head;
struct Node *prevPtr = NULL;
struct Node *nextPtr;

printf ("Following are the nodes of Linked List: 
");

while (currPtr != NULL)
{
    // print current node
    printf ("%d ", currPtr->key);

    // Save the address of next node
    nextPtr = XOR (prevPtr, currPtr->link);

    //move prevPtr and currPtr one position for next iteration

    prevPtr = currPtr;
    currPtr = nextPtr;
}

Joe

O listă dublu legată are nevoie de 2*N pointeri stocați pentru N noduri, plus cel puțin un pointer suplimentar (cap, sau poate cap și coadă).

O listă legată XOR are nevoie de N pointeri stocați pentru N noduri, plus cel puțin doi pointeri suplimentari (capul și ultimul nod vizitat, sau poate capul și coada și ultimul nod vizitat). În timpul parcurgerii, se stochează un nod (ultimul nod vizitat), dar atunci când se trece la următorul nod, se rescrie adresa acestuia cu adresa nodului anterior.

Comentarii

  • De fapt, aveți nevoie de N+2 pointeri pentru N noduri. Pentru a traversa în oricare dintre direcții, aveți nevoie de un pointer fără XOR la primul nod și de un altul la ultimul nod. –  > Por Jerry Coffin.
  • Nu sunt de acord (cel puțin în cazul general). Dacă doriți să puteți traversa din ambele direcții în același timp (independent), sigur că aveți nevoie de acest lucru; dar dacă doriți doar posibilitatea de a merge înapoi sau înainte de la nodul curent, aveți nevoie doar de un singur pointer către ultimul nod traversat. Puteți apoi să vă întoarceți la acel pointer sau să mergeți înainte la XOR-ul dintre acel pointer și cel din listă. Nu toate DLL-urile (sau chiar majoritatea) sunt create pentru a permite traversarea de la ambele capete. –  > Por Joe.
  • @JerryCoffin: O listă dublu legată are nevoie și de acestea, așa că ați putea la fel de bine să vă concentrați doar pe indicatoarele din nodurile reale, caz în care este 2*N vs N. –  > Por hammar.
  • Editat pentru a face cele de mai sus puțin mai clare. Presupun că și asta este inexact, deoarece dacă nu trebuie să vă amintiți indicatorul de cap sau de coadă, este tot N+1, dar cred că este mai confuz decât este necesar aici. –  > Por Joe.