Circular Linked List in C

What is a Circular Linked List in C?

Introduction

A circular linked list is a list in which the nodes are connected in a sequence, where the last node always points to the head (first) node of the linked list. Generally, the last node in a singly or doubly linked list contains NULL, which means the end of the list. However, the circular linked lists do not have any end as the last node always points to the first node of the linked list which makes it circular.

We must be cautious when navigating circular linked lists to avoid endlessly exploring the list. It should be noted that, unlike normally linked lists, circularly linked lists do not have any nodes with a NULL pointer, every node has a next node in a linear sequence.

Singly Circular Linked List in C

A node in a circular singly linked list contains a data block and a next block to store the address of the next node. The last node's next block contains the address of the first (head) node.

Syntax:

Doubly Circular Linked list in C

A node in a circular doubly linked list contains a data block, and two blocks (prev and next) to store the addresses of the previous node and the next node. The first (head) node contains the address of the last node in the prev block, and the last node's next block contains the address of the first (head) node.

Syntax:

Representation of Linked List in C

• Representation of singly circular linked list:

• Representation of doubly circular linked list:

Programs for Different Operations on the Circular Linked List in C

The following programs show the implementation of commonly used operations on a circular linked list in C language.

Insertion of a Node at the Beginning

We can insert a node at the beginning of the circular linked list using the below procedure:

1. Create a new node and assign it to a temporary variable.
2. If our list is empty (head is NULL), then assign the new node's address in the head pointer and the new node's next pointer.
3. If the list is not empty, assign the head node's address in a new current variable to traverse the list. Assign the new node's address in the last node (current).
4. Update the new node's next block to point to the current first node by assigning the head node's address, then update the head pointer to point to the new node.

Diagrammatic Representation:

Below is the C program to add a node at the beginning of the circular linked list:

Output:

Time and Space Complexities:

O(1) is the time and space complexity of this operation since the insertion operation at the beginning needs a constant space and a constant amount of time.

Explanation:

In the above C program, we have created a structure for the circular singly linked list. Using this structure, we have implemented a createNode() function to create new nodes using the dynamic memory allocation function malloc(). We have also created an insertNodeAtBeginning() function to insert the nodes in the circular linked list. It takes two arguments, first the address of the head node and second the data for the new node. Also, the viewList() function can be used to view the entire list.

Insertion of a Node at the End

We can insert a node at the end of the circular linked list using the below procedure:

1. Create a new node and assign it to a temporary variable.
2. If our list is empty (head is NULL), then assign the new node's address in the head pointer and the new node's next pointer.
3. If the list is not empty, assign the head node address in a new current variable to traverse the list. Assign the new node's address in the last node (current).
4. Update the new node's next block to point to the current first node by assigning the head node's address.

Diagrammatic Representation:

Below is the C program to add a node at the end of the circular linked list:

Output:

Time and Space Complexities:

O(1) is the time and space complexity of this operation since the insertion operation at the end also needs a constant space and a constant amount of time.

Explanation:

Similar to the first C program, we have created a structure for the circular singly linked list. We have created an insertNodeAtEnd() function to insert new nodes at the end of the list. It takes two arguments, first the address of the head pointer and second the data for the new node. We can view the entire list using the viewList() function.

Insertion of a Node After a Specific Element

We can insert a node after a specific element in the circular linked list using the below procedure:

1. Create a new node and assign it to a new node variable.
2. Assign the head node address in a new temp variable, and traverse the list till the next node contains the specified value.
3. Assign the next node's address in the new node variable.
4. Update the current node's next block address to point to the new node.

Diagrammatic Representation:

Below is the program to add a node after a specific value in the circular linked list in C:

Output:

Time and Space Complexities:

O(n) is the time complexity for this operation since the insertion operation at a specific position requires the traversal of the list. O(1) is the space complexity as it requires constant space.

Explanation:

