Part 2: Linked Lists

This post is part of a series on the fundamentals of computer science. If you haven’t already, you can read an introduction here, or take a deep dive into the level basics of how memory works here.

‍

Recap

Let’s recap: arrays are stored in memory contiguously, so it’s difficult to add or remove elements to them - that would require us to move, in the worst case, the entire array to a new place in memory, leaving a bunch of empty houses behind. And I promised to present a solution to this problem: linked lists.

But before we jump into that, let’s pay extra attention to how addresses work in our little (or, as we will see very soon, indeed big) town of Memory.

Do you remember the very short 64-bit vs 32-bit mention in the previous post? Turns out, they are directly related to our addresses!

32 bits can be used to encode a whopping 4,294,967,296 (2^32, i.e. 2 to the power of 32) different states, or numbers. That’s more than 4 billion numbers, which seems like a lot! If our town of Memory had 4,294,967,296 houses, we could number each one of them with numbers from 1 to 4,294,967,296! That’s a lot of houses, I bet we could store a lot of useful information in there… 4 gigabytes?

👉 This is why old operating systems (and CPUs) that were built on the 32-bit architecture could only have up to 4GB of RAM. You could put as much RAM in your PC as you wanted, but the OS wouldn’t be able to use anything past the first 4GB.

Ok, so we have 4,294,967,296 houses. Now, imagine that we wanted to write someone’s house number down. If we did that, that number would take up… 32 houses, that’s right! So by using mere 32 houses, we could write down the address of anyone in our little town.

👉 64 bits, on the other hand, can be used to encode 18,446,744,073,709,551,616 different numbers. That’s why 64-bit operating systems can have more than 4GB of RAM.  A lot more. Don’t even try to compare these numbers, one is so much more ridiculous than the other.

Cool, back to the topic of this post. For the sake of consistency and being modern, we will keep using a 64-bit system. Of course, in a 64-bit system, it would take 64 houses, not 32, to write down a single address.

Previously, we saw how we can store variables like true, [true] or 1in our houses of Memory. However, if a memory address is just a 64-bit number, that means that we can store addresses in the very same memory! 🤯

‍

Pointers

A commonly used term is “a pointer”. It’s a pointer because it merely points to the real value, rather than containing it. We’re also introducing pointer variables, which are exactly that - instead of storing a number directly, it points to a memory address where the number is actually stored.

👉 I’m switching to Go here to demonstrate what you might see in other lower level programming languages (they are not low level, just lower level than Ruby), and to easier demonstrate what certain structures look like under the hood. Asterisks *  usually mean that we’re declaring a pointer variable or following the pointer (dereferencing it), and ampersands & that we’re writing down the address of a variable.

Okay, so now we can deal with integers, and pointers to integers.

So how does this help us with our original problem, inserting a new value in the middle of an array?

Well, the first thing we’d have to do is stop storing the array as an array, and instead store it as a linked list.

Woah woah woah, what the hell has just happened?

Oops, sorry, let’s break down the new things I’ve introduced here.

type LinkedListNode struct - this is how we define Structs in Go. We only need to care about LinkedListNode here, it’s the name of our new struct.

What is a struct? It’s basically a complex type. Whenever a single integer is not enough for your needs (that must be pretty rare, right?), you need a struct. Or a class, which is essentially the same thing, but with its own quirks which we will not be discussing today.

*LinkedListNode - well, we’ve just talked about how we can point to integers. There’s nothing stopping us from pointing to anything else in our town of Memory, and since the nodes of our linked list will have to live in Memory (because there’s nowhere else for them to be), we can point to them, and we would have to use the same 64 bits for that pointer.

‍

How does our new friend Linked List work?

Instead of storing our 1024 values contiguously, we can store them in a Linked List. Our single LinkedListNode would take up 65 bits of memory: 1 bit for the actual value, and 64 bits for the pointer to the next value.

If we initialised this list, we would store the first value in house number 1, and the second value in house number 66 (1 + 65). The pointer in the first node would point to house number 66. The pointer in the second node would point to house number (66 + 65 =) 131, and so on.

An astute reader will exclaim, “But what about the last node, where would its pointer point to?” Another astute reader will point out that, for some reason, our house numbering system starts with 1, whereas everybody knows that the first item in an array has an index of 0, not 1!

That’s because in memory, 0 is a special address, otherwise called null or nil. It points to nothing. Zilch. Nada.

So, very simply, the next pointer of the last node in our list will have a value of 0, or nil.

So, if we wanted to insert a new node in this list, between the first and the second nodes, this is how it could look like:

Nobody had to move houses! Our newest neighbour moved in the first available house, and then we only had to change the values of one pointer - the first node now points to the fourth node (fourth in the memory order) rather than the second one (again, in the memory order).

And this scales! We could have a million items in our linked list, and still have to perform only one update to add a new item to it. Pretty cool, eh?

‍

Let's wrap this up

In this post, we’ve (hopefully) learned a bunch of new things, most notably, pointers and structs. Hold on to them - some time soon, we will look into data structures more exciting than linked lists. But before that, we will take a side step to talk about computational complexity, i.e. O(n).