Circular Linked List


In a circular linked list elements can be inserted from anywhere. In a circular linked list the last node has the address or it points towards the head node of the list. The elements point to each other in such a way through which a chain is formed. Memory for circular linked list can be allocated when required as a circular linked list has a dynamic size.

dynamic size


Application of circular linked list:

A circular linked list can be used to implement circular queue. It is also used in personal computers in which multiple applications are running. The circular linked list is used in this to keep the application in it and the operating system allots time to each application for running.


Implementing circular linked List:

A circular linked list can be implemented very easily as it is the same just like a singly linked list. The only difference is that the last node of list is pointed to the head node of the list. In the singly or linear linked list, the last node points to null. Consider the following code in which circular linked list is implemented:

CODE:

class Node {

  public:

  int obj;

  node* next;

  node () {

    obj = 0;

    next = NULL;

  }

  node (int a) {

    obj = a;

    next = NULL;

  }

}


Circular Linked List:

Circular linked can implemented as we implemented a linear linked list but an addition of few more methods. The following is the code in which class for circular linked list is created:

CODE:

class CircularLinkedList {

  public:

  node *head;

  int InsertingAtFront (node *p);

  int isEmpty ();

  int InsertingAtEnd (node *p);

  node* searching (int y);

  node* deletingNode(int a);

  CircularLinkedList () {

    head = NULL;

  }

}


Insertion at the beginning:

Consider the following code to insert an element at the beginning of the circular linked list:

CODE:

int CircularLinkedList :: InsertingAtFront (node *p)

{

  int x = 0;

  if(head == NULL) {

    p -> next = head;

    head = n;

    x ++;

  }

  else {

    p -> next = head;

    Node* last = LastNode();

    last -> next = p;

    head = p;

    x ++;

  }

  return x;

}

In the above code, a node is created first for any linked list and this node has head and null as the pointer. To insert the node at front the head node is made to point to it.


Insertion at the End:

Consider the following code to insert the node at the end of circular linked list:

CODE:

int CircularLinkedList :: InsertingAtEnd (node *p) {

  if (head == NULL) {

    head = p;

    p -> next = NULL;

  }

  else {

    node *last = LastNode();

    last -> next = p;

    p -> next = head;

  }

}

In the above code, if the linked list is empty then we will make the new node as the head node of the linked list. And if the linked list is not empty, then the last node is found and we will make the new node to be next of last node in this way new node will be the last node and we will make this last node to point towards the head node.


Searching for an element in list:

To search an element in the list, we will traverse through the list and will compare the data in the list with the element to be found. If node is found, it will be returned. If node is not found, pointer will point to the next node. Consider the following code to search for an element in the linked list:

CODE:

node* CircularLinkedList :: searching (int a) {

  node *pointer = head;

  while (pointer != NULL && pointer -> data != a) {

    pointer = pointer -> next;

  }

  return ptr;

}


Deleting a node from list:

Consider the following code to delete the data from the circular linked list:

CODE:

node* CircularLinkedList :: deletingNode (int a) {

  node *p = searching (a);

  node *pointer = head;

  if(pointer == NULL) {

cout << “Circular linked list is empty”;

    return NULL;

  }

  else {

    while(pointer -> next != p) {

      pointer = pointer -> next;

    }

    pointer -> next = p -> next;

    return p;

  }

}

In the above code first we searched for the node which has the same data as ‘a’. If the first node is the one to be deleted then the next node will be set as head node.