XOR länkad lista

En XOR länkad lista är en typ av datastruktur som används i datorprogrammering . Den drar fördel av den bitvisa XOR -operationen för att minska lagringskraven för dubbelt länkade listor .

Beskrivning

En vanlig dubbellänkad lista lagrar adresser till föregående och nästa listobjekt i varje listnod, vilket kräver två adressfält:

... ABCDE ... –> nästa –> nästa –> nästa –> <– föregående <– föregående <– föregående <–

En XOR-länkad lista komprimerar samma information till ett adressfält genom att lagra den bitvisa XOR (här betecknad med ⊕) för adressen för föregående och adressen för nästa i ett fält:

... ABCDE ... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌

Mer formellt:

länk(B) = addr(A)⊕addr(C), länk(C) = addr(B)⊕addr(D), ...

När du går igenom listan från vänster till höger: om du antar att markören är vid C, kan föregående post, B, XOReras med värdet i länkfältet (B⊕D). Adressen för D kommer då att erhållas och listan kan återupptas. Samma mönster gäller åt andra hållet.

dvs addr(D) = länk(C) ⊕ addr(B) där

länk(C) = addr(B)⊕addr(D)

så

addr(D) = addr(B)⊕addr(D) ⊕ addr(B) addr(D) = addr(B)⊕addr(B) ⊕ addr(D)

eftersom

X⊕X = 0 => addr(D) = 0 ⊕ addr(D)

eftersom

X⊕0 = X => addr(D) = addr(D)

XOR-operationen avbryter addr(B) som förekommer två gånger i ekvationen och allt vi har kvar är addr(D) .

För att börja gå igenom listan i endera riktningen från någon punkt krävs adressen till två på varandra följande poster. Om adresserna för de två på varandra följande posterna är omvända, kommer listövergång att ske i motsatt riktning.

Operationsteori

Nyckeln är den första operationen och egenskaperna för XOR:

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

R2-registret innehåller alltid XOR för adressen för aktuell post C med adressen för föregående post P: C⊕P. Länkfälten i posterna innehåller XOR för vänster och höger efterföljande adresser, säg L⊕R. XOR för R2 (C⊕P) med det aktuella länkfältet (L⊕R) ger C⊕P⊕L⊕R.

• Om föregångaren var L, tar P(=L) och L ut och lämnar C⊕R.
• Om föregångaren hade varit R, avbryts P(=R) och R, vilket lämnar C⊕L.

I varje fall är resultatet XOR för den aktuella adressen med nästa adress. XOR av detta med den aktuella adressen i R1 lämnar nästa adress. R2 lämnas med det erforderliga XOR-paret av den (nu) aktuella adressen och föregångaren.

Funktioner

• Två XOR-operationer räcker för att göra övergången från ett objekt till nästa, samma instruktioner räcker i båda fallen. Betrakta en lista med poster {…BCD…} och där R1 och R2 är register som innehåller respektive adress för den aktuella (säg C) listposten och ett arbetsregister som innehåller XOR för den aktuella adressen med den tidigare adressen (säg C) ⊕D). Cast as System/360 instruktioner:

 X R2,Link R2 <- C⊕D ⊕ B⊕D (dvs B⊕C, "Link" är länkfältet i den aktuella posten, som innehåller B⊕D) XR R1,R2 R1 < - C ⊕ B⊕C (dvs B, voilà: nästa post) 

• Slutet på listan betecknas genom att föreställa sig ett listobjekt på adress noll placerat intill en slutpunkt, som i { 0 ABC...} . Länkfältet vid A skulle vara 0⊕B. En ytterligare instruktion behövs i ovanstående sekvens efter de två XOR-operationerna för att detektera ett nollresultat vid utveckling av adressen för det aktuella objektet,
• En listslutpunkt kan göras reflekterande genom att länkpekaren blir noll. En nollpekare är en spegel . (XOR för den vänstra och högra grannadressen, är densamma, är noll.)

Nackdelar

• Allmänna felsökningsverktyg kan inte följa XOR-kedjan, vilket gör felsökningen svårare;
• Priset för den minskade minnesanvändningen är en ökning av kodkomplexiteten, vilket gör underhållet dyrare;
• De flesta sophämtningsscheman fungerar inte med datastrukturer som inte innehåller bokstavliga pekare ;
• Inte alla språk stöder typkonvertering mellan pekare och heltal, XOR på pekare är inte definierad i vissa sammanhang;
• När du går igenom listan behövs adressen till den tidigare åtkomst noden för att beräkna nästa nods adress och pekarna kommer att vara oläsbara om man inte går igenom listan – till exempel om pekaren till ett listobjekt fanns i en annan datastruktur ;
• XOR länkade listor ger inte några av de viktiga fördelarna med dubbellänkade listor, såsom möjligheten att ta bort en nod från listan genom att bara känna till dess adress eller möjligheten att infoga en ny nod före eller efter en befintlig nod när man bara känner till adressen av den befintliga noden.

Datorsystem har allt billigare och rikligare minne, därför är lagringskostnader i allmänhet inte ett överordnat problem utanför specialiserade inbäddade system . Där det fortfarande är önskvärt att minska omkostnaderna för en länkad lista, avrullning ett mer praktiskt tillvägagångssätt (liksom andra fördelar, som att öka cacheprestanda och snabbare slumpmässig åtkomst ).

Variationer

Den underliggande principen för den länkade XOR-listan kan tillämpas på alla reversibla binära operationer. Att ersätta XOR genom addition eller subtraktion ger något annorlunda, men i stort sett ekvivalenta, formuleringar:

Tillägg länkad lista

... ABCDE ... ⇌ A+C ⇌ B+D ⇌ C+E ⇌

Den här typen av lista har exakt samma egenskaper som den länkade XOR-listan, förutom att ett nolllänksfält inte är en "spegel". Adressen till nästa nod i listan ges genom att subtrahera den föregående nodens adress från den aktuella nodens länkfält.

Subtraktionslänkad lista

... ABCDE ... ⇌ CA ⇌ DB ⇌ EG ⇌

Denna typ av lista skiljer sig från den vanliga "traditionella" XOR-länkade listan genom att de instruktionssekvenser som behövs för att korsa listan framåt skiljer sig från den sekvens som behövs för att korsa listan bakåt. Adressen till nästa nod, framöver, ges genom att lägga till länkfältet till den föregående nodens adress; adressen för den föregående noden ges genom att subtrahera länkfältet från nästa nods adress.

Den subtraktionslänkade listan är också speciell genom att hela listan kan flyttas till minnet utan att behöva lappa pekarvärden, eftersom att lägga till en konstant offset till varje adress i listan inte kommer att kräva några ändringar av värdena som lagras i länkfälten. (Se även serialisering .) Detta är en fördel jämfört med både XOR länkade listor och traditionella länkade listor.

Binärt sökträd

Begreppet XOR länkad list kan generaliseras till XOR binära sökträd .

Se även

• XOR swap-algoritm

externa länkar

• Prokash Sinha (1 december 2004). "En minneseffektiv dubbelt länkad lista" . Linux Journal .
• Implementering av Xor List i C++ i bibliotekslistor.