Circular Linked List – Insertion

Circular Linked List - Insertion

Meta Description: Learn the most efficient way to insert a node in a circular linked list.

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this article, we are going to learn about the insertion operations in a circular linked list. In a circular linked list, the last node doesn’t point to NULL. Instead, it points to the first node, forming a circle.

There are four main insertion operations:

  • Insert at the beginning of the list
  • Insert at the end of the list.
  • Insert in an empty list.
  • Insert in between the nodes.

Let's have a glance at the approaches and algorithms for the above four insertion operations.

Approach (Insert at the beginning)

While inserting at the beginning in a circular linked list, we have to keep in mind that the last node always points to the head node.

If we keep the above point in mind, we can say that firstly, we will make the new node point to the head node. Now, as we know that the last should point to the first node of the list, so we will make the last node point to the new node. In this way, the last node will point to the newly created node, and the newly created node will point to the head. Now, the newly created node will become the head.

Algorithm

  • Create the node which is to be inserted, say NewNode.
  • Do NewNode - > next = last - > next. This step ensures that the current node is being added at the beginning of the list, as the next of the last node is always the head of the list. The NewNode will become the head.
  • As it is a circular linked list, the last will now point to the new node, so last - > next = NewNode. By doing this, the last node will now point to the newly created node, which is our new head. In this way, the tail is being updated.

Function Implementation



struct Node *addBegin(struct Node *last, int data)
{
    if (last == NULL)
        return addToEmpty(last, data);

    struct Node *NewNode =
            (struct Node *)malloc(sizeof(struct Node));

    NewNode -> data = data;
    NewNode -> next = last -> next;
    last -> next = NewNode;

    return last;
}

Approach (Insert at the end)

While inserting at the end in a circular linked list, we have to keep in mind that the last node always points to the head node.

If we keep the above point in mind, we can say that firstly, we will make the new node point to the next of the last node. After doing this, we will make the last node point to the new node. In the end, the new node will become the last node.

Algorithm

  • Create the node which is to be inserted, say NewNode.
  • Make the new node point to the next of the last node NewNode - > next = last - > next.
  • Make the last node point to the new node last - > next = NewNode. By doing this, the last node, instead of pointing to the head node, will point to the new node.
  • In the end, the NewNode will become the last node. In this way, the tail is being updated.

Function Implementation


struct Node *addEnd(struct Node *last, int data)
{
    if (last == NULL)
        return addToEmpty(last, data);
    
    struct Node *NewNode =
        (struct Node *)malloc(sizeof(struct Node));

    NewNode -> data = data;
    NewNode -> next = last -> next;
    last -> next = NewNode;
    last = NewNode;

    return last;
}

Approach (Insert in an empty list)

While inserting in an empty list, we have to keep in mind that the last node will be NULL initially.

If we keep the above point in mind, we can say that firstly, we will allocate memory for the new node. Now, the new node will become the new tail. As there is only a singly node, so this new node is the tail as well as the head of the list. So, the new node will point to itself. In this way, we can update the head and tail, and insert in an empty list.

Algorithm

  • Create the node which is to be inserted, say NewNode.
  • Make the new node the last node last = NewNode.
  • As it is the only node in the list, it will be the tail as well as head.
  • Keeping the above point in mind, we will make the NewNode point to the last(itself) NewNode - > next = last.
  • By performing the above steps, the head and tail are being updated, as well as the NewNode is being added to the empty list.

Function Implementation


struct Node *addToEmpty(struct Node *last, int data)
{
    if (last != NULL)
    return last;

    struct Node *NewNode =
        (struct Node*)malloc(sizeof(struct Node));

    NewNode -> data = data;
    last = NewNode;

    last -> next = last;

    return last;
}

Approach (Insert in between the nodes)

In this approach, we will be given a node’s data. We will have to insert the new node just after this given node.

To achieve this, we will first create the node which is to be inserted, say NewNode, then we will simply traverse the list till we find the the node with the given data. Let the node that is found is P. So, to insert this New Node just after P, we will simply do NewNode - > next = P -> next. After this, make P point to this NewNode. By doing this, we are successfully inserting the new node after a given node.

Algorithm

  • Create the node which is to be inserted, say NewNode.
  • Traverse through the list till the node with the given data is not found.
  • Store the node in P.
  • Make the next of NewNode point to the next of P, NewNode - > next = P - > next
  • Make P point to the NewNode P - > next = NewNode.

Function Implementation


struct Node *addAfter(struct Node *last, int data, int item)
{
    if (last == NULL)
        return NULL;
 
