XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields: ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <– An XOR linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field: ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <-> When you traverse the list from left to right: supposing you are at C, you can take the address of the previous item, B, and XOR it with the value in the link field (B⊕D). You will then have the address for D and you can continue traversing the list. The same pattern applies in the other direction.
To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction.
This form of linked list may be inadvisable:
Computer systems have increasingly cheap and plentiful memory, and storage overhead is not generally an overriding issue outside specialized embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random access).
Why does it work?
The R2 register always contains the XOR of the address of current item C with the address of the predecessor item P: C⊕P. The Link fields in the records contain the XOR of the left and right successor addresses, say L⊕R. XOR of R2 (C⊕P) with the current link field (L⊕R) ields C⊕P⊕L⊕R.
• If the predecessor was L, the P(=L) and L cancel out leaving C⊕R.
• If the predecessor had been R, the P(=R) and R cancel, leaving C⊕L.
In each case, the result is the XOR of the current address with the next address. XOR of this with the current address in R1 leaves the next address. R2 is left with the requisite XOR pair of the (now) current address and the predecessor.
The underlying principle of the XOR linked list can be applied to any reversible binary operation. Replacing XOR by addition or subtraction gives slightly different, but largely equivalent, formulations:
Addition linked list
... A B C D E ... <–> A+C <-> B+D <-> C+E <-> This kind of list has exactly the same properties as the XOR linked list, except that a zero link field is not a "mirror". The address of the next node in the list is given by subtracting the previous node's address from the current node's link field.
Subtraction linked list
... A B C D E ... <–> C-A <-> D-B <-> E-C <-> This kind of list differs from the "traditional" XOR linked list in that the instruction sequences needed to traverse the list forwards is different from the sequence needed to traverse the list in reverse. The address of the next node, going forwards, is given by adding the link field to the previous node's address; the address of the preceding node is given by subtracting the link field from the next node's address. The subtraction linked list is also special in that the entire list can be relocated in memory without needing any patching of pointer values, since adding a constant offset to each address in the list will not require any changes to the values stored in the link fields.(See also Serialization.) This is an advantage over both XOR linked lists and traditional linked lists.
The subtraction linked list also does not require casting C pointers to integers. The subtraction of two C pointers yields an integer. Note that it is still not portable to all platforms since subtraction of pointers is only guaranteed to be valid if the two pointers are elements in the same array or allocated block.
Data Structures Related Interview Questions
|RDBMS Interview Questions||DBMS Interview Questions|
|Adv Java Interview Questions||Core Java Interview Questions|
|C Interview Questions||Database Administration Interview Questions|
|CSS Advanced Interview Questions||Maven Interview Questions|
|Computer architecture Interview Questions||Object Oriented Analysis and Design Interview Questions|
|Standard Template Library (STL) Interview Questions||Xml Publisher Interview Questions|
All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.