XOR Linked List - Features

Features

  • Given only one list item, one cannot immediately obtain the addresses of the other elements of the list.
  • Two XOR operations suffice to do the traversal from one item to the next, the same instructions sufficing in both cases. Consider a list with items {…B C D…} and with R1 and R2 being registers containing, respectively, the address of the current (say C) list item and a work register containing the XOR of the current address with the previous address (say C⊕D). Cast as System/360 instructions:
X R2,Link R2 <- C⊕D ⊕ B⊕D (i.e. B⊕C, "Link" being the link field in the current record, containing B⊕D) XR R1,R2 R1 <- C ⊕ B⊕C (i.e. B, voilà: the next record)
  • End of list is signified by imagining a list item at address zero placed adjacent to an end point, as in {0 A B C…}. The link field at A would be 0⊕B. An additional instruction is needed in the above sequence after the two XOR operations to detect a zero result in developing the address of the current item,
  • A list end point can be made reflective by making the link pointer be zero. A zero pointer is a mirror. (The XOR of the left and right neighbor addresses, being the same, is zero.)

Read more about this topic:  XOR Linked List

Famous quotes containing the word features:

    “It is a tribute to the peculiar horror of contemporary life that it makes the worst features of earlier times—the stupefaction of the masses, the obsessed and driven lives of the bourgeoisie—seem attractive by comparison.”
    —Christopher Lasch (b. 1932)