    struct Node *temp, *P;
    P = last -> next;
    do
    {
        if (P ->data == item)
        {
            temp = (struct Node *)malloc(sizeof(struct Node));
            temp -> data = data;
            temp -> next = P -> next;
            P -> next = temp;
 
            if (P == last)
                last = temp;
            return last;
        }
        P = P -> next;
    }  while(P != last -> next);
 
    cout << item << " not present in the list." << endl;
    return last;
 
}

Dry Run


Code Implementation


#include
using namespace std;

struct Node
{
    int data;
    struct Node *next;
};

struct Node *addToEmpty(struct Node *last, int data)
{
    if (last != NULL)
    return last;

    struct Node *NewNode =
        (struct Node*)malloc(sizeof(struct Node));

    NewNode -> data = data;
    last = NewNode;

    last -> next = last;

    return last;
}

struct Node *addBegin(struct Node *last, int data)
{
    if (last == NULL)
        return addToEmpty(last, data);

    struct Node *NewNode =
            (struct Node *)malloc(sizeof(struct Node));

    NewNode -> data = data;
    NewNode -> next = last -> next;
    last -> next = NewNode;

    return last;
}

struct Node *addEnd(struct Node *last, int data)
{
    if (last == NULL)
        return addToEmpty(last, data);
    
    struct Node *NewNode =
        (struct Node *)malloc(sizeof(struct Node));

    NewNode -> data = data;
    NewNode -> next = last -> next;
    last -> next = NewNode;
    last = NewNode;

    return last;
}

struct Node *addAfter(struct Node *last, int data, int item)
{
    if (last == NULL)
        return NULL;
 
    struct Node *temp, *p;
    p = last -> next;
    do
    {
        if (p ->data == item)
        {
            temp = (struct Node *)malloc(sizeof(struct Node));
            temp -> data = data;
            temp -> next = p -> next;
            p -> next = temp;
 
            if (p == last)
                last = temp;
            return last;
        }
        p = p -> next;
    }  while(p != last -> next);
 
    cout << item << " not present in the list." << endl;
    return last;
 
}


void traverse(struct Node *last)
{
    struct Node *p;

    if (last == NULL)
    {
        cout << "List is empty." << endl;
        return;
    }

    p = last -> next;

    do
    {
        cout << p -> data << " ";
        p = p -> next;

    }
    while(p != last->next);

}

int main()
{
    struct Node *last = NULL;

    last = addToEmpty(last, 2);
    last = addBegin(last, 1);
    last = addEnd(last, 3);
    
    last=addAfter(last,4,2);

    traverse(last);

    return 0;
}


public class PrepBytes
{

static class Node
{
    int data;
    Node next;
};

static Node addToEmpty(Node last, int data)
{

    if (last != null)
    return last;

    Node temp = new Node();

    temp.data = data;
    last = temp;


    last.next = last;

    return last;
}

static Node addBegin(Node last, int data)
{
    if (last == null)
        return addToEmpty(last, data);

    Node temp = new Node();

    temp.data = data;
    temp.next = last.next;
    last.next = temp;

    return last;
}

static Node addEnd(Node last, int data)
{
    if (last == null)
        return addToEmpty(last, data);
    
    Node temp = new Node();

    temp.data = data;
    temp.next = last.next;
    last.next = temp;
    last = temp;

    return last;
}

static Node addAfter(Node last, int data, int item)
{
    if (last == null)
        return null;
 
    Node temp, p;
    p = last.next;
    do
    {
        if (p.data == item)
        {
            temp = new Node();
            temp.data = data;
            temp.next = p.next;
            p.next = temp;
 
            if (p == last)
                last = temp;
            return last;
        }
        p = p.next;
    } while(p != last.next);
 
    System.out.println(item + " not present in the list.");
    return last;
 
}

static void traverse(Node last)
{
    Node p;

    if (last == null)
    {
        System.out.println("List is empty.");
        return;
    }

    p = last.next;


    do
    {
        System.out.print(p.data + " ");
        p = p.next;

    }
    while(p != last.next);

}


public static void main(String[] args)
{
    Node last = null;

    last = addToEmpty(last, 2);
    last = addBegin(last, 1);
    last = addEnd(last, 3);
    
    last=addAfter(last,4,2);

    traverse(last);
}
}

Output
1 2 4 3

Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to insert a node in a circular linked list. Inserting nodes at various positions in circular linked list is must to know from coding interviews perspective. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Delete Alternate Nodes Of A Linked List
Next post Remove Nth Node From End Of The Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *