XОР повезана листа

XОР повезана листа је структура података која се користи у програмирању. Она користи предност над битовском XОР операцијом да смањи захтеве за складиштење за двоструко повезане листе.

Опис

Обична двоструко повезана листа чува адресе претходних и наредних ставки листе у сваком чвору листе, захтевајући два поља адресе.

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

XОР повезана листа компресује исте информације у једном адресном пољу чувајући битовске XОР (овде ознацен ⊕) адресе за претходну и следећу адресу у једном пољу:

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

Формалније:

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

Када прелазимо листу са лева на десно: претпоставимо да се налазимо на C, можемо узети адресу претходне ставке,Б, и извршимо XОР са вредношћу линк поља(Б⊕Д). Тада ћемо имати адресу за D и можемо наставити да прелазимо листу. Исти образац важи и у другом смеру.

   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)

Да бисмо покренули прелазак кроз листу у било ком смеру из неке тачке, морамо имати адресу две узастопне ставке ,не само једне. Ако су адресе две узастопне ставке обрнуте, треба завршити прелазак листе у супротном смеру.

Теорија операције

Кључ је прва операција, и својства XОР-а:

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

Р2 регистар увек садржи XОР адресе тренутне ставке C са адресом претходника П : Ц⊕П. Линк поља у евиденцији садржи XОР левог и десног следбеника адреса , Л⊕Р. XОР Р2(Ц⊕П) са тренутним пољем (Л⊕Р) даје Ц⊕П⊕Л⊕Р.

• Ако је претходник био L, онда се П(=L) и L поништавају остављајући Ц⊕Р.
• Ако је претходник био Р, онда се П(=Р) и Р поништавају, остављајући Ц⊕Л.

У сваком случају, резултат је XОР тренутне адресе са следећом адресом. XОР са тренутном адресом у Р1 оставља следећу адресу. Р2 је остављен са неопходним XОР паром (сада) тренутне адресе и претходника.

Карактеристике

Две XОР операције довољне су да би се извршио прелаз од једне ставке на другу, исте инструкције су довољне у оба случаја. Размотримо листу ставки {...B C D...} и Р1 и Р2 као регистре који садрже адресу тренутне (C) ставке листе и радног регистра који садрзи XОР тренутне адресе са претходном адресом (Ц⊕Д) :

 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)

• Крај листе је означен замишљајући ставку листе на адреси нула постављену суседно од крајње тачке, као {0 А Б C...}. Поље на А било би 0⊕Б. Додатна инструкција је потребна у горњој секвенци после две XОР операције да детектује нулу у развоју адресе тренутне ставке,
• Крајња тачка листе може бити рефлектујућа тако што ће показивач веза бити нула. Нула показивач је огледало. (XОР леве и десне суседне адресе,који је исти, је нула.)

Недостаци

• Алатке опште намене за дебаговање не могу пратити XОР систем,што отежава отклање грешака;
• Цена смањивања употребе меморије је пораст комплексности кода,чинећи одржавање скупљим;
• XОР показивача није дефинисан у неким контекстима(нпр. C језик),мада многи језици пружају неку врсту конверзије измедју показивача и целих бројева;
• Показивачи ће бити нечитљиви ако неки не прелази листу- на пример,ако је показивач на ставку листе садржан у другој структури података;
• Док се листа прелази,мора се памтити адреса претходно приступљеног чвора у циљу израчунавања следеће адресе чвора.
• XОР повезане листе не пружају неке од битних предности двоструко-повезане листе,као што је могућност брисања чвора из листе знајући само његову адресу, или могућност убацивања новог чвора пре или после већ постојећег чвора знајући једино адресу постојећег чвора.

Варијације

Основни принцип XОР повезане листе може се применити на било које реверзибилне бинарне операције. Замена XОР-а сабирањем или одузимањем даје мало другачије,али у великој мери еквивалентне, формулације:

Сабирање повезане листе

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

Ова врста листе има потпуно исте особине као XОР повезана листа , осим што нулто поље није "огледало". Адреса следећег чвора у листи је дата одузимањем претходне адресе чвора са тренутним пољем чвора.

Одузимање повезане листе

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

Ова врста листе се разликује од "традиционалне" XОР повезане листе у томе што су инструкцијске секвенце које треба да прелазе листу унапред другачије од секвеници које прелазе листу унатраг. Адреса следећег чвора,идући унапред,дата је додавањем поља на претходну адресу чвора;адреса претходног чвора је дата одузимањем поља следеће адресе чвора.

Одузимање повезане листе је такодје посебно у томе што цела листа може бити премештена у меморију без потребе било каквог закрпљавања вредности показивача. Ово је предност у односу над обе XОР повезане листе и традиционалне листе.

Види још

• XОР размена