Circular Linked List

Linked List: Linked list is data structure in which allocated memory is divided into two parts, one stores the data and another stores the address of next element.

When the first and last element of linked list is connected, it is called as Circular Linked List.

Let us have a look on it’s implementation:

1. We declare a structure which is having a data of integer type and a pointer of structure type which is used to store address of next elements. And having a global pointer variable which always stores the address of first node(head) in linked list.
2. We use a Create Function which is used to create a list and the list nodes store both data and address.
3. We linked the elements in such a way that every Node stores data and address of next node and the now the last element of list is not pointing to NULL, as it now stores address of first node(head).
4. To insert a node at any position we declare a new node and store the data in it, and iterate till pos-1 and now this node point to new node and the new node point to the next node. (there are some edge cases like inserting at beginning, which you may understand with the code).
5. To delete a node from given position, you do same, iterate till pos-1 and point this node to the next node of current node and now delete the current node.
6. To display elements we just iterate through the list using the address of first node(head).

Here’s a C++ Implementation of the Circular Linked List:

---

#include <iostream>
using namespace std;
struct Node // Declaring a Node structure 
{
    int data;
    Node *next;
};
Node *head; // Declare a head node which always point to the first element of list
void create(int A[], int n) // here create a list 
{
    int i;
    Node *last, *t;
    head = new Node;
    head->data = A[0];
    head->next = head;
    last = head;
    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = last->next;
        last->next = t;
        last = t;
    }
}
void insert(int x, int pos) // Inserting a element at given position
{
    Node *t, *p = head;
    if (pos == 0)
    {
        t = new Node;
        t->data = x;
        t->next = head;
        while (p->next != head)
        {
            p = p->next;
        }
        p->next = t;
        t = head;
    }
    else
    {
        t = new Node;
        t->data = x;
        for (int i = 1; i < pos - 1; i++)
        {
            p = p->next;
        }
        // p->next=t;
        t->next = p->next;
        p->next = t;
    }
}
void Delete(Node *h, int pos) // delete a node from a given position
{
    if (pos == 1)
    {
        while (h->next != head)
        {
            h = h->next;
        }
        h->next = head->next;
        free(head);
        head = h->next;
    }
    else
    {
        for (int i = 0; i < pos - 2; i++)
        {
            h = h->next;
        }
        Node *q;
        q = h->next;
        h->next = q->next;
        delete q;
    }
}
void recurrdisplay(Node *h) // display function using recurrsion
{
    static int flag = 0;
    if (h != head || flag == 0)
    {
        flag = 1;
        cout << h->data << " ";
        recurrdisplay(h->next);
    }
}
void Display(Node *h) // display function using iteration
{
    while (h->next != head)
    {
        cout << h->data << " ";
        h = h->next;
    }
    cout << h->data << " ";
    // also we can use do while loop
}
int main()
{
    int A[] = {2, 4, 6, 8, 7};
    create(A, 5);
    recurrdisplay(head); cout<<"\n";
    cout << "Now Linked list"
         << "\n";
    Display(head); 
    cout << "\n";
    insert(4, 3);
    cout << "Now Linked list"
         << "\n";
    Display(head);
    cout << "\n";
    Delete(head, 1);
    cout << "Now Linked list"
         << "\n";
    Display(head);
    cout << "\n";
    Delete(head, 4);
    cout << "Now Linked list"
         << "\n";
    Display(head);
}

Time complexity analysis:

a. Inserting a node

O(pos): depends on the position where to insert.(except Inserting at beginning takes constant time).

b. Deleting a node

O(pos): position of the element to be deleted. (except Deleting at beginning takes constant time).

This Article was Exclusively written by Amit Singh Bisht | LinkedIn

Read Next: Functions, Prototypes & Recursion in C++