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

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