What is a Linked list

Linked lists are one of the most simpler and basic data structures which are defined by the Wikipedia as follows:

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. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each Node contains: data, and a reference (in other words, a link) to the next Node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.

Why we want to build/use Linked lists

Maybe you’re wondering: “If all we want is a list of adjacent elements… Why not use an array or a slice directly?”.
And the short answer to that question is that it’s generally better and simpler to just use a slice.

The long answer actually looks pretty much like the short one but adding at the end an “although this is not always the case”.

So… When do we want to use Linked lists? Well, the reality is that linked lists have some advantages over arrays and slices, for example:

  • In a Linked list elements can be easily inserted and removed without reallocation (that is because Linked lists need not be stored contiguously in memory).
  • Linked lists also allows to insert or remove nodes at any point in the list in a constant number of operations.

For these reasons, stacks, queues and very simple cache systems are usually implemente using Linked lists.

How can we build a Linked list

To implement a Linked list in Go, we will first define it’s basic component: the Node.

Defining a Node

As we saw in the definition of the Wikipedia:

[…] each Node contains: data, and a reference (in other words, a link) to the next Node in the sequence.

So our Node implementation could be something like this:

type Node struct {
    value int   // Our data
    next  *Node // Pointer (link) to the next Node in the list
}

Defining a Linked list

Our implementation of a Linked list should then, be something like this:

type LinkedList struct {
    first  *Node // The first Node
    last   *Node // The last Node
    length int   // The number of nodes
}

The last field in our implementation is to make it easier to insert (append) new Nodes to the end of our Linked list.

Append

func (l *LinkedList) Append(n *Node) {
    // We check if our Linked list is empty
    if l.length == 0 {
        l.first = n // If it is, we set the first Node to the new Node
        l.last = n  // We also set the last Node to the new Node
        l.length++  // Finally, we increment the length
        return
    }

    l.last.next = n // We link our last Node to out new last Node
    l.last = n      // Then, we set the last Node Node to the new Node
    l.length++      // And finally, we increment the length
}

Prepend

func (l *LinkedList) Prepend(n *Node) {
    // As in Append, first we check if the linked list is empy
    if l.length == 0 {
        l.first = n // If it is, we set the first Node the new Node
        l.last = n  // We also set the last Node to the new Node
        l.length++  // Finally, we increment the length
        return
    }

    firstNode := l.first     // We save our old first Node in a temporal variable
    l.first = n              // Then, we set the first Node to the new Node
    l.first.next = firstNode // Finally we link the new first Node to the old one
    l.length++               // And then, we increment the length
}

Lookup

func (l *LinkedList) Lookup() []int {
    // If the list is empty we return nil
    if l.length == 0 {
        return nil
    }

    var nodes []int
    node := l.first

    // If the next Node is nil (doesn't exist) it means that
    // we're done.
    for node != nil {
        nodes = append(nodes, node.value)
        node = node.next
    }

    return nodes // Then, we can return the slice with all the values found
}

Our Lookup implementation may not be the most correct one. But now that you’ve seen the base, it should be easy for you to modify it according to your needs.

Delete

func (l *LinkedList) Delete(v int) {
    // If the list is empty we have nothing to delete.
    if l.length == 0 {
        return
    }

    // If instead, the Node to delete is the first one on our list
    // we can remove it directly.
    if l.first.value == v {
        l.first = l.first.next // We set the first Node to the second Node
        l.length--             // Then, we decrement the length of our list
        return
    }

    var prevNode *Node // A reference to the previous Node of the one we are looking for
    node := l.first
    for node.value != v {
        // If we have reached the end of the list it means that
        // our Node doesn't exist and that we have nothing to remove.
        if node == nil {
            return
        }

        prevNode = node
        node = node.next
    }

    prevNode.next = node.next // We remove the Node by removing the reference to it from the previous one
    l.length--                // Finally, we decrement the length
}

Go Playground

You can find all the code here.