# Data Structures with Go - Part 3: Memory Efficient Doubly Linked Lists

Aahan Singh
·Jul 7, 2021·  Subscribe to my newsletter and never miss my upcoming articles

1. Understand how to improve the memory efficiency of Doubly Linked Lists.

2. Understand how pointers and garbage collection determine what can and cannot be implemented in Go.

TLDR: It's impossible to implement this in Go.

As a recap, Doubly Linked Lists store 2 pointers in addition to the data in each node.

But what if we could make this more efficient? That’s exactly what we are going to discuss in this article.

But how? Using binary arithmetic of course 😁

### XOR

XOR (denoted as ⊕) is the equivalent subtraction in the binary number system. If two numbers are the same then XOR results in 0 else it results in 1.

``````1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
``````
• XOR is symmetric i.e. A ⊕ B = B ⊕ A

• XOR is also associative i.e. A ⊕ ( B ⊕ C) = (A ⊕ B) ⊕ C

• XOR of 0 with any other number is that number itself i.e. A ⊕ 0 = A. This is called the identity property.

• XOR of any number with itself is 0 i.e. A ⊕ A = 0. This is called the self-inverse property.

Using these 3 properties we can create more efficient Doubly Linked Lists. So now instead of storing 2 pointers, each node only stores 1. This pointer is the XOR of the previous node’s address and the next node’s address.

Let's say we have 3 nodes in our list: A -> B -> C

Node B has 2 fields,

1. Data

You might recall that the first node in the list has its previous pointer set to null and the last node has its next pointer set to null.

So for Node A:

And for Node C:

Thus the first and last nodes are the only 2 nodes whose `DifferencePointer` actually points to other nodes in the list. Every other node’s `DifferencePointer` stores a proxy which when combined with the address of either its previous or its next node results in the address of another node in the list.

But how do we actually access the elements or traverse the list?

Assume we are at node B. If we want to move to node C, perform the following: `B.differencePointer ⊕ AddressOfA` .

Let’s expand this expression:

``````We know that B.differencePointer = AddressOfA ⊕ AddressOfC

therefore,

= 0 ⊕ AddressOfC (Self-inverse property)
``````

Thus we have found the address to node C. Similarly we can find the address of node A:

``````B.differencePointer ⊕ AddressOfC
= AddressOfA ⊕ 0 (Self-inverse property)
``````

It's now clear that we can use just one pointer in each node. While traversing, all we need to do is use a temporary pointer for traversal which stores the address of the previous node. Using this and the DifferencePointer of each node, we can find the address of the next node.

The pseudocode for this is would look like this:

``````// headNode, tmp & current are pointers to nodes.
previous = NULL
while (current != NULL) {
print(current.Data)
tmp = current
current = XOR(previous, current.DifferencePointer)
previous = tmp
}
``````

## But wait,

### we can’t implement this is Go.

Yeah, you read that right. It is not possible to implement this version of Doubly Linked Lists in go because of 2 reasons:

1. Go doesn’t support pointer arithmetic out of the box. There are workarounds but even if we do implement these workarounds we still can’t implement the data structure because,

2. Any variable that is unreachable is deleted by the garbage collector. In this implementation, only the first and last nodes have a direct pointer to the next (in case of the first node) or previous (in case of the last node) nodes respectively. Every other node in the list is indirectly referenced via the `DifferencePointer` which means that they are unreachable.

If you’d like to read about these 2 points in some more depth:

1. Talks about how pointers in Go are different than in C or C++: https://dave.cheney.net/2014/03/17/pointers-in-go

2. Talks about converting pointers to integers: https://utcc.utoronto.ca/~cks/space/blog/programming/GoPointerToInteger

### You should now:

1. Understand a little more about pointers in Go.

2. Know how the memory efficiency of Doubly Linked Lists can be improved (albeit not in Go).