C program to create and traverse Circular linked list

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.

Circular linked list


Required knowledge

Basic C programming, 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.datadata;
    head.nextNULL;
    prevNodehead;
    For count ← 2 to N do
        alloc (newNode)
        read (data)
        newNode.datadata;
        newNode.nextNULL;
        prevNode.nextnewNode;
        prevNodenewNode;
    End for
    prevNode.nexthead;
End


Algorithm 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
        currenthead;
        Do
            write ('Data =', current.data)
            currentcurrent.next;
        While (current != head)
    End if
End


Steps 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.
Creation of Circular linked list step 1
Make sure that the next pointer field of head node should point to NULL.
Creation of circular linked list step 2
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.
Creation of circular linked list step 3
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.
Creation of circular linked list step 4
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.
Creation of circular linked list step 5
Move the prevNode ahead i.e. prevNode should point to newNode which can be done as prevNode = prevNode.next.
Creation of circular linked list step 6
Repeat step 4-6 till N (where N is the total number of nodes to be created).
Creation of circular linked list step 7
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.
Creation of circular linked list step 8


Program

/**
 * 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;

    /*
     * Runs 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;

            //Links the previous node with newly created node
            prevNode->next = newNode;

            //Moves the previous node ahead
            prevNode = newNode;
        }

        //Links the last node with first node
        prevNode->next = head;

        printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
    }
}



/**
 * Displays 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);
    }
} 


Output
============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
0. Exit
--------------------------------------------
Enter your choice : 1
Enter the total number of nodes in list: 4
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40

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





============================================
CIRCULAR LINKED LIST PROGRAM
============================================
1. Create List
2. Display list
0. Exit
--------------------------------------------
Enter your choice : 0


Happy coding ;)
Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment