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.