Matt Good

Singly Linked List in Go

5 Oct 2020
Linked List Overview

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:

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

type LinkedList struct {
	Head 	*Node
	Tail 	*Node
}

Operations

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

Linked List Structure

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.

Linked List Push Front

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.

Linked List Push Back

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.

Linked List Pop Back

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.

Linked List Add Before

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.

Operationno tailwith tail
PushFront(val)O(1)
PopFrontO(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:

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.