Exploring container package in Go (list, ring and heap)

July 3, 2020July 8, 2020

Using heap, list and ring

Photo byMitchell Luo onUnsplash. If you want, you can Download it

The container package is  an implementation of common data structures like doubly linked lists and heaps. As I studied them, I realized they are quite useful so lets first start with the list package, which is a doubly linked list. 

List

This package is quite straightforward but it has some gotchas that you might not expect. You can instantiate a list with the list.New() function. Don't forget that you can play around and execute the below code.

The package provides some common functions to put items in the list like list.PushFront, list.PushBack, list.InsertAfter, list.InsertBefore and others so lets see the list.PushFront since that might be the first one that you might use. The rest of them are quite straightforward and easy to use.

What you might expect from this example is that it prints numbers from 1 to 5 but it actually prints them in reverse, from 5 to 1. When a list is instantiated, it is created with a root element. That root element is the starting point for every list. When you add a value to the list, that value is inserted right of the root element. When you insert the next value, the previous one is moved one place to the right and the next one is inserted in its place, making the current element inserted next to the root. Lets explore that in the next example.

Iterating a list

You can iterate a list from the front or from the back by using the list.Front() and list.Back() functions.

When you call list.Back() or List.Front(), an *Element struct is returned. This struct has next and prev values that are pointers to the next and previous element of the list so it can be used to go trough the values without a loop. The value in an Element can be accessed as el.Value.

Note that trying to access a previous list item from the front of the list is not allowed since a list is not circular.

Heaps

The package documentation states the definition of a heap as this package implements it:

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

From this definition, I thought that this package is an implementation of a tree structure but, from what I've seen from playing with it and looking at the source code, it's actually a sorted list.

heap Interface

Before I show you how to implement the simplest heap, I have to tell you about the heap.Interface.

As you can see, heap.Interface uses sort.Interface so both of them must be implemented. So, let's implement heap.Interface first and then start using it. 

In order to use the heap, your type has to implement the heap.Interface. This interface inherits the sort.Interface that has 3 functions: Len(), Less(i, j int) and Swap(i, j int). Len() is used to get the length of your type, Less(i, j int) is used to determine whether the element with index i should sort before the element with index j, and finally, Swap(i, j int) swaps the elements with indexes i and j. All of these functions must be implemented by you, the user and the heap package uses them internally. 

Before I start explaining anything, I'm going to implement heap.Interface, then go from there. First, lets implement the ones from the sort.Interface.

Implementing heap.Interface

Implementing Len() is quite straightforward. Len() only returns the size of the list.

As I said in the explanation of Less(i, j int), it is used to determine whether the element with index i should sort before the element with index j. From looking at the source code of the heap implementation, Less() is used to determine weather the elements should be swapped. From the implementation above, Less() returns true if i < j which means that the list that implements this Less() will sort our list from min to max. If we switch the condition to >, the list will be sorted from max to min. Swap(i, j int) just replaces the values at indexes i and j

Right now we still cannot use the IntHeap because we still need to implement Push() and Pop(). So lets do that now...

Don't forget that Push() and Pop() have to use pointer receivers since they modify whatever data structure they are working on. Below is an example of accessing the values of a heap.

Keep in mind that when you call heap.Init(), it sorts the structure that you gave it. The same thing happens when using Push() or Pop(). 

If you tried executing the code, you would see that IntHeap is now sorted, min to max. If you change Less() function to sort from max to min, it will do that.

The documentation also provides the source code of a PriorityQueue so I'm not going to put it here since it is very comprehensive so check it out in the docs

Ring

From the documentation, Package ring implements operations on circular lists. Its a simple explanation but lets go straight into an example to see what is going on. First, I am going to create a ring with the New() function just to see what it does.

Basic example

When a ring is created with the number of rings in it with ring.New(5), internally, 5 rings are actually created. Lets take a look at the actual source code of ring.New()

I you look at the signature of a ring, you can see that it has prev and next ring.Ring instances and a Value field that is a generic interface{} so you can put anything into it. 

You can see if we put 5 as the number of rings, 5 ring.Ring structs will be created. The same goes for 10 million so keep that in mind when working with rings.

Also, creating 0 (zero) rings will not create a new ring but will return nil. 

Populate a ring

You populate a ring by assigning a value to the ring.Value field.

Or better yet, in a loop.

Iterating a ring

Iterating a ring is done with the ring.Do() function that accepts a function that then, receives the next ring instance as its value. 

You can implement your own loop that iterates the ring but mind you that a ring is a circular structure and you have to have a way of stopping it. 

Note that, since a ring is a circular structure, you can pick any ring in that structure and start iterating it. 

Conclusion

That is it. I hope container can be a useful package for your project and that this post explained it well.

Side note: I created this blogging platform in which you are reading this blog. If you like it, it would mean a lot to me if you start writing on it. I created it because I wanted to create a place for you, software developers, to be able to express yourself in code. I hope you will at least consider it. If you have any suggestions/questions/bug reports, you can send it to me on marioskrlec111@gmail.com. Although this platform is still young, I have big plans for it and if you try using it, together we can create a blogging platform for software developers from all backgrounds and experiences, even for PHP developers (just kidding, I worked in PHP for 5 years and I like it).