loader image
Teachics

Circular Linked List

A circular linked list is a type of linked list in which the last node is also connected to the first node to form a circle. Thus a circular linked list has no end.

circular linked list data structure
Circular Linked List Data Structure

There are two types of linked lists:

  • Circular Singly Linked List.
  • Circular Doubly Linked List.

Representation of Circular Linked List

Each of the nodes in the linked list consists of two parts:

  • A data item.
  • An address that points to another node.

A single node can be represented using structure as

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

Each struct node contains a data item as well as a pointer to another struct node. The following example creates a Circular Linked List with three items and display its elements.

Example: Creating a Circular Linked List

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

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

int main()
{
    // Create and initialize nodes
    struct node *head;
    struct node *one = NULL;
    struct node *two = NULL;
    struct node *three = NULL;
    struct node *current = NULL;
 
    // Allocate memory for the nodes
    one = (struct node*) malloc(sizeof(struct node));
    two = (struct node*) malloc(sizeof(struct node));
    three = (struct node*) malloc(sizeof(struct node));
 
    // Assign data to nodes
    one->data = 1;
    two->data = 2;
    three->data = 3;
 
    // Connect first node
    // with the second node
    one->next = two;
     
    // Connect second node
    // with the third node
    two->next = three;
 
    // Connect second node
    // with the third node
    three->next = one;
 
    // Save address of first node in head
    head = one;
    current = head;
 
    // print the linked list values
    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }
    return 0;
}

Now we’ve made a circular linked list with three nodes.

circular linked list
Representation of Circular Linked List
Output
1 2 3

Inserting a New Node to a Circular Linked List

A new node can be inserted anywhere in a circular linked list. Here, we are discussing the following cases.

  • Inserting a new Node at the beginning of a Circular Linked List.
  • Inserting a new Node at the end of a Circular Linked List.

The remaining cases are the same as those described for a singly linked list.

Insert at the beginning of a list

Suppose we want to add a new node with data 24 as the first node in the following linked list. The following changes will be done in the linked list.

circular inserting an element in the beginning of a linked list
  • Allocate memory for new node and initialize its DATA part to 24.
  • Add the new node as the first node of the list by pointing the NEXT part of the new node to HEAD.
  • Make HEAD to point to the first node of the list.
  • Make HEAD point to the new node.

Algorithm: InsertAtBeginning

Step 1: IF AVAIL = NULL
            Write OVERFLOW
            Go to Step 11
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = HEAD
Step 6: Repeat Step 7 while PTR -> NEXT != HEAD
Step 7:     PTR = PTR -> NEXT
        [END OF LOOP]
Step 8: SET NEW_NODE -> NEXT = HEAD
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: SET HEAD = NEW_NODE
Step 11: EXIT

Note that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node.

Insert at the end of the list

Suppose we want to add a new node with data 24 as the last node of the following circular linked list. The following changes have to be made in the linked list.

circular inserting an element in the end of a linked list
  • Allocate memory for the new node and initialize data.
  • Traverse to the end of the list.
  • Point the NEXT part of the last node to the newly created node.
  • Make the value of next part of last node to HEAD.

Algorithm: InsertAtLast

Step 1: IF AVAIL = NULL
            Write OVERFLOW
            Go to Step 1
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = HEAD
Step 6: SET PTR = HEAD
Step 7: Repeat Step 8 while PTR -> NEXT != HEAD
Step 8:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 1 : EXIT

Deleting a Node from a Circular Linked List

Let’s look at how a node is removed from a circular linked list in the following scenarios.

  • The first node is deleted.
  • The last node is deleted.

The remaining cases are the same as those described for a singly linked list.

Deleting first node from a list

The following changes have to be made to the linked list if we want to remove the first node having data 24.

deleting first node of a circular linked list 1
  • Check if the linked list is empty or not. Exit if the list is empty.
  • Make HEAD points to the second node.
  • Traverse to the end of the list and point the next part of last node to second node.
  • Free the first node from memory.

Algorithm: DeleteFirst

Step 1: IF HEAD = NULL
            Write UNDERFLOW
            Go to Step 8
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: Repeat Step 4 while PTR -> NEXT != HEAD
Step 4:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 5: SET PTR -> NEXT = HEAD -> NEXT
Step 6: FREE HEAD
Step 7: SET HEAD = PTR -> NEXT
Step 8: EXIT

Deleting last node from the list

Suppose we want to delete the last node from the circular linked list. The following changes will be done in the list.

deleting last node from a circular linked list
  • Traverse to the end of the list.
  • Change value of next pointer of second last node to HEAD.
  • Free last node from memory.

Algorithm: DeleteFirst

Step 1: IF HEAD = NULL
            Write UNDERFLOW
            Go to Step 8
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: Repeat Steps 4 and 5 while PTR NEXT != HEAD
Step 4:     SET PREPTR = PTR
Step 5:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 6: SET PREPTR -> NEXT = HEAD
Step 7: FREE PTR
Step 8: EXIT
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments