XOR povezana lista

XOR povezana lista je struktura podataka koja se koristi u programiranju. Ona koristi prednost nad bitovskom XOR operacijom da smanji zahteve za skladištenje za dvostruko povezane liste.

Opis

Obična dvostruko povezana lista čuva adrese prethodnih i narednih stavki liste u svakom čvoru liste, zahtevajući dva polja adrese.

...  A       B         C         D         E  ...
         –>  next –>  next  –>  next  –>
         <–  prev <–  prev  <–  prev  <–

XOR povezana lista kompresuje iste informacije u jednom adresnom polju čuvajući bitovske XOR (ovde oznacen ⊕) adrese za prethodnu i sledeću adresu u jednom polju:

...  A        B         C         D         E  ...
        <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

Formalnije:

link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

Kada prelazimo listu sa leva na desno: pretpostavimo da se nalazimo na C, možemo uzeti adresu prethodne stavke,B, i izvršimo XOR sa vrednošću link polja(B⊕D). Tada ćemo imati adresu za D i možemo nastaviti da prelazimo listu. Isti obrazac važi i u drugom smeru.

   tj.   addr(D) = link(C) ⊕ addr(B)
   gde
         link(C) = addr(B)⊕addr(D)
   onda  
         addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
     
         addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
   otada 
          X⊕X = 0                 
          => addr(D) = 0 ⊕ addr(D)
   otada
          X⊕0 = x
          => addr(D) = addr(D)

Da bismo pokrenuli prelazak kroz listu u bilo kom smeru iz neke tačke, moramo imati adresu dve uzastopne stavke ,ne samo jedne. Ako su adrese dve uzastopne stavke obrnute, treba završiti prelazak liste u suprotnom smeru.

Teorija operacije

Ključ je prva operacija, i svojstva XOR-a:

• X⊕X=0
• X⊕0=X
• X⊕Y=Y⊕X
• (X⊕Y)⊕Z=X⊕(Y⊕Z)

R2 registar uvek sadrži XOR adrese trenutne stavke C sa adresom prethodnika P : C⊕P. Link polja u evidenciji sadrži XOR levog i desnog sledbenika adresa , L⊕R. XOR R2(C⊕P) sa trenutnim poljem (L⊕R) daje C⊕P⊕L⊕R.

• Ako je prethodnik bio L, onda se P(=L) i L poništavaju ostavljajući C⊕R.
• Ako je prethodnik bio R, onda se P(=R) i R poništavaju, ostavljajući C⊕L.

U svakom slučaju, rezultat je XOR trenutne adrese sa sledećom adresom. XOR sa trenutnom adresom u R1 ostavlja sledeću adresu. R2 je ostavljen sa neophodnim XOR parom (sada) trenutne adrese i prethodnika.

Karakteristike

Dve XOR operacije dovoljne su da bi se izvršio prelaz od jedne stavke na drugu, iste instrukcije su dovoljne u oba slučaja. Razmotrimo listu stavki {...B C D...} i R1 i R2 kao registre koji sadrže adresu trenutne (C) stavke liste i radnog registra koji sadrzi XOR trenutne adrese sa prethodnom adresom (C⊕D) :

 X  R2,Link    R2 <- C⊕D ⊕ B⊕D (tj. B⊕C, "Link" kao polje 
                                u trenutnom registru, koji sadrži B⊕D)
 XR R1,R2      R1 <- C ⊕ B⊕C    (tj. B,sledeci registar)

• Kraj liste je označen zamišljajući stavku liste na adresi nula postavljenu susedno od krajnje tačke, kao {0 A B C...}. Polje na A bilo bi 0⊕B. Dodatna instrukcija je potrebna u gornjoj sekvenci posle dve XOR operacije da detektuje nulu u razvoju adrese trenutne stavke,
• Krajnja tačka liste može biti reflektujuća tako što će pokazivač veza biti nula. Nula pokazivač je ogledalo. (XOR leve i desne susedne adrese,koji je isti, je nula.)

Nedostaci

• Alatke opšte namene za debagovanje ne mogu pratiti XOR sistem,što otežava otklanje grešaka;
• Cena smanjivanja upotrebe memorije je porast kompleksnosti koda,čineći održavanje skupljim;
• XOR pokazivača nije definisan u nekim kontekstima(npr. C jezik),mada mnogi jezici pružaju neku vrstu konverzije izmedju pokazivača i celih brojeva;
• Pokazivači će biti nečitljivi ako neki ne prelazi listu- na primer,ako je pokazivač na stavku liste sadržan u drugoj strukturi podataka;
• Dok se lista prelazi,mora se pamtiti adresa prethodno pristupljenog čvora u cilju izračunavanja sledeće adrese čvora.
• XOR povezane liste ne pružaju neke od bitnih prednosti dvostruko-povezane liste,kao što je mogućnost brisanja čvora iz liste znajući samo njegovu adresu, ili mogućnost ubacivanja novog čvora pre ili posle već postojećeg čvora znajući jedino adresu postojećeg čvora.

Varijacije

Osnovni princip XOR povezane liste može se primeniti na bilo koje reverzibilne binarne operacije. Zamena XOR-a sabiranjem ili oduzimanjem daje malo drugačije,ali u velikoj meri ekvivalentne, formulacije:

Sabiranje povezane liste

...  A        B         C         D         E  ...
        <–>  A+C  <->  B+D  <->  C+E  <->

Ova vrsta liste ima potpuno iste osobine kao XOR povezana lista , osim što nulto polje nije "ogledalo". Adresa sledećeg čvora u listi je data oduzimanjem prethodne adrese čvora sa trenutnim poljem čvora.

Oduzimanje povezane liste

...  A        B         C         D         E  ...
        <–>  C-A  <->  D-B  <->  E-C  <->

Ova vrsta liste se razlikuje od "tradicionalne" XOR povezane liste u tome što su instrukcijske sekvence koje treba da prelaze listu unapred drugačije od sekvenici koje prelaze listu unatrag. Adresa sledećeg čvora,idući unapred,data je dodavanjem polja na prethodnu adresu čvora;adresa prethodnog čvora je data oduzimanjem polja sledeće adrese čvora.

Oduzimanje povezane liste je takodje posebno u tome što cela lista može biti premeštena u memoriju bez potrebe bilo kakvog zakrpljavanja vrednosti pokazivača. Ovo je prednost u odnosu nad obe XOR povezane liste i tradicionalne liste.

Vidi još

• XOR razmena