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:

    “Art is the child of Nature; yes,
    Her darling child, in whom we trace
    The features of the mother’s face,
    Her aspect and her attitude.”
    —Henry Wadsworth Longfellow (1807–1882)

    “Each reader discovers for himself that, with respect to the simpler features of nature, succeeding poets have done little else than copy his similes.”
    —Henry David Thoreau (1817–1862)