Linked Lists in Go

Cute gopher listening to its music playlist written in Go

Linked lists are one of the basic data structures that we come across in computer programming. In this article, we are going to learn different types of linked lists, operations and its complexity. To make things interesting we are going to learn all these by building a music playlist in Golang for our cute little gopher.

Linked lists are nothing but a bunch of nodes containing the data and a pointer to access the next node.

There are 3 types of linked lists.

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Let’s take a look at each type.

Singly Linked Lists

Singly linked lists are the simplest type of linked lists where a node contains the data and pointer only to its next node. Which means you can only iterate them in one order, not reverse.

Since a pointer to next node is stored on the node itself, it is not necessary that all nodes should be stored sequentially in memory. Unlike arrays, the elements in the linked lists are not stored sequentially in memory.

nodes in the linked list pointing to the next node, stored in a non-sequential way

If you notice the above picture, the address of the first node — 0x00000000 is the address of the first node. You should never lose the address of the first node in a singly linked list, or else you will not be able to find out the head node.

Losing the head node in the singly linked list means losing access to your linkedlist. When I say “never lose the address of head node”, it means you have to be careful while storing it in global variables and prevent replacing it or watch out for variable scopes in local variables.

Also in the same picture, the last element of the singly linked list stores nil as it has no more next node to point to.

We are going to build the music playlist now. We know that the music playlist will have a sequence of songs and we can listen to the next song by clicking the next track button. ⏭

There are primarily two entities here. The playlist itself and the songs in the playlist. We need to define them in our code.

Our song type has the fields name, artist and next — a link to the next song.

type song struct {
  name string
  artist string
  next *song
}

Fields in our playlist are the name, start — a pointer to the head of our linked list or first song in the playlist and nowPlaying which points to currently playing song.

type playlist struct {
  name string
  start *song
  nowPlaying *song
}

We need five main operations here to implement a basic playlist.

1. Create a playlist
2. Add song
3. Show all songs
4. Start playing
5. Next/Previous Song

It’s time to implement these operations in our Go code.

After defining our song and playlist structs. We have a createPlaylist() function that returns an instance of the playlist.

The addSong() method first checks whether the linked list is empty if not it then iterates through the linked list by using the pointer to next song until currentSong.next becomes nil. When the next song is nil, it means we are at the end of the linked list. Now we add a new song by linking it to the current song.

showAllSongs() method simply iterates through our playlist(linked list) and prints every song one by one.

startPlaying() method starts playing the playlist by playing the first song. nextSong() method plays next track.

When you run the code by calling all the methods from the main() function, the code prints the following.

Created playlist
Adding songs to the playlist...
Showing all songs in playlist...
{name:Ophelia artist:The Luminers next:0xc0000701b0}
{name:Shape of you artist:Ed Sheeran next:0xc0000701e0}
{name:Stubborn Love artist:The Luminers next:0xc000070210}
{name:Feels artist:Calvin Harris next:<nil>}
Now playing: Ophelia by The Lumineers
Changing next song...
Now playing: Shape of you by Ed Sheeran
Changing next song...
Now playing: Stubborn Love by The Lumineers

Now we implemented a basic music playlist for our app. But it is missing one important operation. There is no functionality implemented to get back to the previous song. Singly linked list has only access to the next node in the list. So in order to implement the previous track ⏮, we need to use doubly linked lists.

Before going to doubly linked lists, if you notice our addSong() function, it iterates through every node in our linked list to add a new song. This operation is costly — O(n). We can avoid this by keeping track of the tail node. If we have the track of tail node, we simply can link new node to tail directly without iterating through the list.

We will keep track of the tail node in a doubly linked list which we are about to implement.

Doubly Linked Lists

The only difference between the singly and doubly linked is that apart from storing a pointer to the next node, each node also stores the pointer to the previous node.

Doubly linked lists having access to both next node and previous node

Having access to the previous node allows us to iterate the linked list in reverse order. This exactly what we need in order to help our little gopher to get to the previous song in its playlist.

Our type definition for playlist and songs will change now.

