# Doubly linked lists in Go

## What is a Doubly linked list

Like Linked lists, Doubly linked lists are a very simple data structure whose definition from Wikipedia is:

A Doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each Node contains three fields: two link fields (references to the previous and to the next Node in the sequence of nodes) and one data field.

Basically now our *Node* struct will have a value, a link to the next Node in the list and another link to the previous one.

## Doubly linked lists VS Linked lists

Doubly linked lists have an important difference over Linked lists: **they can be traversed in forward or backwards directions**.

With Doubly linked lists is also more easy insert new Nodes before existing ones.

But Doubly linked lists are not perfect and have disadvantages over Linked lists:

- Each
*Node*requires extra space due to the extra pointer. - All operations become a little more complicated because you have to manage now the extra pointer.

## How can we build a Doubly linked list

To implement a Doubly linked list in Go we need to start defining it’s basic component: the *Node*.

### Defining a Node

```
Type Node struct {
value int // Our data
pre *Node // Pointer to the previous Node
next *Node // Pointer to the next Node
}
```

### Defining a Doubly linked list

```
Type DoublyLinkedList struct {
head *Node // The first node
tail *Node // The last node
length int // The number of nodes
}
```

### Append

```
// Append adds a *Node to the end of the DoublyLinkedList
func (dl *DoublyLinkedList) Append(n *Node) {
// We check if our Doubly linked list is empty
if dl.length == 0 {
// If it is we set the first and the last node
// to the new one and finally we increment the length.
dl.first = n
dl.last = n
dl.length++
return
}
// If no, we save the pointer of the last Node in the list.
lastNode := dl.last
// Then, we update the last node (tail) in our Doubly linked list
// with the new Node, connecting it to the previous last Node
// and also connecting our previous last Node to the new one.
// Finally, we only need to increment the length.
dl.last = n
dl.last.pre = lastNode
lastNode.next = n
dl.length++
}
```

### Prepend

```
// Prepend adds a *Node to the start of the DoublyLinkedList
func (dl *DoublyLinkedList) Prepend(n *Node) {
// We check if our Doubly linked list is empty
if dl.length == 0 {
// If it is we set the first and last node
// to the new one and finally we increment the length.
dl.first = n
dl.last = n
dl.length++
return
}
// If out list is not empty, we save the pointer of the
// first Node in the list.
preFirstNode := dl.first
// Then, we update the first node (head) in our Doubly linked list
// with the new Node, connecting it to the previous first Node
// and also connecting our previous first Node to the new one.
// Finally, we only need to increment the length.
dl.first = n
dl.first.next = preFirstNode
preFirstNode.pre = n
dl.length++
}
```

### Lookup

```
// Lookup ranges over the DoublyLinkedLIst and returns
// a []int with all the values found.
func (dl *DoublyLinkedList) Lookup() []int {
if dl.length == 0 {
// If our list is empty we simply return nil
return nil
}
// If not, we range over the nodes saving each node's value
// into a slice which we'll return.
var nodes []int
node := dl.first
// If the next Node is nil it means that we are
// done.
for node != nil {
nodes = append(nodes, node.value)
node = node.next
}
return nodes
}
```

### Delete

```
// Delete removes a Node from the doubly linked list with the
// same value as the received.
func (dl *DoublyLinkedList) Delete(v int) {
if dl.length == 0 {
// If our list is empty we simply return
return
}
// If the Node to remove is the first one on our
// list we remove it directly and then return.
if dl.first.value == v {
dl.first = dl.first.next
dl.first.pre = nil
dl.length--
return
}
// If the Node to remove is the last one on our
// list we remove it directly and return.
if dl.last.value == v {
prePreLastNode := dl.last.pre
dl.last = prePreLastNode
prePreLastNode.next = nil
dl.length--
return
}
// Finally, if the first Node nor the last Node are the nodes
// we are looking for, we range over the list trying to find
// it. If the Node don't exist we simply return. If exists we
// simply remove it removing it's pointers from the previous
// node and the next.
var prevNode *Node
var nextNode *Node
node := dl.first
for node.value != v {
if node == nil {
return
}
prevNode = node
node = node.next
nextNode = node.next
}
prevNode.next = node.next
nextNode.pre = prevNode
// In each case we have to remember to decrease the lenght.
dl.length--
}
```

## Go playground

You can find all the code here.