Singly Linked List in Go

Matt Good — Mon, 12 Oct 2020 18:35:26 +0000

Overview

A Linked List is a collection of nodes that together form a linear ordering. Each node is an object that stores a data field and a pointer, called Next, to another node. There are two special nodes within a Linked List:

Head is a pointer to the first element of the list, if the list is empty, then the value of Head is nil.
Tail is optional and points to the last element. We'll see the benefits of this pointer in the next section.

type Node struct {
    Value   interface{}
    Next    *Node
}

type LinkedList struct {
    Head    *Node
    Tail    *Node
}

Operations

Here are some examples of the operations that can be performed on a Linked List. The whole implementation can be found on Github.

Push Front

This operation adds an element to the front of a Linked List. For this purpose you have to create a new node with the desired value
and set the Next pointer to the current head of the list.

Next you have to update the head pointer to point to the newly created node.

func (l *LinkedList) PushFront(val interface{}) {
    node := &Node{Value: val, Next: l.Head}
    l.Head = node
    if l.Tail == nil {
        l.Tail = l.Head
    }
}

If the linked list is empty on adding the element and you're using a Tail pointer, you also have to update the Tail pointer to point to the newly created node (which represents in this case also the head of the list).

Pop Front

To remove the first element of a Linked List you first have to check if the list is not empty.
Then the head of the list needs to be updated to point to its next node. If the head now points to nil, the list is empty and you have to update the tail too.

func (l *LinkedList) PopFront() error {
    if l.Head == nil {
        return errors.New("can't remove from empty list")
    }
    l.Head = l.Head.Next
    if l.Head == nil {
        l.Tail = nil
    }
    return nil
}

Push Back

Adding an element to the end of a list is quite expensive as you have to traverse through the whole list to find the last element. Each node has a pointer to the next node, which allows traversing from head to tail, but not the other way around.
So you would have to iterate all the nodes to get to the end of the list.
Tail pointer to the rescue, which makes this kind of operations way cheaper.

func (l *LinkedList) PushBack(val interface{}) {
    node := &Node{Value: val, Next: nil}
    if l.Tail == nil {
        l.Head = node
        l.Tail = node
    } else {
        l.Tail.Next = node
        l.Tail = node
    }
}

Create a new node with the desired value and set the Next pointer to nil. If the list is empty update both the head and the tail to point to the created node.

Otherwise, update the Next pointer of the current tail to the new node and then update the tail pointer itself.

Pop Back

Similar to the Pop Front operation you have to check if the list is not empty, otherwise throw an error.
Afterwards, if there's only one element in the list set both head and tail to nil as the list is now empty.

func (l *LinkedList) PopBack() error {
    if l.Head == nil {
        return errors.New("can't remove from empty list")
    }
    if l.Head.Value == l.Tail.Value {
        l.Head = nil
        l.Tail = nil
        return nil
    }
    currentHead := l.Head
    for currentHead.Next.Next != nil {
        currentHead = currentHead.Next
    }
    l.Tail = currentHead
    currentHead.Next = nil
    return nil
}

Here it gets a little more complicated, as you have to find the second to last element and as already mentioned, there is no way to traverse back in a Singly Linked List.

So you have to start at the head and walk through the list until you find the second to last element. Once found, update the Tail to point to that second last element (which leaves out the last element).
Finally, set the next pointer of the now last element to nil.

Add After

This operation inserts a new node after another given node.
Therefore, you create a new node with the desired value and set the Next pointer to the node which the given node is currently pointing to.
Update the given node to point to the new node. If the given node was the tail element, also update the tail to point to the new node.

func (l *LinkedList) AddAfter(node *Node, val interface{}) {
    newNode := &Node{Value: val, Next: node.Next}
    node.Next = newNode
    if l.Tail.Value == node.Value {
        l.Tail = newNode
    }
}

Add Before

This operation is the most complicated one, because again, you have to loop through the list from the head to get to the element which comes before the given node.
First, if the list is empty or the given node is the first element of the list, you can re-use the Push Front operation to insert the node as head of the list.

If that is not the case you have to loop through the list until you find the prior element of the given node. Within the loop keep track of both the previous and the current node as you have to insert the new node between these two.
When you have the right place for inserting, you have to check if the current node is not nil (which means you reached the tail) and insert the new node between the two nodes.
Otherwise, add the node to the back of the list via the already implemented Push Back operation.

func (l *LinkedList) AddBefore(node *Node, val interface{}) {
    if l.Head == nil || l.Head == node {
        l.PushFront(val)
    } else {
        var prev *Node
        cur := l.Head
        for cur != nil && cur != node {
            prev = cur
            cur = cur.Next
        }
        if cur != nil {
            prev.Next = &Node{Value: val, Next: cur}
        } else {
            l.PushBack(val)
        }
    }
}

Cost of operations

Operations on the front of the list are cheap thanks to the head pointer. Inserting an element at the back of the list is also cheap (without a tail pointer, this operation would cost O(n)).
Removing the last element runs in O(n) as you have to loop through the whole list, same applies to the Add Before operation.

Operation	no tail	with tail
PushFront(val)	O(1)
PopFront	O(1)
PushBack(val)	O(n)	O(1)
PopBack()	O(n)
AddAfter(Node, val)	O(1)
AddBefore(Node, val)	O(n)

Last, adding an element after an existing node again runs in O(1) thanks to the forward pointers in the list.

When to use

A Linked List has the following advantages over a conventional array:

No fixed size, nodes can be added and removed dynamically.
Inserting and deleting aren't as expensive as there is no need of creating room for shifting existing elements.

In Go we use slices (dynamic arrays) instead of arrays, which takes care of the resizing, so no need for a Linked List for this issue.
But what about the insertion/deletion costs? A talk from Bjarne Stroustrup shows, that there isn't a speed advantage at all for these operations over an array.

So we remain with only disadvantages like increased memory usage (to store pointers) and bad random access speed.

Conclusion

As far as I'm concerned, there's no real world advantage in using a Singly Linked List in Go, just stick with slices.

DEV Community: Matt Good