Problem in understanding XOR linked list.

Question

I am reading XOR linked list (from Wikipedia).But I am having some problems in understanding it.

I am not getting following paragraph.

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.

I have few questions about it :

1. How does it (the XOR linked list itself) actually work ?

   (It would be great if you justify your answer by giving some example.i.e by taking some addresses and then doing some calculations accordingly.)

2. How can I implement it? A brief idea about implementation.

3. Practically where it is or can be used? Is it really helpful as it seems?

Answer 1

1. The above procedure works by storing the addresses of both the next and previous elements in one field (let's call it A). Therefore, to get the value of the next element in the list you take the address of the other element you have (which is why you need two...call it B). To find the address of the next element, you just A XOR B to get C (the location of the next element).

2. Depends on what language you're using. Study up on bitwise operations in whatever language you're using and you should be able to figure it out pretty quick.

3. It can be used anywhere you use a double-linked list (the XOR linked list will save memory). The caveat being that you have to have two sequential elements of the list to traverse through the elements.

Answer 2

3. This kind of linked list is not very practical nowadays. Its main benefit is to save memory, which is generally cheap and plentiful. The wikipedia article you linked to pretty clearly spells out the disadvantages:

This form of linked list may be inadvisable:

• General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult;
• The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive;
• Most garbage collection schemes do not work with data structures that do not contain literal pointers;
• XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers;
• The pointers will be unreadable if one isn't traversing the list — for example, if the pointer to a list item was contained in another data structure;
• While traversing the list you need to remember the address of the previously accessed node in order to calculate the next node's address.

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).