Linked List

What is a linked list

According to the Almighty Wikipedia, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. So they are similar to arrays, but allow for more flexible memory location. Arrays must have contiguous memory, while linked lists allow memory to be spread out. Each node in the list will provide a pointer to where the next node resides in memory so you can find it by running down the chain.

How do we build one

Initial boilerplate

Let’s start by creating a file called main.go. In it, we will paste this basic code to get us up and running:

package main

import (
    errors
    log
)

func main() {
    // Optionally parse flags here

    if err := run(); err != nil {
        log.Fatalln(err)
    }
}

We will define the run function later.

Structs

Every good data structure needs structs. Here, we need two:

type node struct {
    next *node
    elem string
}

type linkedlist struct {
    head *node
    tail *node
    size int
}

The node struct has a pointer to the next node as it’s first member. By default, node.next will be nil, which is fine. We will link the nodes by adding nodes to the next variable. The elem variable is the actual data we care about. This can be of any type, we are just using strings to keep it simple.

The linkedlist struct is the actual meat and potatoes of everything. All of the methods we are about to define will come from this struct. As you can probably guess, head is the first node in the list, tail is the last, and size holds the count of how many nodes are in the list.

Methods

Methods adds functionality to our structs. There are many different possible methods we could use, but at its core, a linked list needs the following:

func (l *linkedlist) push(elem string) {
    n := &node{
        elem: elem,
    }

    if l.size == 0 {
        l.head = n
        l.tail = n
    } else {
        l.tail.next = n
        l.tail = n
    }

    l.size++
}

func (l *linkedlist) at(index int) (string, error) {
    if index >= l.size {
        return , errors.New(Index out of bounds)
    }

    node := l.head
    for i := 0; i < index; i++ {
        node = node.next
    }

    return node.elem, nil
}

The first function, push, is used to add a new element to the end of the list. I could call the function append, but that’s already keyword in golang, so we’ll call it push. Later, we will see data structures that have push and pop. First, push creates a node that holds the elem we were given. Then it does two different things depending on the size of the list. If the list is empty (l.size == 0), we simply point head and tail to the new node. If the list already has something in it, we tell the last node to point to the new node l.tail.next = n, then we set the new node to be the last node in the list l.tail = n. Order is important here. If you swap those two lines, you will get nil pointer errors. Then, finally, we increment the size by one since we just added a node.

The second function, at, simply returns the node at the specific index. This is 0-based indexing so calling at(0) will return the first element in the list. We have to do bounds checking, which is why we can return an error, but otherwise we simply return the element of the node at that index. Looking at the code now, we see that the first if statement does the aforementioned bounds-checking, then we simply loop through the nodes. This is the ‘linked’ part of ‘linked list’. Here, the node variable is a pointer to a node in the list. We incrementally move this pointer down the chain by setting node = node.next. Once we iterate the correct number of times, we return the element of the current node. As you can see, this data structure does NOT allow for random access. That means if we have a list with 2,000 elements, and we want to find the 1,000th element, we need to loop over the 0th element, then the 1st, then the 2nd, etc. So the at function grows linearly with the size of the list.

Constructor

I know golang doesn’t have constructors per se, but we can still define a function that returns a linked list so we don’t have to repeat ourselves.

func NewLinkedList(elems ...string) *linkedlist {
    ll := &linkedlist{}

    for _, v := range elems {
        ll.push(v)
    }

    return ll
}

First, we create an empty linkedlist. This allows to reuse the methods that are defined for that structure. Namely, we call push once per element in the elems slice. Then we simply return a pointer to the list.

Usage

The run function is where we get to use the linkedlist.

func run() error {
    ll := NewLinkedList(foo, bar)

    log.Println(ll.at(0)) // foo nil
    log.Println(ll.at(1)) // bar nil
    log.Println(ll.at(2)) //     Index out of bounds

    ll.push(baz)
    log.Println(ll.at(2)) // baz nil

    return nil
}

You can see we create a linkedlist with two elements, then we print out those two elements. We also try to print the element at index 2, but we get an error. So we simply append a new element and then we can print out that element. It’s worth noting that you don’t need to know anything about a node to use a linkedlist. If we were putting this into a library, we could keep node as unexported and only export the linkedlist and its associated methods. We don’t even need to export the fields on a linkedlist. This dramatically cleans up the code.

In the above example, we create a single linked list that can add and retrieve elements. In order to be CRUD complete, we still need to be able to update an element as well as delete it. There are even some scenarios where we need have pointers going forward and backwards in what’s called a doubly linked list. That will be as simple as changing the node type to be:

type node struct {
    prev *node
    next *node
    elem string
}