Implementing Singly Linkedlist using Golang

Introduction

In the last post I introduced Linkedlists and their basic concepts. In this blog we’ll see how to implement Singly Linkedlists in Golang.

Singly Linkedlist

In this type of linkedlist each node points only to the next node in sequence. The tail of a Singly linkedlist always points to a null node.

Implementing Singly Linkedlist

A linkedlist is a sequence of nodes pointing to the next node in that sequence.

So, inorder to implement a linkedlist we first need to define what a node will be.

A node can look like this:

type Node struct{
    data int
    next *Node
}

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

Since a linkedlist is a sequence of nodes, we need the pointer to first node. Using the first node we can traverse the whole linkedlist by using the next pointers.

Hence a Singly Linkedlist can look like this:

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

size is not mandatory in a linkedlist, its good to have. size makes it easier to keep track of size of linkedlist.

Insertion in a linkedlist(at the end of linkedlist)

Insertion in a linkedlist can be under two conditions:

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

We will write a function which takes care of both these conditions.

// Insert a node to the end of linkedlist
func (s *SinglyLinkedList) Insert(newNode *Node){
    if s.size == 0{
        // when linkedlist is empty we make the newNode the head and tail of the linkedlist, as it is the only node in linkedlist
        s.head = newNode
        s.tail = newNode
    }else{
        // if linkedlist is not empty then we first point the tail's next to the newNode
        s.tail.next = newNode
        // then we make the newNode the tail of our linkedlist
        s.tail = newNode
    }
    // after any of these conditions execute we increase the size of linkedlist by 1
    s.size += 1
}

Takeaways from above code:

• I have used SinglyLinkedList as a receiver to the function. It’s not mandatory to do that, but when you’re writing some functionality based over a struct its good to use it as a reciever, as it helps with writing clean code. I will follow the same convention for rest of the implementations as well.
• When the linkedlist is empty:
  • We make the newNode both the head and tail of the linkedlist. Since newNode is curently the only node in our linkedlist it represents both the head and tail of linkedlist.
• When linkedlist has one or more nodes then:
  • We first make the newNode the next pointer of current tail.
  • Then we make newNode the tail of linkedlist.
• Finally increase the 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 (s *SinglyLinkedList) isInRange(index int) bool{
    return index >= 0 && index <= s.size
}

// InserAt the passed index
func (s *SinglyLinkedList) InsertAt(index int, newNode *Node) error{
    // checking if index is out of bounds
    if !s.isInRange(index){
        // return error if index out of bounds
        return errors.New("Index out of bounds")
    }
    // if index is equal to size of linkedlist then we need to insert at the end of linkedlist.
    if index == s.size{
        // using the function we wrote above to insert at the end of linkedlist
        s.Insert(newNode)
        return nil
    }

    node := s.head
    var previousNode *Node
    // getting the previousNode of the index at which newNode is to be inserted.
    for i := 0; i != index;i,node = i+1,node.next{
        previousNode = node
    }
    // node is pointing to head of linkedlist then we need to maker the newNode head of linkedlist
    if node = s.head{
        newNode.next = node
        s.head = newNode
    }else{
        // this condition executes when we're inserting in middle of linkedlist
        // we point the next of newNode to the next of previousNode
        newNode.next = previousNode.next
        // then we point previousNode's next to the newNode
        previousNode.next = newNode
    }
    // after any of these conditions execute we increase the size of linkedlist by 1
    s.size += 1
    return nil
}

Takeaways from above code:

• Since we’re inserting at a given index we need to check if that index is valid wrt our linkedlist.
• If insertion index is the size of linkedlist then we know that we need to insert at the end of linkedlist. Since we had already written code to insert at the end(insert function) of linkedlist we can use that directly.
• If insertion index is not the last of linkedlist, then we need to find the previous and next node of the index at which we will insert.
• After finding that index we check if the insertion is to happen at the front of linkedlist.
• If yes then we make the newNode’s next to point to current head of linkedlist and then make the newNode head of linkedlist.
• Otherwise we’re inserting somewhere in between the linkedlist. For this we point newNode’s next to previousNode’s next and then previousNode’s next becomes the newNode.
• Increase size of linkedlist at the last.

Getting value from a linkedlist

We can write a simple function to get the value from a 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.

// Get the data at passed index
func (s *SinglyLinkedList) Get(index int) (int,error){
    // check if index is out of bounds
    if !s.isInRange(index){
        // return error if index out of bounds        
        return -1, errors.New("Index out of bounds")
    }
    // check if list is un-initialized
    if s.head == nil && s.tail == nil{
        return -1, errors.New("not initialized")
    }
    // iterate till the index node
    node:=s.head
    for i := 0; i != index; i, node = i+1,node.next{        
    }
    // return data at the index node.
    return node.data,nil
}

Takeaways from above code:

• Since we’re using index to get the value, we need to check if that index is valid wrt our linkedlist.
• We also need to check if the linkedlist is initialized.
• Iterate till the index and return value at index node.

Deletion in 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 previousNode of deletion index and 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.

// RemoveAt removes a node at given index
func (s *SinglyLinkedList) RemoveAt(index int) error{
    // check if index is out of bounds
    if !s.isInRange(index){
        // return error if index out of bounds        
        return errors.New("Index out of bounds")
    }
    // find previousNode and deletion node
    node := s.head
    var previousNode *Node
    for i := 0; i != index; i, node = i+1, node.next{
        previousNode=node
    }
    // at this point node will contain deletion node and as the name suggests previousNode will be node prevoius to deletion node
    // if deletion node is head node
    if node == s.head{
        // if linkedlist has only one element
        if s.size == 1{
            // empty the linkedlist
            s.head = nil
            s.tail = nil
            s.size -= 1
            return nil
        }
        // else make node.next the head of linkedlist
        s.head = node.next
    }

    // if deletion node is the tail node
    if node == s.tail{
        // make the previousNode tail of linkedlist
        s.tail = previousNode        
    }
    // previousNode found is not nil
    if previousNode != nil{
        // point previousNode's next to deletion node's next
        previousNode.next = node.next        
    }
    // make the deletion node nil
    node = nil
    // reduce size of linkedlist
    s.size -= 1
    return nil
}

Takeaways from above code:

• Since we’re using index to get the value, we need to check if that index is valid wrt our linkedlist.
• We try to find the previous and deletion nodes wrt to passed index.
• If deletion node is head of linkedlist and linkedlist has only one node then empty the linkedlist. Else make deletion node’s next as the head of linkedlist.
• If deletion node is tail of linkedlist then make the previous node as the tail of linkedlist
• If the previousNode is not nil then point previousNode’s next to deletion node’s next.
• Reduce size of linkedlist at the last.

Closing words

Above we saw basic operations(insert, insertAt, Get and RemoveAt) of a custom linkedlist that we implemented.

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

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

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