Insertion in Singly Linked List

Introduction

Singly linked list (SLL) is a linked list in which two nodes are connected with a single link in between them. First node stores the address of the second node, second node stores the address of third node and so on . A node do not store the address of previous node in singly linked list.
The structure of singly linked list is shown in the above diagram.
A node whose address part is null is the end of the list.

To retrieve the whole linked list , we need the address of starting node. It is stored in the pointer called head.  

Operations on linked list  

Following  operations  can be performed on singly linked list .
  1. Insertion : Insertion can be at start , at end or at given position .
  2. Deletion : Deletion can be at start , at end or at given position.
  3. Display
  4.  Reverse a linked list
In this article we are going to discuss  the insertion and display . In next article we will see deletion and reversing the linked list.

  

   Insertion 

Adding the data element in the list is called as Insertion . 
There are again three cases  of inserting the element  :
Insertion 
i) at start of the linked list
ii)  at a given position
iii) at the end of the linked list  

Let's see all the cases one by one 

i) At start of the linked list
Steps :
 1. Create a new node , newNode.
 2. Link the next of newNode to the head of linked list.  
    newNode->next = head

 3. Now , make head = newNode.

ii) Insertion at a given position
 Steps :
 1. Take the location as input from user (Here location = 3 ) .
 2. Create a new node , name it as newNode.
 3. Traverse the linked list till the one node before the given location , call  that node as prev. 
 4. Make newNode->next = prev->next and prev->next = newNode. (refer diagram below)


 5. The element inserted at given position is shown in diagram below.



iii) Insertion at the end of the linked list (append)
Steps :  
 1. Traverse the list till the last node.
 2. Create a new node and name it as newNode .
 3. Make next pointer of last node points to the newNode.
   temp->next = newNode
  4. And you are done .

  #C++ code for insertion [Start , End , given position]


#include<iostream>

using namespace std;

struct node
{
    int data;

    node *next;
};

node *head;

node *createNode(int value);

void insertStart(int value);

void insertPosition(int value,int pos);

void insertEnd(int value);

void display();

int main()
{
    head =NULL;

    int choise;

    int n,key;

    int location;

    cout<<"\n\t\tOperations on linked list \n";

    do
    {
        cout<<"\n\t\t\t____Menu____\n";

        cout<<"\n\t\t  1.Create a Linked List \n";

        cout<<"\t\t  2.Insert at Start  \n";

        cout<<"\t\t  3.Insert at End \n";

        cout<<"\t\t  4.Insert at a Position \n";

        cout<<"\t\t  5.Display Linked List \n";

        cout<<"\t\t  6.Exit\n";

        cout<<"\t  Yours choise :  ";

        cin>>choise;

        switch(choise)
        {
            case 1:

                    cout<<"How many nodes do you want to add ?  ";

                    cin>>n;

                    for(int i=0;i<n;i++)
                    {

                        cout<<"Enter the data :";

                        cin>>key;

                        insertEnd(key);

                    }
            break;
            case 2:

                    cout<<"Enter the data : ";

                        cin>>key;

                        insertStart(key);

            break;

            case 3:
                    cout<<"Enter the data :  ";

                    cin>>key;

                    insertEnd(key);

            break;
            case 4:
                    if(head==NULL)

                        cout<<"\t\tSorry! Linked List is Empty!\n";

                    else
                    {
                        cout<<"Enter the position :  ";

                        cin>>location;

                        cout<<"Enter the data :  ";

                            cin>>key;

                            insertPosition(key,location);
 
                    }

            break;

            case 5:

                    display();

            break;
        }

    }while(choise<6);
}


node *createNode(int value)
{
    node *n = new node;

    n->data = value;

    n->next = NULL;

    return n;
}

void insertStart(int value)
{
    node *newNode;

    newNode = createNode(value);

    if(head==NULL)
    {
        head = newNode;
    }
else
    {
        newNode->next = head;

        head = newNode;
    }
        cout<<"\nNode inserted succesfully at begining "<<endl;

}

void insertPosition(int value,int pos)
{
    node *newNode =createNode(value);

    node *prev = head;

    int i=1;

        while(prev!=NULL)
        {
            if((pos-1)==i)

                break;
            else
            {
                prev = prev->next;

                i++;
            }
        }
        newNode->next = prev->next;

        prev->next = newNode;

        cout<<"\nNode inserted succesfully at position :"<<pos<<endl;
  
}

void insertEnd(int value)
{
    node *newNode = createNode(value);

    node *temp = head;

    if(head==NULL)
    {
        head = newNode;
    }
    else
    {
      
        while(temp->next!=NULL)
        {
            temp = temp->next;
        }
        temp->next= newNode;
    }
  
    cout<<"Node inserted succesfully at End \n"<<endl;

}

void display()
{
    node *temp = head;

    int count =0;

    cout<<"Displaying the elements of linked list :\n";

    while(temp!=NULL)
    {
        cout<<"\t"<<temp->data<<"\n";

        temp=temp->next;

        count++;
    }
    cout<<"Node count : "<<count<<endl;
}

Download the Code here
Note :  This code is successfully compiled and run under Linux distribution Ubuntu 18.04 LTS environment . 

Output :
            Operations on linked list

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  1
How many nodes do you want to add ?  4
Enter the data :10
Node inserted succesfully at End

Enter the data :20
Node inserted succesfully at End

Enter the data :30
Node inserted succesfully at End

Enter the data :40
Node inserted succesfully at End


            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  5
Displaying the elements of linked list :
    10
    20
    30
    40
Node count : 4

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  2
Enter the data :5

Node inserted succesfully at begining

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  5
Displaying the elements of linked list :
    5
    10
    20
    30
    40
Node count : 5

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  3
Enter the data :100
Node inserted succesfully at End


            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  5
Displaying the elements of linked list :
    5
    10
    20
    30
    40
    100
Node count : 6

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  4
Enter the position : 4
Enter the data :400

Node inserted succesfully at position :4

            ____Menu____

        1.Create a Linked List
        2.Insert at Start 
        3.Insert at End
        4.Insert at a Position
        5.Display Linked List
        6.Exit
    Yours choise :  5
Displaying the elements of linked list :
    5
    10
    20
    400
    30
    40
    100
Node count : 7

Conclusion : 

Singly Linked List (SLL) is successfully created . Nodes are inserted according to the cases at beginning , end and at a given position in singly linked list .