Implementing a Circular Linked List

To implement a circular linked list, we use a singly linked list and add a note at the end of the linked list which would point to the first node of the linked list.

Suppose we have a singly linked list as follows

At the end of this linked list, we add a new node with the name “node”, later we make that node point to the first node. The following diagram depicts the procedure.

Insertion in a singly circular linked list:

Insertion at the beginning of a linked list:

We can insert at the beginning of CLL in O(1) and O(n) time complexity.

To achieve that, we iterate to the end of the CLL, and once we reach the last node we perform the following steps:

We make the next pointer of our newnode to point to the next of our last node
Change the next pointer of our last node to point it to the new node.
Return the new node [new head of your CLL]

To do this in O(1) time complexity, simply make the newnode the second node of your CLL and swap the data of the head node and the new node.

Insertion at end

Approach: This is very similar to insertion at the beginning, the difference here is, we are returning the original head as our head of CLL.

To do this, traverse to the end of CLL and:

Change the next pointer of your last node to point to the new node.
Change the next pointer of your new node to point to the head of the CLL.
Return head.

Code:


node * insertion_beg(node * head, int x) {
  node * newnode = new node(x);
  if (head == NULL) { // CLL is empty
    newnode->next = newnode;
    return newnode;
  } else {
    // O(1) approach
    newnode->next = head->next;
    head->next = newnode;
    swap(newnode->data, head->data);
    return head;
  }
}

D