Write a C program to create a circular linked list of n nodes and traverse the list. How to create a circular linked list of n nodes and display all elements of the list in C. Algorithm to create and traverse a Circular linked list.
Required knowledge
Basic C programming, Function, Dynamic memory allocation, Circular linked list
Algorithm to create Circular linked list
Algorithm to create circular linked list
%%Input : N {Total number of nodes to be created}
Being:
alloc (head)
read (data)
head.data ← data;
head.next ← NULL;
prevNode ← head;
For count ← 2 to N do
alloc (newNode)
read (data)
newNode.data ← data;
newNode.next ← NULL;
prevNode.next ← newNode;
prevNode ← newNode;
End for
prevNode.next ← head;
EndAlgorithm to traverse Circular linked list
Algorithm to traverse or display a circular linked list
%%Input : head {Pointer to the first node of the list}
Begin:
If (head == NULL) then
write ('List is empty')
Else then
current ← head;
Do
write ('Data =', current.data)
current ← current.next;
While (current != head)
End if
EndSteps to create circular linked list
The creation steps of a circular linked list is almost similar as of singly linked list. Circular linked list only differs only differs in the last stage of its creation as of singly linked list.
Follow these steps to create a circular linked list.
- Create a head node and assign some data to its data field.
- Make sure that the next pointer field of head node should point to NULL.
- Now head node has been created that points to the first node of the list. Lets take another pointer that also points to the first node say prevNode pointer.
- Create a newNode and assign some more value to its data field and also do sure that next pointer field of newNode should point to NULL.
- Now connect the previous node with newly created node i.e. connect the next pointer field of prevNode with the newNode. So that next pointer field of prevNode points to newNode.
- Move the prevNode ahead i.e. prevNode should point to newNode which can be done as prevNode = prevNode.next.
- Repeat step 4-6 till N (where N is the total number of nodes to be created).
- After all nodes have been created. Now at final stage we have to connect the last node with the first node in order to make it circular. Therefore, now connect the next pointer field of prevNode with the head node i.e. prevNode.next = head (Since prevNode points to last node of the list) and you are done.
Program to create and traverse Circular linked list
/**
* C program to create and traverse Circular Linked List
*/
#include <stdio.h>
#include <stdlib.h>
/*
* Basic structure of Node
*/
struct node {
int data;
struct node * next;
}*head;
/*
* Functions used in this program
*/
void createList(int n);
void displayList();
int main()
{
int n, data, choice=1;
head = NULL;
/*
* Run forever until user chooses 0
*/
while(choice != 0)
{
printf("============================================\n");
printf("CIRCULAR LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);
createList(n);
break;
case 2:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-2");
}
printf("\n\n\n\n\n");
}
return 0;
}
/**
* Creates a circular linked list of n nodes.
* @n Number of nodes to be created
*/
void createList(int n)
{
int i, data;
struct node *prevNode, *newNode;
if(n >= 1)
{
/*
* Creates and links the head node
*/
head = (struct node *)malloc(sizeof(struct node));
printf("Enter data of 1 node: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
prevNode = head;
/*
* Creates and links rest of the n-1 nodes
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
// Link the previous node with newly created node
prevNode->next = newNode;
// Move the previous node ahead
prevNode = newNode;
}
// Link the last node with first node
prevNode->next = head;
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}
}
/**
* Display the content of the list
*/
void displayList()
{
struct node *current;
int n = 1;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
current = head;
printf("DATA IN THE LIST:\n");
do {
printf("Data %d = %d\n", n, current->data);
current = current->next;
n++;
}while(current != head);
}
}============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 0. Exit -------------------------------------------- Enter your choice : 1 Enter the total number of nodes in list: 5 Enter data of 1 node: 10 Enter data of 2 node: 20 Enter data of 3 node: 30 Enter data of 4 node: 40 Enter data of 5 node: 50 CIRCULAR LINKED LIST CREATED SUCCESSFULLY ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 0. Exit -------------------------------------------- Enter your choice : 2 DATA IN THE LIST: Data 1 = 10 Data 2 = 20 Data 3 = 30 Data 4 = 40 Data 5 = 50 ============================================ CIRCULAR LINKED LIST PROGRAM ============================================ 1. Create List 2. Display list 0. Exit -------------------------------------------- Enter your choice : 0