Working With Linked Lists In Golang

A linked list is a linear data structure, which means it is another a way to represent a sequence of things inside computer memory. You're probably already familiar with arrays, so how are they any different? The main thing to understand about arrays is that the data they contain is contiguous, which means each element of the array is actually physically lined up in one section of memory. This makes arrays really efficient in terms of accessing certain elements, however adding and removing elements in arrays can require a lot of time complexity because you need to shift elements to either make space for new elements or close in gaps left behind by ones that were removed. Also, the fact that they have to be contiguous means that you have to always be sure to have a block of memory large enough to store your array and even more if you have to resize it due to adding more elements than it can hold.

So here's where linked Lists can be useful. Linked lists don't need to be contiguous in memory because each element in a linked list points to the next element. What this means is, you can put the elements anywhere in memory and just update the "next" pointers of individual elements to add items, remove items, and rearrange the list. For example, if you have a linked list like this:

A -> B -> C -> D -> E

and you wanted to add an element, Z between B and C, you just update B so that it points to the new element and make the new element point to C, like this:

A -> B -> Z -> C -> D -> E

None of the other existing elements had to move, so inserting an element is done in O(1) time. If you contrast that with arrays, you would have to shift C and everything following it over one space to make room for Z. This would be O(n) time. Also, if you didn't have enough space in the array, you'd have to increase the size (usually doubling it), so it could also be O(n) space to add a new element in the worst case too. It doesn't look bad for a list this short, but what if you had a million elements in the array? You would notice the performance difference.

So let's get right into what we need to create linked lists. We'll refer to each element in the list as a node. Each node will have a pointer to the next node. The actual list itself will just be a pointer to the first node, which we'll call the head.

type Node struct {
	Data any
	Next *Node
}

type LinkedList struct {
	Head *Node
	mu   sync.Mutex
}

Adding Nodes to the List

Next, we need to add some methods to the linked list struct so we can do stuff like add and remove elements. Let's first create a method that will let us add to the back of it. All we're doing here is:

• 1. Creating a node and getting a pointer to it using the "address of" operator (&)
• 2. Checking to see if the head node already exists or not
• 3. If it doesn't, just set the head node to the one we just created
• 4. If the head does already exist, start at it and loop through each node's "next" node until you get to one that doesn't have a "next". We know that's the last one.
• 5. At that last node, make it's "next" the new one we created in step one

func (ll *LinkedList) AddToBack(data any) {
	ll.mu.Lock()
	defer ll.mu.Unlock()

	new_node := &Node{
		Data: data,
		Next: nil,
	}
	if ll.Head == nil {
		ll.Head = new_node
		return
	}
	current := ll.Head
	for current.Next != nil {
		current = current.Next
	}

	current.Next = new_node
	return
}

You can probably see a downside to adding a node to the back like this. With linked lists, there are no indicies that allow us to be able to directly target the last element in the list. We just have to iterate through the whole list by following the chain of "next" nodes. This means adding to the back is done in O(n) time UNLESS you keep a pointer to the last node on the linked list, which you can definitely do! This example is just the most basic variety, but if you were optimizing your code for lots of adds to the back, you might want to do that... or maybe use a different data structure like a stack or a queue. Just depends on the use case.

Ok, next we should be able to add an element at the front of the list. Very similar logic here:

• 1. Create a node and get a pointer to it using the "address of" operator (&)
• 2. Check to see if the head node already exists
• 3. If it does, set the newly added node's next to it (all nodes after the head will retain their nexts if they have them)
• 4. Make the new node the head

func (ll *LinkedList) AddToFront(data any) {
	ll.mu.Lock()
	defer ll.mu.Unlock()

	new_node := &Node{
		Data: data,
		Next: nil,
	}

	if ll.Head != nil {
		new_node.Next = ll.Head
	}

	ll.Head = new_node
}

Adding a new head will always be O(1) since we don't have to traverse the list. Just put it at the front. But what if we wanted to insert an element after a certain node? All we have to do in that case is:

• 1. Create a node and get it's pointer
• 2. Get the next node of the one we want to insert after and store it in a temp variable
• 3. Set the existing node's next to the new node we created in step one
• 4. Set the new node's next to the existing node's old next (that we have stored in the temp variable)
• 5. If the existing node's next was non existent (nil), the new node's will be too, which means its the new tail

func (ll *LinkedList) InsertAfter(data any, node *Node) {
	ll.mu.Lock()
	defer ll.mu.Unlock()

    if node == nil {
		return
	}

	new_node := &Node{
		Data: data,
		Next: nil,
	}

    temp := node.Next
    node.Next = new_node
    new_node.Next = temp
}

