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