Implementing Doubly Linkedlist using Golang

Introduction

In the last post we saw how to implement a Singly Linkedlist from scratch using golang. In this blog we’ll see how to implement Doubly Linkedlists in Golang.

Doubly Linkedlist

In a Doubly linkedlist each node can point to next as well as the previous node in the sequence. Hence in doubly linkedlist we have one more pointer in node called previous. Just like the Singly Linkedlist tail of Doubly linkedlist points to a null node.

Implementing Doubly Linkedlist

As mentioned above a doubly linkedlist’s node has a next pointer as well as a previous pointer. Hence the struct for a Doubly linkedlist would look like this:

type DoublyLinkedlistNode struct{
    data int
    next *DoublyLinkedlistNode
    previous *DoublyLinkedlistNode
}

In DoublyLinkedlistNode we have added one more pointer called previous. data can be of any datatype(string, double, struct, etc) available in Go.

The wrapper struct for a DoublyLinkedlist would look like this:

type DoublyLinkedlist struct{
    head *DoublyLinkedlistNode
    tail *DoublyLinkedlistNode
    size int
}

Insertion in a Doubly linkedlist(at the end)

We have the same conditions as we had in a Singly linkedlist for insertion:

• When the linkedlist is empty.
• When the linkedlist is not empty.

We will write a similar function as we wrote for Singly linkedlist.

func (d *DoublyLinkedlist) Insert(newNode *DoublyLinkedlistNode){
    // checking if linkedlist is empty
    if d.size == 0 && d.head == nil{
        // since the linkedlist is empty we make the newNode both head and tail
        // this is because newNode will be the only node in linkedlist
        d.head = newNode
        d.tail = newNode
    } else{
        // while inserting at the end
        // first we point linkedlist's tail's next to our newNode, as newNode will be the next in sequence now
        d.tail.next = newNode
        // we point newNode's previous to the current tail of linkedlist
        newNode.previous = d.tail
        // finally we make newNode the tail of our linkedlist
        d.tail = newNode
    }
    // at the end we increase size of linkedlist by one
    d.size += 1
}

Key takeaways from above code:

• When linkedlist is empty:
  • We simply make the newNode as both the head and tail of linkedlist. This is done because newNode is the only node in our linkedlist hence it represents both head and tail.
• When linkedlist is not empty:
  • First we make tail's next point to our newNode.
  • Then we make newNode’s previous point to tail of the linkedlist.
  • Then finally make newNode the tail of our linkedlist.
• At the end we increase size of linkedlist by one.

Inserting at a given position

For inserting at a given position we need the position of insertion and the node to insert.

Since there’s a possibility that the position we pass to the function maybe out of bound we will return error from this function.

// isInRange checks if passed index is +ve and less than or equal to current size of linkedlist
func (d *DoublyLinkedlist) isInRange(index int) bool{
    return index >= 0 && index <= d.size
}

func (d *DoublyLinkedlist) InsertAt(index int, newNode *DoublyLinkedlistNode) error {
    // checking if passed index is out of bounds
    if !d.isInRange(index){
        // return error if index is out of bounds
        return errors.New("Index out of bounds")
    }
    // find the node before which newNode needs to be inserted
    currNode:= d.head
    for i := 0; i != index; i, currNode = i+1, currNode.next{        
    }
    // if the insertion node is head of linkedlist
    if currNode == d.head{
        // make newNode's next to point to head of linkedlist
        newNode.next = d.head
        // make current head's previous point to newNode
        d.head.previous = newNode
        // make newNode the head of linkedlist
        d.head = newNode
    } else if currNode == d.tail{
        // if insertion node is tail of linkedlist
        // then we can simply call our Insert function we wrote earlier
        // since newNode needs to be inserted at the end of linkedlist
        d.Insert(newNode)
        // return nil error
        // we don't let current function increase size of linkedlist
        //  since it is already handled by Insert function
        return nil
    } else {
        // this condition means we're inserting somewhere in the middle
        // make newNode's previous point to currNode's previous
        newNode.previous = currNode.previous
        // make currNode's previous' next point to newNode
        currNode.previous.next = newNode
        // make newNode's next point to currNode
        newNode.next = currNode
        // make currNode's previous to point to newNode
        currNode.previous = newNode
    }
    // finally increase size and return nil error
    d.size +=1
    return nil
}

Key takeaways from above code:

• Since we’re taking index as input from user we need to check if index is out of bounds.
• We find the node(currNode) before or after which the newNode needs to be inserted.
• If currNode is head of linkedlist then we need to insert newNode before currNode, to do that:
  • We make newNode’s next to point to head of linkedlist.
  • We make current head’s previous point to newNode.
  • We make newNode the head of linkedlist.
• If currNode is tail of linkedlist then we need to insert newNode after the currNode, to do that:
  • We simply call our Insert function we wrote earlier, since newNode needs to be inserted at the end of linkedlist. In any other condition we need to insert newNode before the currNode, to do that:
  • We make newNode’s previous point to currNode’s previous.
  • We make currNode’s previous’ next point to newNode.
  • We make newNode’s next point to currNode.
  • We make currNode’s previous to point to newNode.
• Finally we increase size and return nil error.

Getting value from a doubly linkedlist

We can write a simple function to get the value from a doubly linkedlist at a certain index by iterating over the linkedlist.

Since we will again be taking an index as argument we need to return an error in case the index is out of bounds of linkedlist.

func (d *DoublyLinkedlist) Get(index int) (int,error){
    // checking if passed index is out of bounds
    if !d.isInRange(index) {
        // return error if index is out of bounds
        return -1, errors.New("Index out of bounds")
    }
    // find the node at the passed index
    currNode := d.head
    for i := 0; i != index; i, currNode = i+1, currNode.next{        
    }
    // return data from the node found at index
    return currNode.data, nil
}

Key takeaways from above code:

• Since we’re taking index as input from user we need to check if index is out of bounds.
• Find the node at passed index by iterating over the linkedlist. Since this is a doubly linkedlist we can iterate the linkedlist from head or the tail of linkedlist. Above code iterates from head of linkedlist.
• Return data from node found at index and nil error.

Deletion in Doubly linkedlist

Like we used index to insert in linkedlist we can use index to delete from a linked list as well.

For deletion we will need to find the deletion node. Since we’re implementing doubly linkedlist we can easily get previous node, so we don’t need to find previous node.

Since we will again be taking an index as argument we need to return an error in case the index is out of bounds of linkedlist.

func (d *DoublyLinkedlist) RemoveAt(index int) error{
    // check if passed index is out of bounds
    if !d.isInRange(index) {
        // return error if index is out of bounds
        return errors.New("Index out of bounds")
    }
    // find deletion node
    delNode := d.head
    for i :=0; i != index; i, delNode = i+1, delNode.next {        
    }
    // if deletion node is head of linkedlist 
    if delNode == d.head {
        // make deletion node's next's previous nil
        delNode.next.previous = nil
        // make deletion node's next the head of linkedlist
        d.head = delNode.next        
    } else if delNode == d.tail {
        // if deletion node is tail node
        // make deletion node's previous the  tail of linkedlist
        d.tail = delNode.previous
        // make deletion node's previous nil
        delNode.previous = nil        
    } else {
        // deleting somewhere in the middle of linkedlist
        // make deletion node's previous' next point to deletion node's next
        delNode.previous.next = delNode.next
        // make deletion node's next's previous to point to deletion node's previous
        delNode.next.previous = delNode.previous
        // make the deletion node pointer fields nil
        delNode.next = nil
        delNode.previous = nil
    }
    // finally decrease size of linkedlist by one and return nil error
    d.size -= 1
    return nil
}

Key takeaways from above code:

• Since we’re taking index as input from user we need to check if index is out of bounds.
• Find the node to be deleted at the index passed.
• If delNode is head of linkedlist:
  • We make deletion node’s next’s previous nil.
  • We make deletion node’s next the head of linkedlist.
• If delNode is tail of linkedlist:
  • We make deletion node’s previous the tail of linkedlist.
  • We make deletion node’s previous nil.
• Deleting somewhere between the linkedlist:
  • We make deletion node’s previous’ next point to deletion node’s next.
  • We make deletion node’s next’s previous to point to deletion node’s previous.
  • We make the deletion node pointer fields(next and previous) nil.
• We finally decrease size of linkedlist by one and return nil error.

Closing words

Above we saw basic operations(Insert, InsertAt, Get and RemoveAt) of a custom Doubly linkedlist that we implemented.

Here’s a link to the whole code at one place.

Here’s how the above gist’s code looks in action:

In the next blog we will see the same operations implemented for a Circular linkedlist.

I hope you enjoyed reading this blog and it added some value.