type song struct {
   name     string
   artist   string
   previous *song
   next     *song
}

We have added a field called previous to store the pointer to the previous node.

Our playlist type looks like this.

type playlist struct {
  name       string
  head       *song
  tail       *song
  nowPlaying *song
}

If you notice, in our playlist struct we also store the field tail, which points to the tail node of the LinkedList.

Here is the code for doubly linked list implementation. It is similar to the singly LinkedList snippet except for the part where we have added a few extra fields to our structs and a small change in our addSong() method.

While the rest of all methods remaining same, in line number 33, inside addSong() method we are directly jumping to the tail node instead of iterating from first. This changes the insert operation to O(1) from the previous O(n). Then we link the new node to the existing tail node, link the tail node as new node’s previous node and finally set the new tail node by doing p.tail = s outside the else condition.

We have also added the new function previousSong() which will help our gopher to switch to previous tracks. Running the code will print the following. We are now able to seek the next track and previous track as well.

Created playlist
Adding songs to the playlist...
Showing all songs in playlist...
{name:Ophelia artist:The Lumineers previous:<nil> next:0xc0000701b0}
{name:Shape of you artist:Ed Sheeran previous:0xc000070180 next:0xc0000701e0}
{name:Stubborn Love artist:The Lumineers previous:0xc0000701b0 next:0xc000070210}
{name:Feels artist:Calvin Harris previous:0xc0000701e0 next:<nil>}
Now playing: Ophelia by The Lumineers
Changing next song...
Now playing: Shape of you by Ed Sheeran
Changing next song...
Now playing: Stubborn Love by The Lumineers
Changing previous song...
Now playing: Shape of you by Ed Sheeran
Changing previous song...
Now playing: Ophelia by The Lumineers

The only major difference in the implementation here is that when you add a new node to doubly LinkedList, you need to tell the LinkedList that the current tail node is the new node’s previous node.

Circular LinkedList

A circular linked list is one which can loop back from the last node to the first node and vice versa.

You can make the singly or doubly linked lists circular by linking the last node back to the first node. This can make our music playlist to loop back to the first song after pressing next track ⏭ while playing the last song in the playlist.

Doubly LinkedList made list made circular by linking last and first nodes to each other

It is easy to implement this in our music playlist code. So I will leave it up to you to figure it out:)

Operational Cost

When we implement any data structure in our code, it is important to know the operational cost. It will help you to optimise your code and do right tradeoffs based on the use cases. Usually, Big O notation is used to measure the complexity.

Here are the complexities of different operations in linked list.

Access — O(n)

Search — O(n)

Insert— O(1)

Delete — O(1)

LinkedList vs Arrays

You might think that arrays are available in all programming languages out of the box, why we have to implement a LinkedList and maintain them.

Yes, arrays are easier than linkedlists in some languages that don’t provide linear collections as a part of standard library, but there are few nuances.

Even though arrays allows us to access the element in O(1) if we know the index, insertion of elements to an array will cost O(n). Appending an element to end of an array is quite easy, but if you append something to the middle, all other elements after that should be moved by one step.

Adding an element to the middle of an array needs shifting

This is one of the major difference between LinkedList and array. If you are implementing a priority queue where you need faster insertions in the middle, it is a good idea to go with LinkedLists.

Also remember, LinkedLists are bit heavy because it holds data as well as a pointer to next node, where array holds only the data. You have to compromise on the space complexity in order to have a better time complexity. End of the day software is about doing right tradeoffs.

LinkedLists are the basic DS used in computer programming and there are many other data structures built on top of LinkedLists.

Sometimes it feels so good to go back to fundamental simplicity from the highest complexity. It felt good for me when I brushed up my data structure knowledge before writing this post. Hope you enjoyed it.

Loved getting back to the basics?, follow BackendArmy on medium for more posts on applied data structures and algorithms.

Found this post interesting?
It would mean a lot to me if you could hold the “clap” icon and give a shoutout to me on twitter. That would really make my day.

Also, you can subscribe to our newsletter to receive more blog posts and premium courses on backend engineering.
— thanks!