Insights On Memory Efficient Linked List.
In today's world, it is very much necessary to make the proper utilization of the resources to spend less and gain more out of anything. Hence being a software engineer, he should know how to process and manage the data more efficiently and consuming very less memory space. In this article, we will see how could one avoid using two pointers in a doubly-linked list and save a lot of memory.
Doubly Linked List
Unlike a singly linked list, doubly linked lists have pointers pointing to both the node next to it and the node before it. This help us in traversing back and forth whenever there is a need to do so. We need not traverse the linked list from the beginning if there was a need for accessing a node before the node where we are currently pointing to.
The structure of a node of a doubly linked:
struct Node{
int data; //Data stored in the node.
Node* next_node; //Pointer pointing to the next node.
Node* prev_node; //Pointer pointing to the previous node.
};Memory utilization
Let us talk about the memory utilization of the doubly-linked list. Consider we have a doubly-linked list with 10 nodes where each node stores an integer value. Each node of the list contains an integer and two pointers. We know that an integer occupies 4 bytes in the memory. Each pointer occupies 4 bytes if your machine is using a 32-bit processor to store a 32-bit long address and occupies 8 bytes in case you are having a machine using a 64-bit processor. Let us assume your processor to be 64 bit. Hence two pointers occupy 16 bytes in the memory. Summing up totals to the memory occupied by a node which is 16 + 4 = 20 bytes. Ten nodes occupy 20*10 = 200 bytes of memory. Could we reduce this? Yes, let us see how we could reduce this in the next section of the article.
Memory Efficient Linked List
As the name suggests this linked list functions just like a doubly-linked list but will occupy less memory when compared to the same during runtime. A node in this linked list will have data and a pointer. Unlike the pointers in the nodes of the singly or doubly linked list, the pointer in the node of the memory-efficient linked list would not store the address of any nodes but will store the bitwise XOR of the addresses of the node next to it and the node previous to it. Thus instead of using two pointers, we get the job done with just one pointer.
struct Node{
int data; //Data stored in the node.
Node *address_difference;
};
/*address_difference = next_node_addr ^ prev_node_addr */In the next two sections, we will look at why to avoid doubly-linked list and how do we traverse the Memory Efficient Linked List.
Avoid Doubly-Linked List
Let us assume that the doubly linked list used previously is now implemented as a memory-efficient linked list. The list was of size 10 and each node had a data of type int. The difference from the old implementation and the new one is that in the new implementation each node is having only one pointer which was two in the old case. Hence each node occupies only 4 + 8 = 12 bytes of space in the memory. The memory occupied by the list totals to 12 * 10 = 120 bytes of memory. We see a huge difference between the previous value and the value calculated now. That is memory-efficient linked list is occupying 80 bytes lesser than the doubly linked list.
This may seem very less but what if the list had 1000 nodes? The difference, in this case, would calculate to 8000 bytes. For the list having 1000000 nodes, the difference would be 8000000 bytes which are almost equal to 8MB!! Can you imagine? You have saved 8MB of your RAM from being used unnecessarily. This is why the memory-efficient linked list is preferred over the doubly-linked list.
Traversing Memory-Efficient Linked List
Traversing forward and backward of the linked list could be done using the properties of XOR.
Properties of XOR
Let a and b be the addresses of the previous and next node respectively.
1) (a ^ b) ^ b = a
2) (a ^ b) ^ a = bAssume the linked list, head -> A -> B -> C -> D -> E -> null.
Consider we are at node C and want to get to node D. Pointer in node C has the value (addr_B ^ addr_D). Using this how do we get the address of node D? It’s actually simple. Looking at the property one in the box above we see that expression (addr_B ^ addr_D) ^ addr_B would give us the address of the node D. Hence while traversing in the forward direction its necessary that we use an extra pointer to remember the address of the previous node which would help us in calculating the address of the next node.
Similarly to traverse the list in the backward direction we must have the address of the next node to calculate the address of the previous node. Using the property two from the above box that is (addr_B ^ addr_D) ^ addr_D would give us the address of the node B.
I will provide the code snippet on how to traverse the linked list and insert a new node at the end of the list below. If you want a detailed implementation of then please check the link provided below. This would take you to my GitHub repository where I have written down the code for constructing a Memory-Efficient Linked List and printing all the contents in the list.
struct Node{
int x;
Node *diff;
};Node* CreateNode(Node *start){
Node *temp = new Node;
std::cout<<"Enter the element: ";
std::cin>>temp->x;
if(start == 0){
start = temp;
temp->diff = 0;
}
else{
Node *temp2 = start;
Node *prev = 0, *store;
while((Node*)((uintptr_t)(temp2->diff)^(uintptr_t)(prev)) != 0){
store = temp2;
temp2 = (Node*)((uintptr_t)(temp2->diff)^(uintptr_t)(prev));
prev = store;
}
temp2->diff = (Node*)((uintptr_t)(temp)^(uintptr_t)(prev));
temp->diff = temp2;
}
return start;
}int main(){
Node *start = 0;
int size;
std::cout<<"Enter the size of the list: ";
std::cin>>size;
for(int i=0; i<size; i++)
start = CreateNode(start);
return 0;
}
GitHub Link to my Code:
https://github.com/RosNayak/C-/blob/master/MemoryEfficientList.cpp
Hope this post will help. Thank you.
