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

Question

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.

Answer 1

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:

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:

---

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:

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

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:

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

When you see

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

• This uses less memory than a Doubly Linked List. Approximately 33% less.

• It uses only one pointer. This simplifies the structure of the node.

• As doynax said, a sub-section of a XOR can be reversed in constant time.

---

Disadvantages of XOR Linked List

• This is a bit tricky to implement. It has higher chances of a failure, and debugging it is quite difficult.

• All conversions (in case of an int) have to take place to / from uintptr_t

• You cannot just acquire the address of a node, and start traversing (or whatever) from there. You have to always start from the head or tail.

• You cannot go jumping, or skipping nodes. You have to go one by one.

• Moving requires more operations.

• It is difficult to debug a program which is using a XOR Linked List. It is much easier to debug a Doubly Linked List.

---

References

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/