C program to insert a node in Circular Linked List

Write a program to create a circular linked list and insert a new node at the beginning or at any position in the given list. How to insert a new node at the beginning of a circular linked list in C. How to insert a new node at any position in a circular linked list in C.
Insertion of new node in a Circular linked list


Required knowledge

Basic C programming, Dynamic memory allocation, Circular linked list

Algorithm to insert a new node at the beginning of a Circular linked list

For inserting new node at the beginning of a circular linked list. We need to connect new node with the first node and re-connect the last node with new node instead of head node.
Algorithm to insert new node at the beginning of Circular linked list
%%Input : head {Pointer to first node of the linked list}
Begin
    If (head == NULL) then
        write ('List is empty')
    End if
    Else then
        alloc (newNode)
        read (data)
        newNode.datadata;
        newNode.nexthead;

        currenthead;
        While (current.next != head) do
            currentcurrent.next;
        End while
        current.nextnewNode;
    End if
End


Algorithm to insert new node at the any position in Circular linked list

Algorithm to insert new node at any position of a circular linked list
%%Input : head {Pointer to first node of the list}
        N {Position where to insert}
Begin
    If (head == NULL) then
        write ('List is empty')
    End if
    Else if (N == 1) then
        insertAtBeginning()
    End if
    Else then
        alloc (newNode)
        read (data)
        newNode.datadata;
        
        currenthead;
        For count ← 2 to N-1 do
            currentcurrent.next;
        End for
        newNode.nextcurrent.next;
        current.nextnewNode;
    End if
End


Steps to insert new node in a Circular linked list

Suppose we want to insert a new node in the circular linked list at 3 position i.e. just after 2nd position. The list initially contains 3 nodes. We will follow below steps to insert node at 2nd position in the list.
Create a newNode and assign some data to its data field.
Insertion of new node in Circular linked list step 1
Traverse to N-1 position in the list, in our case since we want to insert node at 3rd position therefore we would traverse to 3-1 = 2nd position in the list. Say current pointer points to N-1th node.
Insertion of new node in a circular linked list step 2
Link the next pointer field of newNode with the node pointed by the next pointer field of current(N-1) node. Which means newNode.next = current.next.
Insertion of new node in a circular linked list step 3
Connect the next pointer field of current node with the newly created node which means now next pointer field of current node will point to newNode. And you are done now.
Insertion of new node in a circular linked list step 4


Insertion of new node in a circular linked list step 5


Program

/**
 * C program to insert a new node in a Circular Linked List
 */

#include <stdio.h>
#include <stdlib.h>


/*
 * Basic structure of Node
 */
struct node {
    int data;
    struct node * next;
}*head;



/*
 * Functions used in this program
 */
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtN(int data, int position);




int main()
{
    int n, data, choice=1;

    head = NULL;

    /*
     * Runs forever until user chooses 0
     */
    while(choice != 0)
    {
        printf("============================================\n");
        printf("CIRCULAR LINKED LIST PROGRAM\n");
        printf("============================================\n");
        printf("1. Create List\n");
        printf("2. Display list\n");
        printf("3. Insert at beginning\n");
        printf("4. Insert at any position\n");
        printf("0. Exit\n");
        printf("--------------------------------------------\n");
        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch(choice)
        {
            case 1:
                printf("Enter the total number of nodes in list: ");
                scanf("%d", &n);
                createList(n);
                break;
            case 2:
                displayList();
                break;
            case 3:
                printf("Enter data to be inserted at beginning: ");
                scanf("%d", &data);
                insertAtBeginning(data);
                break;
            case 4:
                printf("Enter node position: ");
                scanf("%d", &n);
                printf("Enter data you want to insert at %d position: ", n);
                scanf("%d", &data);
                insertAtN(data, n);
                break;
            case 0:
                break;
            default:
                printf("Error! Invalid choice. Please choose between 0-4");
        }

        printf("\n\n\n\n\n");
    }

    return 0;
}



/**
 * Creates a circular linked list of n nodes.
 *
 * @n Number of nodes to be created
 */
void createList(int n)
{
    int i, data;
    struct node *prevNode, *newNode;

    if(n >= 1)
    {
        /*
         * Creates and links the head node
         */
        head = (struct node *)malloc(sizeof(struct node));

        printf("Enter data of 1 node: ");
        scanf("%d", &data);

        head->data = data;
        head->next = NULL;

        prevNode = head;

        /*
         * Creates and links rest of the n-1 nodes
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            printf("Enter data of %d node: ", i);
            scanf("%d", &data);

            newNode->data = data;
            newNode->next = NULL;

            //Links the previous node with newly created node
            prevNode->next = newNode;
            //Moves the previous node ahead
            prevNode = newNode;
        }

        //Links the last node with first node
        prevNode->next = head;

        printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
    }
}



/**
 * Displays the content of the list
 */
void displayList()
{
    struct node *current;
    int n = 1;

    if(head == NULL)
    {
        printf("List is empty.\n");
    }
    else
    {
        current = head;
        printf("DATA IN THE LIST:\n");

        do {
            printf("Data %d = %d\n", n, current->data);

            current = current->next;
            n++;
        }while(current != head);
    }
}



/**
 * Inserts a new node at the beginning of the list
 *
 * @data Data of the first node
 */
void insertAtBeginning(int data)
{
    struct node *newNode, *current;

    if(head == NULL)
    {
        printf("List is empty\n");
    }
    else
    {
        /*
         * Creates new node, assign data and links it to head
         */
        newNode = (struct node *)malloc(sizeof(struct node));
        newNode->data = data;
        newNode->next = head;

        /*
         * Traverses to last node and links last node
         * with first node which is new node
         */
        current = head;
        while(current->next != head)
        {
            current = current->next;
        }
        current->next = newNode;

        /*Makes new node as head node*/
        head = newNode;

        printf("NODE INSERTED SUCCESSFULLY\n");
    }
}



/**
 * Inserts a new node at any position in the list
 *
 * @data Data of the new node
 * @position Position where to insert new node
 */
void insertAtN(int data, int position)
{
    struct node *newNode, *current;
    int i;

    if(head == NULL)
    {
        printf("List is empty.\n");
    }
    else if(position == 1)
    {
        insertAtBeginning(data);
    }
    else
    {
        /*
         * Creates new node and assign data to it
         */
        newNode = (struct node *)malloc(sizeof(struct node));
        newNode->data = data;

        /*
         * Traverse to n-1 node
         */
        current = head;
        for(i=2; i<=position-1; i++)
        {
            current = current->next;
        }

        /* Links new node with node ahead of it and previous to it*/
        newNode->next = current->next;
        current->next = newNode;

        printf("NODE INSERTED SUCCESSFULLY.\n");
    }
} 


Output
============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 1
Enter the total number of nodes in list: 2
Enter data of 1 node: 20
Enter data of 2 node: 40

CIRCULAR LINKED LIST CREATED SUCCESSFULLY





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 20
Data 2 = 40





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 3
Enter data to be inserted at beginning: 10
NODE INSERTED SUCCESSFULLY





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 40





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 4
Enter node position: 3
Enter data you want to insert at 3 position: 30
NODE INSERTED SUCCESSFULLY.





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 30
Data 4 = 40





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
3. Insert at beginning
4. Insert at any position
0. Exit
--------------------------------------------
Enter your choice : 0



Happy coding ;)
Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment