Menu
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.
706
What is a memory efficient double linked list? Explanation: Memory efficient doubly linked list has only one pointer to traverse the list back and forth. The implementation is based on pointer difference. It uses bitwise XOR operator to store the front and rear pointer addresses.
Advantage: We save a lot of memory space. For each node we are saving one pointer, if there are n nodes then our memory consumption is reduced by O(n). If we want to reverse the doubly linked list (pre will become next & vice-versa) it is O(n) operation (pointers need to be changed for each node).
Advertisements. Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List.
Doubly Linked list is more effective than the Singly linked list when the location of the element to be deleted is given. Because it is required to operate on "4" pointers only & "2" when the element to be deleted is at the first node or at the last node.
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.
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:
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.
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.
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.
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/
185
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With