Implementing Circular Linkedlist using Golang

Introduction

In a Circular linkedlist each node points to the next node sequence, except the tail points to the head of linkedlist. Circular linkedlist behaves like a Singly Linkedlist, except for the tail’s next pointing to null, it points to the head.

Implementing Circular Linkedlist

As mentioned above a Circular linkedlist behaves just like a Singly Linkedlist except for it’s tail pointing to head rather than to a null node.

Insert, InsertAt, Get and Remove operations would be very similar to a Singly Linkedlist.

type Node struct{
    data int
    next *Node
}

data can be of any datatype(string, double, struct, etc) available in Go.

The wrapper struct for a Circular Linkedlist would look like this:

type CircularLinkedlist struct{
    head *Node
    tail *Node
    size int
}

Insertion in a Circular 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 (c *CircularLinkedlist) Insert(newNode *Node) {
    // checking if linkedlist is empty
    if c.size == 0 && c.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
        c.head = newNode
        c.tail = newNode
    } else {
        // while inserting at the end
        // make current tail's next point to newNode
        c.tail.next = newNode
        // make newNode the tail of linkedlist
        c.tail = newNode
        // make new tail's next point to head of linkedlist
        c.tail.next = c.head
    }
    // finally increase size of linkedlist by one
    c.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:
  • We make current tail’s next point to newNode.
  • We make newNode the tail of linkedlist.
  • We make new tail’s next point to head of linkedlist.
• Finally 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 (c *CircularLinkedlist) isInRange(index int) bool{
    return index >= 0 && index <= c.size
}

func (c *CircularLinkedlist) InsertAt(index int, newNode *Node) error {
    // checking if index is out of bounds.
    if !c.isInRange(index) {
        return errors.New("Index out of bounds")
    }
    // insertion at the start of linkedlist
    if index == 0 {
        // make newNode's next to point to current head of linkedlist
        newNode.next = c.head
        // make newNode head of linkedlist
        c.head = newNode
        // make tail's next point to the new head of linkedlist
        c.tail.next = c.head
        // increase size by one
        c.size += 1
        // return nil error
        return nil
    }
    // insertion at last of linkedlist
    if index == c.size {
        // make current tail's next point to newNode
        c.tail.next = newNode
        // make newNode tail of linkedlist
        c.tail = newNode
        // make new tail to point to head of inkedlist
        c.tail.next = c.head
        // increase size by one
        c.size += 1
        // return nil error
        return nil
    }

    // inserting somewhere in middle
    // finding previousNode for the given insertion index
    currNode := c.head
    var previousNode *Node
    for i := 0; i != index; i, currNode = i+1, currNode.next {
        previousNode = currNode
    }
    // make newNode's next point to previousNode's next
    newNode.next = previousNode.next
    // make previousNode's next to point to newNode
    previousNode.next = newNode
    // increase size by one
    c.size += 1
    // return nil error
    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.
• If insertion is at start of Circular linkedlist:
  • We make newNode’s next to point to current head of linkedlist.
  • We make newNode head of linkedlist.
  • We make tail’s next point to the new head of linkedlist.
  • Increase size by one.
  • Return nil error.
• If insertion is at end of Circular linkedlist:
  • We make current tail’s next point to newNode.
  • We make newNode tail of linkedlist.
  • We make new tail to point to head of inkedlist.
  • Increase size by one.
  • Return nil error.
• If insertion is anywhere else:
  • We find previousNode for the given insertion index.
  • We make newNode’s next point to previousNode’s next.
  • We make previousNode’s next to point to newNode.
  • Increase size by one.
  • Return nil error.

Getting value from a Circular linkedlist

We can write a simple function to get the value from a circular 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 (c *CircularLinkedlist) Get(index int) (int, error) {
    // checking if index is out of bounds of linkedlist
    if !c.isInRange(index) {
        return -1, errors.New("Index out of bounds")
    }
    // find the node at the passed index
    currNode := c.head
    for i := 0; i != index; i, currNode = i+1, currNode.next {        
    }
    // return data at passed index and nil error
    return currNode.data, nil
}

Key takeaways from abovr code:

• Since we’re taking index as input from user we need to check if index is out of bounds.
• We find the node at the passed index by iterating over the linkedlist.
• We return the data at the node found at the passed index and return nil error.

Deletion in Circular 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 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 (c *CircularLinkedlist) RemoveAt(index int) error {
    // checking if index is out of bounds of linkedlist
    if !c.isInRange(index) {
        return errors.New("Index out of bounds")
    }
    // find previous node of the given index
    currNode := c.head
    var previousNode *Node
    for i := 0; i != index; i, currNode = i+1, currNode.next {
        previousNode = currNode
    }
    if currNode == c.head {
        // if deletion node is head of linkedlist
        // make head of linkedlist to point to currNode's next
        c.head = currNode.next
        // make tail's next to point to new head
        c.tail.next = c.head
    } else if currNode == c.tail {
        // if deletion node is tail of linkedlist
        // make previousNode the tail of linkedlist
        c.tail = previousNode
        // make new tail's next to point to head of linkedlist
        c.tail.next = c.head
    } else {
        // deleting anywhere else in the linkedlist
        // make previousNode's next to point to currNode's next
        previousNode.next = currNode.next
    }
    // finally decrease size by one and return nil error
    c.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 previousNode as per the passed index’s node.
• If deletion is at start of linkedlist:
  • We make head of linkedlist to point to currNode’s next.
  • We make tail’s next to point to new head.
• If deletion is at end of linkedlist:
  • We make previousNode the tail of linkedlist.
  • We make new tail’s next to point to head of linkedlist.
• Deletion anywhere else:
  • We make previousNode’s next to point to currNode’s next.
• 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 Circular 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:

The next blog series will be on how to implement a queue using Golang.

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