XOR Linked List and GC Barrier
Introduction
In this article we are going to quickly review the singly-linked-list, doubly-linked-list, and learn a trick to implement a space efficient doubly-linked-list which looks like a singly-linked-list!
Then, we are going to see that it is not possible to implement the space efficient version of the doubly-linked-list in a programming language like Java or Go that has a Garbage Collector (GC)! It needs to be implemented in a language like C/CPP.
Quick Review of a Singly Linked List
As you can see in this picture, we have some boxes called a Node that stores a value like 3 or whatever; and also stores the memory address of the next Node in the chain. For example, the first node in the picture stores value 3 and also stores the next Node’s memory address which is &2222 (it’s just a dummy address :D). The last node in the chain points nowhere (NULL).
The data structure comes handy when we want to implement a time efficient queue, stack or, …
But one flaw of this data structure is deleting a node in the middle of the chain. For example, in the picture above, if you want to delete the node with value 7, you need to connect it’s previous node to the next node. But the node 7 doesn’t have the previous node’s address! It only has the next node’s address. So, you need to walk through the chain from the beginning (iterate) and find the previous node first. After finding it, you simply connect it to the node after node 7. In this way, the node 7 is disconnected from the chain.
If the language you are coding has a GC, it will free that node’s memory!
So the delete operation has a time complexity of O(n) which is not quite good!
Doubly Linked List to Rescue
In the doubly linked list, each node not only stores the next node’s memory address, it also stores the previous node’s address too.
In this way, if you want to delete a node in between the chain, for example, the node 7 in the picture above, you already have the previous node and the next node’s address. You don’t need to walk through the chain!
This makes the delete operation very fast (O(1)).
But what about the memory?!
A node in the doubly linked list stores both the next and the previous nodes’ addresses so it consumes more memory than the singly linked list (e.g. n*8 bytes). If you are coding for an embedded system with a very limited memory, you may need to save some bytes!
XOR Linked List
This is a memory efficient doubly linked list called XOR-Linked-List. I’m not going to explain it’s details; You can check it out yourself.
In this scheme, each node stores the XOR of the previous and the next node’s memory address.
Let’s check something…
Imagine if the memory address of a node is 1 and another node is 0. The XOR is: 0 XOR 1 = 1
Now if you want to extract the previous node’s memory address, you need to XOR this again with the next node’s memory address: 1 XOR 1 = 0.
You can check other details yourself. The thing that I’m interested right now is the behavior of the GC!
What about GC?
In a language that has a GC like Go, a memory block in which no other part of the memory has a reference to, gets marked and freed. It means, if you define a pointer to a variable, that variable will not get freed by GC. But if you remove that pointer, GC will free that variable’s memory.
Can you see the problem with the XOR Linked List?!
In the XOR Linked List, we do not have pointers to other variables. We just store the XOR of the literate memory addresses! They are just some integers. If there is a GC, it will not be able to understand the logic! It will check the memory and see, oh! there is a variable that no one points to! So I will free it up! In that case, the memory you have stored using XOR, will point to a memory that has been freed!
So, you cannot implement this data structure in a language that has a garbage collector (unless there is some kind of trick!) and you have to use a language like C/CPP.
Conclusion
In this post, we reviewed the linked list data structures and learned a new memory efficient version of the doubly linked list called XOR Linked List. We also saw that the XOR linked list needs to be implemented in a language that supports manual memory management rather than having a GC!