Removing a Node from the List

To remove a node, we'll have to traverse the list up until that node, because we have to know what the previous node was in order to set it's new next to the next of the one we want to remove. There's an exception to this if we have what's called a "doubly linked list", where we'd have a next and previous for each node. this let's you traverse in either direction, but let's keep it simple with our singly linked list for now. The main idea is that we want to:

• 1. Start at the head node
• 2. Iterate through each node's next node until we find the one who's "next" node is the one we want to delete, that's it's previous node.
• 3. Update the node to delete's previous node (that we just found in step two) to point to our new node

func (ll *LinkedList) Remove(n *Node) {
	ll.mu.Lock()
	defer ll.mu.Unlock()

	current_node := ll.Head

	if current_node == nil || n == nil {
		return
	}

	if current_node == n {
		ll.Head = current_node.Next
		return
	}

	for current_node.Next != nil {
		if current_node.Next == n {
			current_node.Next = n.Next
			return
		}
		current_node = current_node.Next
	}
}

Notice how even though we removed that node from the list, it's still in memory, there's just nothing linking to it any more. If we wanted to, we could add it to another list or do anything else we want with it. Of course we could even null it out if we wanted to.

That's basically the gist of linked lists, but let's look at a few different types of linked lists

Some Variants of the Linked List

Like I mentioned above, this is considered a singly linked list because there is only one direction that the links flow in. This is most efficient in terms of memory space because we only store a pointer to each node's next node, but we could also store a pointer to the previous node like this:

type Node struct {
	Data any
	Next *Node
	Prev *Node
}

Now we can start at any node and traverse in any direction. Of course the first node in the list won't have a previous and the last node in the list won't have a next, unless...

...we have a circular linked list. All we have to do to make it into one is point the last node to the first node in the list. And of course, if we have a doubly linked list we can point the head node's previous to the last node in the list.

So that's basically it for the main types of linked lists and the methods they need for you to use them. Now for fun, let's see how we can reverse a singly linked list!!!

Reversing a Singly Linked List

So here's the overall plan. We need to change the direction of the pointers. But how can we do that if we don't know what a node's previous node was? Well, we can actually figure that out in a couple of ways. Let's start with the iterative approach. What we need to do is:

• 1. Start at the head node
• 2. Iterate through each node and store it's next into a temp variable because we're going to need it later but are about to overwrite it
• 3. Make the node in the current iteration have it's next point to the node from the last iteration (more on that in a second)
• 4. Store the current node into another temp variable that will be used for the above step in the next iteration of the loop
• 5. Set the current node to the old next node (that we stored in the temp variable in step two)
• 6. Finally after we finish the loop, the last "new next" node will have been the last node in the loop, which means its now the head node, so set it

func (ll *LinkedList) Reverse() {
	ll.mu.Lock()
	defer ll.mu.Unlock()

	current := ll.Head
	var new_next *Node

	for current != nil {
		old_next := current.Next
		current.Next = new_next
		new_next = current
		current = old_next
	}

	ll.Head = new_next
}

Now let's look at how to do it recursively. The idea here is that we want to take advantage of the way the call stack works with recursive function calls. Every time we recursively call the Reverse Method, it adds a new stack frame on top of the last one. So if we can defer the function calls returning until they reach the last node in the list, we can flip the pointers as the call stack unwinds and we return from the original function call. This function will accept a node as it's parameter and return a node. Since it can't get to the last return until it's base case is met (the head is nil or the head's next is nil), it will keep stacking on stack frames until that happens.

• 1. When the base case is met, the last stack frame will return the last node in the list.
• 2. Since it's the last node in the original list, it's the head in our new list.
• 3. Since the last function call on the stack after original last node will be the first one to continue execution with the returned value, it's next's next will be will be the new head's next, which will be set to itself. This is where the pointer swapping happens
• 4. Doing the above creates a cycle between the last two nodes and we break it by setting the "old" next to last node's (now second) to nil
• 5. Since p is what's returned from each recursive call, this pointer flipping continues until the call stack finishes unwinding.

func ReverseRecursive(Head *Node) *Node {
	ll.mu.Lock()
	defer ll.mu.Unlock()

	if Head == nil || Head.Next == nil {
		return Head
	}

	p := ReverseRecursive(Head.Next)
	Head.Next.Next = Head
	Head.Next = nil

	return p
}

So that's basically linked lists in a nutshell. There's a lot more you can do with them so go practice!