Find error in the C++ code
June 13, 2012Work & Time question
June 13, 2012Memory Efficient doubly linked list
Implement doubly linked list which has only one pointer (may not be directly of apointer data type) per node.
An ordinary doubly linked list will require 2 pointers per node, one pointing to the previous node and another pointing to the next node in the list as shown below.
Doubly linked list looks like below
Where blue arrow is indicating the next pointer and red arrow is indicating the previous pointer.
Note that the Previous pointer of first node and the next pointer of last nodes are NULL.
This implementation of linked list has 2 pointer per node. Your question is,
Implement doubly linked list using only one pointer per node. (Note that you should be able to navigate in both forward and backward direction using the single pointer.)
Solution:
We have only one pointer and that pointer will act as both the forward and the backward pointer. This is where XOR comes into play:
The basic operations on XOR (as also used in this post), has some interesting facts like,
if A ^ B = C Then C ^ A = B and C ^ B = A
i.e If we have C & A, then we can compute B and if we have C & B, then we can compute A.
We will use this property of XOR operator.
For each Node we will not store either the previous or next pointer, but we will store the XOR of previous & next pointer.
So if we have the below linked list
and if a1, a2, a3, a4 are the addresses of each node respectively, then the XOR list will store
If you are traversing in the forward direction then, you will get the address of next node as below:
| Current Node | Next Node | Value of Pointer =(Add of Prev Node) ^ (Link of Current Node) | Address of Next Node |
| list | a1 | Directly | – |
| a1 | a2 | NULL ^ Link of a2 | NULL^NULL^a2 = a2 |
| a2 | a3 | a1 ^ Link of a2 | a1^a1^a3 = a3 |
| a3 | a4 | a2 ^ Link of a3 | a2^a2^a4 = a4 |
| a4 | NULL | a3 ^ Link of a4 | a3^a3^NULL = NULL |
Hence at each point, you have to store the address of previous node to compute the address of next node.
Address of Next Node = Address of Previous Node ^ pointer in the current Node.
Similarly to compute the address of previous node you need to know the address of next node.
Address of Previous Node = Address of Next Node ^ pointer in the current Node
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). In the above implementation, since we are storing XOR of prev & next it will remain unchanged, and only the head pointer need to be changed to point to last node.
Disadvantage:
- Traversing requires more operations. It is not just going to the next pointer but, performing XOR.
References:
http://www.linuxjournal.com/article/6828?page=0,0
The C++ implementation of this is available here…
9 Comments
You claim “a lot of memory savings”, because you only use one pointer instead of two. A typical pointer is 4 bytes on 32 bit and 8 bytes on 64 bit (not talking about function pointers which are a little different). So lets say you have a ridiculously large doubly linked list with 100,000 nodes. You only save only 390 KB on a 32 bit machine and 781 KB on a 64 bit machine. However with a more realistic size of lets say 100 you are only saving 0.39 KB on a 32 bit machine and 0.78 KB on a 64 bit machine.
So even if you are on a embedded system the complexity added by using XOR logic to use only a single pointer is not worth it. Its a great research project or assignment in college but in the real world where you want maintainable code and the KISS principle is king.
You are right in the numbers.. just another way of looking at it can be: If doubly linked list is storing int, then the memory required by the list will be 2/3′rd (two-third) of the one required in the original version.
Saving 33% of memory to me looks like a lot of memory..
Plus for real application, 100000 nodes is not too large a list.. I mean my real life project may be using 1000 lists, and each of the list has 100 elements.. this is a usual expectation.. imagine storing the employee information (ID’s) in a list.. Having 1000 employees is not a big number.. plus another list used for resources in the company (PCs, Monitors, Printers, Laptops, Mobiles etc).. where the list is storing serial numbers of the devices.. this list can easily have 10000 nodes.. and so on.. so the Office Project may be using some thousands of list (some may be persistent also) and each list may be having some 10000s of nodes..
If you have a requirement where you are just dealing with few hundred nodes, then its not really worth it..
Imagine a complex application like that of google or amazon or ebay.. they must be dealing with so many data structures which may get created per user..
If google is able to save even 1byte of memory per user.. then google will save millions of bytes of server memory(because there must be millions of users accessing google at the same time)..
Well, this is impractical. When you’re creating something for amazon or google, and require 100,000 nodes, you won’t use a doubly linked list. At that time, the main problem will be searching, inserting deleting, and the time taken by them. Thus, you will use a hash table, or something like that.
Actually this is a classical time v/s memory question.. because you are saving on memory but loosing on time (traversal will be costly).. so a decision need to be taken.
doubly linked list has a quality that if i provide you with a node address present in that list you can tell the address of the node previous to it and next to it in constant time but i don’t think this can be done using XOR linked list…
Do you agree???
Please explain..
You are right Sahil.. I should have mentioned this in limitations.. thanks for pointing it out.
Thank you for your post; is there any java implementation for this?
Value of Pointer =(Add of Prev Node) ^ (Link of Current Node)
Here we need to know “the Add of Prev Node” as well so we must be storing it somewhere, then how is it helping in less of memory?