Similar to the above C programs, we have created a circular singly linked list. To insert a node after a specific node, we have created an insertAfterSpecificNode() function. It takes three arguments, first the address of the head pointer, second the data for the new node, and third the data of the node after we have to add the new node. We can view the entire list to check the list after the operation using the viewList() function.

Deleting the First Node

We can delete the first node of a circular linked list in C using the below procedure:

1. If the list has only one node, then delete the head node by using the free() function directly.
2. Create two temporary variables and store the head address in them.
3. Traverse the list to the last node and assign the head's next node address to the last node.
4. Update the head pointer to point to the next node.
5. free the temporary variable which still points to the first node.

Diagrammatic Representation:

Below is the C program to delete the first node from the circular linked list:

Output:

Time and Space Complexities:

O(1) is the time and space complexity of this operation since the deletion of the first node needs a constant space and a constant amount of time.

Explanation:

To delete the first node, we have created a deleteFirstNode() function which takes only one parameter, i.e., the address of the head pointer. We have to make sure that the last node's next block address is also updated to the second node after deleting the first node.

Deleting the Last Node

We can delete the last node of a circular linked list using the below procedure:

1. If the list has only one node, then delete the head node by using the free() function directly.
2. Create two temporary variables and store the head address in one of them.
3. Traverse the list till the second last node and assign the last node address in a temporary node variable.
4. Update the second last node pointer to point to the head node.
5. free the temporary variable which still points to the last node.

Diagrammatic Representation:

Below is the C program to delete the last node from the circular linked list:

Output:

Time and Space Complexities: O(n) is the time complexity for this operation since the deletion operation at the last position requires the traversal of the list. O(1) is the space complexity as it requires constant space.

Explanation: To delete the last node, we have created a deleteLastNode() function which takes only one parameter, i.e., the address of the head pointer. We also have to make sure that the second last node's next block's address is also updated to the first (head) node's address after deleting the last node.

Deleting a Node at a Given Point

We can delete the last node of a circular linked list using the below procedure:

1. Check if the position is first, then apply the algorithm for deleting the first node from a circular linked list (mentioned above).
2. Create two temporary variables and store the head address in one of them.
3. Traverse the list till the previous node to the node to be deleted and assign the position's next node address in a temporary node variable.
4. Update the previous node pointer to point to the current's next node.
5. free the temporary variable which still points to the position node.

Diagrammatic Representation:

Below is the C program to delete a node at a given point (position) from the circular linked list:

Output:

Time and Space Complexities:

O(n) is the time complexity for this operation since the deletion operation at a specified position requires the traversal of the list. O(1) is the space complexity as it requires constant space.

Explanation:

To delete a node at a specific position, we have created a deleteAtPosition() function which takes two parameters, i.e., the address of the head pointer and the position. We have covered all possible test cases in the above program, like deleting the first or last node. We can view the list after the operation to check its validity using the viewList() function.

Example for Understanding

We can use a circular linked list to implement a stack data structure. Let us look at the similarity of operations between stack and circular linked lists:

1. PUSH: Push operation in the stack is similar to the insertion of a node at the beginning of the circular linked list.
2. POP: Pop operation is similar to the deletion of the first node from the circular linked list.
3. TOP: Top points to the first node, i.e., the head pointer in terms of the circular linked list.
4. ViewStack: Stack can be viewed simply by traversing the circular linked list.

C Program to Implement Stack Data Structure Using Circular Linked List:

Output:

Time and Space Complexity:

O(1) is the time and space complexity for all the operations, since the PUSH (insertion at the beginning), and POP (deletion at the beginning) operations need constant space and a constant amount of time.

Explanation:

Implementation of stack using a circular linked list is very simple. The PUSH operation of the stack is similar to the insertion of a node at beginning of the list, POP operation is similar to the deletion of a node from the beginning. A TOP is maintained in the stack, similar to the head pointer in the circular linked list. We can also view the stack using the viewStack() function defined in the program, which is also similar to the viewList() function as seen in the above C programs.