Writing a Linked List using Go - part one

In this article series I will briefly talk about Linked Lists then go about implementing one using Go. This is both a learning exercise for me to get comfortable using Go and to possibly help other developers transition into becoming a Go programmer. That being said please bear in mind I am still learning Go so excuse the code.

Also, Go already has a linked list implemented so better use that in your production code.

Lets begin with a quick refresher on linked lists and for a more detailed analysis read this PDF by Stanford University.

That being said have a look at the following diagram.

A linked list is a simple data structure that is used as the basis for other complex data structures. They are comprised of nodes each containing some data field and a reference field to the next node in the list. In the diagram above our nodes contain an integer field as the data. With this information let us write out the code for a node.

If we were using an Object Oriented language like Python then we could just create a class to represent the node. But Go is a procedural language and it does not have classes. That being said it does have a something similar called struct type which we can use to encapsulate the fields of a node.

type node struct {
    data int
    next *node
}

Here we define a new struct with a data field of type int. The next field has a type of a pointer to a node. Remember pointers store the memory address of the type it is pointing too.

Next up we, need to write the functions to insert and remove nodes into the list. Like I wrote previously Go does not have classes hence you would assume that there wont be methods, but you would be surprisingly wrong. Go has a feature of being able to associate functions with structs methods.

Here is what I mean.

EDIT

Ive simplified the AddToHead method

type LinkedList struct {
    head *node
}

func (ll *LinkedList) AddToHead(data int) {
    ll.head = &node{data: data, next: ll.head}
}

We first create a new struct with a field that is the pointer to the beginning of the linked list. All linked lists need this first reference to able to do any operations on it.

Then we create a method called AddToHead and associate it with the LinkedList struct. This method will create a node with the data that is passed in and then add this node to head of the list. What happens;

• when the list is empty ?
• when there is at least one node in the list (its not a empty list) ?

We handle the first case by checking if the head of the list ll.head is nil which is the zeroed value for a pointer in Go. If ll.head is nil we can just assign ll.head to our tmp node.

If ll.head is not nil we have at least one node in the linked list so we cant just just assign tmp to ll.head as we would lose the references to the rest of the linked list and all of the data. First we have to set the tmp nodes next reference to ll.head to not lose this reference, then reassign ll.head to tmp.

I hope this makes sense. Ive pushed this code onto a repository on GitHub called goll. Once you clone the repository run the following command to checkout the branch containing the code in this article.

git checkout -b part_one

Once this is branch is checked out look at the tests in ll_test.go

In the next post we will look at removing nodes from our linked list and possibly adding another method to insert in sort order.