cdata-structuresmemory-efficientxor-linkedlistmem.-efficient-linkedlist

What is a Memory-Efficient Doubly Linked List in C?

I had come across the term "Memory-Efficient Doubly Linked List" while reading a book on C Data structures. It just had one line saying that a memory-efficient doubly linked list uses less memory than a normal doubly linked list, but does the same job. Nothing more was explained, and no example was given. Just it was given that this has been taken from a journal, and "Sinha" in Brackets.

After searching on Google, the closest I came to was this. But, I couldn't understand anything.

Can someone explain me what is a Memory-Efficient Doubly Linked List in C? How is it different from a normal Doubly Linked List?

EDIT: Okay, I made a serious mistake. See the link I had posted above, was the second page of the article. I didn't see that there was a first page, and thought the link given was the first page. The first page of the article actually gives an explanation, but I don't think it is perfect. It only talks of the basics concepts of Memory-Efficient Linked List or XOR Linked List.

Solution

  • I know that this is my second answer, but I think the explanation I provide here might be better, than the last answer. But note that even that answer is correct.

    A Memory-Efficient Linked List is more often called a XOR Linked List as this is totally dependent on the XOR Logic Gate and its properties.

    Is it different from a Doubly Linked List?

    Yes, it is. It is actually doing nearly the same job as a Doubly Linked List, but it is different.

    A Doubly-Linked List is storing two pointers, which point at the next and the previous node. Basically, if you want to go back, you go to the address pointed by the back pointer. If you want to go forward, you go to the address pointed by the next pointer. It's like:

    enter image description here

    A Memory-Efficient Linked List, or namely the XOR Linked List is having only one pointer instead of two. This stores the previous address (addr (prev)) XOR (^) the next address (addr (next)). When you want to move to the next node, you do certain calculations, and find the address of the next node. This is the same for going to the previous node.It is like:

    enter image description here

    How does it work?

    The XOR Linked List, as you can make out from its name, is highly dependent on the logic gate XOR (^) and it's properties.

    It's properties are:

    |-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

    Now let's leave this aside, and see what each node stores:

    The first node, or the head, stores 0 ^ addr (next) as there is no previous node or address. It looks like:

    enter image description here

    Then the second node stores addr (prev) ^ addr (next). It looks like:

    enter image description here

    The picture above shows node B, or the second node. A and C are address's of the third and first node. All the node, except the head and the tail, are like the above one.

    The tail of the list, does not have any next node, so it stores addr (prev) ^ 0. It looks like:

    enter image description here

    Before seeing how we move, let's see the representation of a XOR Linked List again:

    enter image description here

    When you see

    enter image description here

    it clearly means there is one link field, using which you move back and front.

    Also, to note that when using a XOR Linked List, you need to have a temporary variable (not in the node), which stores the address of the node you were in before. When you move to the next node, you discard the old value, and store the address of the node you were in earlier.

    Moving from Head to the next node

    Let's say you are now at the first node, or at node A. Now you want to move at node B. This is the formula for doing so:

    Address of Next Node = Address of Previous Node ^ pointer in the current Node

    So this would be:

    addr (next) = addr (prev) ^ (0 ^ addr (next))

    As this is the head, the previous address would simply be 0, so:

    addr (next) = 0 ^ (0 ^ addr (next))

    We can remove the parentheses:

    addr (next) = 0 ^ 0 addr (next)

    Using the none (2) property, we can say that 0 ^ 0 will always be 0:

    addr (next) = 0 ^ addr (next)

    Using the none (1) property, we can simplify it to:

    addr (next) = addr (next)

    You got the address of the next node!

    Moving from a node to the next node

    Now let's say we are in a middle node, which has a previous and next node.

    Let's apply the formula:

    Address of Next Node = Address of Previous Node ^ pointer in the current Node

    Now substitute the values:

    addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

    Remove Parentheses:

    addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

    Using the none (2) property, we can simplify:

    addr (next) = 0 ^ addr (next)

    Using the none (1) property, we can simplify:

    addr (next) = addr (next)

    And you get it!

    Moving from a node to the node you were in earlier

    If you aren't understanding the title, it basically means that if you were at node X, and have now moved to node Y, you want to go back to the node visited earlier, or basically node X.

    This isn't a cumbersome task. Remember that I had mentioned above, that you store the address you were at in a temporary variable. So the address of the node you want to visit, is lying in a variable:

    addr (prev) = temp_addr

    Moving from a node to the previous node

    This isn't the same as mentioned above. I mean to say that, you were at node Z, now you are at node Y, and want to go to node X.

    This is nearly same as moving from a node to the next node. Just that this is it's vice-versa. When you write a program, you will use the same steps as I had mentioned in the moving from one node to the next node, just that you are finding the earlier element in the list than finding the next element.

    I don't think I need to explain this.

    Advantages of XOR Linked List

    Disadvantages of XOR Linked List

    References