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

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

By the end of this article you should:

  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

  2. DifferencePointer: AddressOfA ⊕ AddressOfC

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:

  • DifferencePointer: NULL ⊕ AddressOfB = AddressOfB

And for Node C:

  • DifferencePointer: AddressOfB ⊕ NULL = AddressOfB

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,

B.differencePointer ⊕ AddressOfA 
= AddressOfA ⊕ AddressOfC ⊕ AddressOfA
= AddressOfA ⊕ AddressOfA ⊕ AddressOfC (Associative Property)
= 0 ⊕ AddressOfC (Self-inverse property)
= AddressOfC (Identity property)

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

B.differencePointer ⊕ AddressOfC 
= AddressOfA ⊕ AddressOfC ⊕ AddressOfC
= AddressOfA ⊕ 0 (Self-inverse property)
= AddressOfA (Identity 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
current = headNode
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).


If you enjoyed reading this article or if it helped you in any way, a 👏 is appreciated. Do share this article with others who may be interested in the topic too.

Stay in touch with me on Linkedin and Twitter. Follow me on GitHub.