Double Linked List with a Single Link Field
In this article, I will show you how to make a linked list using a simple mathematical hack. This will produce a more memory-efficient linked list where there is only one field in memory to store the actual link to two places.
Table of Contents
Introduction
Before I talk about improvements I have to mention what a double-linked list is. Let’s start with a linked list. If you never had any formal introductions to programming collections, well now is the time.
Usually in most languages when you have a collection you’re having what is called an array. An array is consecutive memory or otherwise said each element is right next to the other. This is usually convenient since you’re having only one pointer to the beginning of this collection and one number to know the size. Then you can access any element just by incrementing the beginning. There is a little problem though. If you want more elements than the size you would have to reallocate and move all elements to a new place that can contain the whole collection. This is a costly operation since it involves a lot of copying. It is also non-thread friendly since you have to implement locks and synchronizations for an extended period. It is also not safe to keep references to the elements inside the collection as the memory might move when resized.
So this is why there is this other popular collection called a linked list. A linked list is slow to go over because its idea is that each element points to the next element in the list. If you want to get the 3rd element you start from the first one and then go over the pointers of each node to get to the 3rd. Well, this is slow to go over but also has some benefits. You don’t need to reallocate previous elements when you add new ones and you can safely keep references to nodes expecting that they won’t randomly disappear. Operations for sorting can also be quite fast since you don’t need to move elements but just assign pointers.
There is also an alternative to the linked list called a double-linked list where you keep reference to the next and previous elements. This is essentially used to help with some algorithms where you can do processing with surrounding elements or help with processing both from the front and back of the list.
So in this article, we’re going to target just that list implementation. You would usually do two pointers on a node where you point to the previous and next nodes and you would also keep the data inside the node. But there is a way with some constraints that you can keep the next and previous pointers into a single value.
The XOR operation
What is the XOR? The XOR operation is also known as exclusive or. It is a bit operation which means that each bit of a number is calculated with each bit in the same position as another number. The exclusive OR operation compares two bits and returns a value based on whether they match or are different. If they are different it will return a 1 and if they match it will return a 0. So it is essentially a bit of a comparison operation.
So a number with two bits would have the following equation:
You get the point now. But another plus of this equation is that you can actually make the reverse operation and get the first or the second number from the resulting number:
Or otherwise, this can be formulated as
Essentially what this means is that when storing a value (c) we can form that value from the previous and next addresses. This way we can store two addresses in one space.
Simple Implementation
Well, it wouldn’t be an article without some code. I will keep the code simple though since implementing an actual list can be quite different depending on your use case.
template<typename T>
class Node {
private:
T value_;
Node* address_;
public:
Node* GetNext(Node* previous) const { return address_ ^ previous; }
void AddElement(Node* next) {
address_ = address_ ^ next;
next->address_ = next->address_ ^ this;
}
void RemoveSelf(Node* previous) {
Node* next = address_ ^ previous;
// remove this and connect to next
previous->address_ = (previous->address_ ^ this) ^ next;
}
}Of course, a downside to this approach is that you always have to iterate forward by knowing the previous element when you’re using a for loop. So you still have to keep and address to one of the forward or backward elements but it is going to be a local variable that you’re going to iterate while looping and not something to keep in RAM which makes this an overall win for memory optimization. It also should be cheap to execute in general as the XOR operation is really easy to implement in terms of hardware.
Conclusion
Well, this is an example of what clever tricks one might think of when looking for optimizations in the code. Sometimes it might be a small memory optimization, sometimes it might be a CPU one. But a programmer always has to think about these little tricks as they might bring a lot of savings down the road. If you haven’t already – check out my article on the quick square root which is a famous hack by a game developer. It is not so significant in modern days as other calculations have proven to be faster and more efficient but is still a nice
Leave a comment