# Linked lists in Go

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

lastfield 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 linke 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.