Singly Linked List in Go
Tags: go, computerscience
Published: 2020-10-12 18:35:26

---
title: Singly Linked List in Go
published: true
description: "How to implement some operations of a Singly Linked List in Go"
tags: ["Go", "ComputerScience"]
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/kxct2s39uka0tgj7y8hi.jpg
---

## 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.

```go
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](https://github.com/MatthiasGood/go-datastructures/blob/main/linkedList.go).

![Linked List Structure](https://dev-to-uploads.s3.amazonaws.com/i/tenx110gggnpgwj678iq.png)

### 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](https://dev-to-uploads.s3.amazonaws.com/i/dykaijfcb59cmkwst4fv.png)

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

```go
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.

```go
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.

```go
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](https://dev-to-uploads.s3.amazonaws.com/i/nk5eo7n66ech1kokiv3s.png)

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](#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.

```go
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](https://dev-to-uploads.s3.amazonaws.com/i/xw3fn9e14yzsyl9uqusm.png)

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.

```go
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](#push-front) operation to insert the node as head of the list.

![Linked List Add Before](https://dev-to-uploads.s3.amazonaws.com/i/m3e9fmyiu3ce7fhf2q6a.png)

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](#push-back) operation.

```go
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](#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](https://www.youtube.com/watch?v=YQs6IC-vgmo) 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.