GO Program to Insert a New Node After the Kth Node in a Given Linked List

A linked list is a linear data structure that consists of a bunch of nodes and each node has two attributes: data and next. Here the Next is a pointer to the next node in the list. There are so many linked list operations that allow us to perform different actions on a linked list. For example, the insertion operation will add a new node to the linked list.

In this program, we will create a singly linked list and add a new node after the Kth node of the list. To accomplish this task, we will find the kth node by traversing through the list till the head become nil. If we found the kth node in the list then update the linked list by adding a new node after the kth node. Let’s see this program in more detail.

How to insert a new node after the Kth node

In this program, we’ll focus our attention on how to add a new node after the kth value node in a given linked list by using GO language.

There is an fmt package which used to import some standard libraries into the program. Use the built-in function fmt.println() to print anything on the screen and fmt.scanln() for reading the data. These functions are defined under the fmt package. So we need to import the “fmt” package to use these functions. After that, open the main function. We are doing the whole program inside the main function, which is the starting point of our program.

Here we use a structure to define a node. Generate linked list by calling the function NewNode that creates nodes by assigning data into its node value and changing the pointer of the node as next node. Now the head is the starting node of the linked list. 

Display all the nodes from the linked list by calling the function TraverseLinkedList(head) that traversing a list starts with the head until it finds the reference value as nil.

Now you have a linked list. Whenever you want to add a node after kth node in the given linked list, read the data you want to add as the first node by using fmt.scanln and passing it to the function AddAfterKthNode. This function defines a method that accepts the head of a linked list and input value. Checks, whether the head is equal to nil which means the list is empty. If the head is equal to nil, return the head without adding any node. Otherwise, update the linked list by adding a new node after the kth node. For this, traverse to node just before the required position of a new node. If it found the kth value position then allocate memory and store data for a new node. Change next pointers to include a new node after the kth node in the linked list. Finally, return the head of the linked list to the main function. You can display the updated linked list by calling the function TraverseLinkedList.

Given below are the steps that are used in the Go program to add a new node in a given linked list after the kth node.

ALGORITHM:

STEP 1: Start
STEP 2: Define a structure of the node
STEP 3: Create a linked list by calling the function NewNode(). Here the head is the start node of the linked list.
STEP 4: Display input linked list by Calling the function TraverseLinkedList(head).
STEP 5: Read the new data which you want to insert into the linked list as an item
STEP 6: Add the new node after the kth node of the linked list by calling head = AddAfterKthNode(head, 10, item)
STEP 7: Display the updated linked list by calling the function TraverseLinkedList(head).
STEP 8: Exit

Steps to Implement NewNode(value int):

STEP 1: Declare the variable n as Node.
STEP 2: Create node n by assigning data into its node value and changing the pointer of the node as the next node. 
STEP 3: Return node n

Steps to Implement TraverseLinkedList(head *Node):

STEP 1: Display all the nodes from the linked list by traversing a list that starts with the head until we find the reference value is nil.

Steps to Implement AddAfterKthNode(head *Node, k, data int):

STEP 1: Define a method that accepts the head of a linked list.
STEP 2: Checks, whether the head is equal to null which means the list is empty. If head == nil, return the head without adding any node. Otherwise do step 3
STEP 3: Define a node temp which will initially point to the head of the list.
STEP 4: Traverse through the list till temp points to nil.
STEP 5: In each iteration, check whether temp will point to the kth value node. If so, do the following steps

  • Define new node ptr
  • The new node ptr will be inserted after the kth node such that temp will point to the new node ptr and the ptr will point to temp.

STEP 6: Return head.
 

GO Source Code

                                          package main
import (
   "fmt"
)
type Node struct {
   value int
   next *Node
}
func NewNode(value int, next *Node) *Node{
   var n Node
   n.value = value
   n.next = next
   return &n
}
func TraverseLinkedList(head *Node){
   temp := head
   for temp != nil {
      fmt.Printf("%d ", temp.value)
      temp = temp.next
   }
   fmt.Println()
}
func AddAfterKthNode(head *Node, k , data int) *Node{
  if head == nil{
      return head
   }
   temp := head
   for temp != nil{
      if temp.value == k{
         ptr := NewNode(data, nil)
         ptr.next = temp.next
         temp.next = ptr
         break
      }
      temp = temp.next
   }
   return head
}
func main(){
   head := NewNode(30, NewNode(10, NewNode(80, NewNode(40, nil))))
   fmt.Printf("Input Linked list is: ")
   TraverseLinkedList(head)
   var item int;
   fmt.Printf ("\nEnter the item which you want to insert?\n") 
   fmt.Scan(&item;)

   head = AddAfterKthNode(head, 10, item)
   fmt.Printf("Updated Linked List by Inserting New Node After %dth Value Node:\n", 10)
   TraverseLinkedList(head)
}

                                      

OUTPUT

Input Linked list is: 30 10 80 40 

Enter the item which you want to insert?
75
Updated Linked List by Inserting New Node After 10th Value Node:
 30 10 75 80 40