Creating of Circular Linked List With Header

In this post, I am explaining how a circular linked list is created and displayed along with the source code. The code is written in C programming language.

Creating of Circular Linked List With Header

In this linked list, we will use a node structure comprising of two members, data and next (see Figure 1). The data member is meant for keeping data which can be value of any type. We can have any number of data members and that too of any type but for keeping this example simple, I am using only one data member and that too for keeping integer value. The next member is a pointer meant for pointing at the next node.

Figure 1 – Structure of node

Initially, a header node is created as shown in Figure 2. As expected, the header node consists of two members, data and next where data member is never used but next member is used for pointing at the first node of the linked list.

Figure 2 – Structure of header node

A new node is created called newNode and user is asked to enter value for its data member. Assuming, user enters an integer value 5 for the data member, the newNode will appear as shown in Figure 3.

Figure 3 – The new node, newNode with value 5 assigned to its data member

The header node, headerNode is connected to the first node, newNode by making the next pointer of headerNode to point at newNode using the following statement:

headerNode->next=newNode

Once connected, the headerNode and newNode will appear a shown in Figure 4.

Figure 4 – The header node connected to the new node

To make the linked list appear as circular linked list, the next pointer of newNode is set to point at headerNode by using the following statement:

newNode->next=headerNode

The circular linked list with header will now appear as shown in Figure 5.

Figure 5 – The next pointer of newNode is set to pont at headerNode

To connect more nodes, we will make use of a temporary pointer called temp. The temp pointer is set to point at the first node i.e. newNode as shown in Figure 6.

Figure 6 – Pointer temp is set to point at first node of the linked list

Again, a new node called newNode is created. User is asked to enter value for its data member. If user enters value 2 for its data member, then the nodes will appear as shown in Figure 7.

Figure 7 – New node created with data member value 2

To connect the new node, newNode, the next pointer of temp is set to point at newNode using the following statement:

temp->next=newNode

The nodes will now appear as shown in Figure 8.

Figure 8 – The next pointer of temp is set to point at newNode

To make the linked list circular, the next pointer of newNode is set to point at headerNode as shown in Figure 9.

Figure 9 – newNode’s next pointer is set to point at headerNode

To connect with more nodes, the temp pointer is moved further to point at its next node using the following statement:

temp=temp->next;

The temp pointer will now point at newNode as shown in Figure 10.

Figure 10 – The temp pointer is moved further to point at its next node

Again, a new node is created by name newNode. Assuming the integer value entered for newNode’s data member is 8, the newNode node will appear as shown in Figure 11.

Figure 11 – A new node is created with data member 8

The new node is connected to the circular linked list by setting the next pointer of temp to point at new node, newNode as shown in Figure 12.

Figure 12 – The temp’s next pointer is set to point at newNode

Again, to make the linked list appear as circular, the next pointer of newNode is set to point at headerNode as shown in Figure 13.

Figure 13 – The next pointer of newNode is set to point at headerNode

Traversing of Circular Linked List with Header

To traverse the circular linked list, we make use of a temporary pointer called temp. The temp pointer is set to point at headerNode by using the following statement:

temp=headerNode;

The circular linked list with header will now appear as shown in Figure 14.

Figure 14 – Pointer temp is set to point at headerNode

The temp pointer is moved further to point at its next node i.e. at the first node, 5 as shown in Figure 15. The data member of the node pointed to by temp is traversed i.e. value 5 is displayed on the screen.

Figure 15- Pointer temp is set to point at first node

After traversing the node, the temp pointer is moved further to point at its next node, 2 as shown in Figure 16. Again, the value in the data member of the node pointed to by temp pointer i.e. 2 is displayed on the screen.

Figure 16 – The temp pointer is moved further to point at second node

The temp pointer is then moved to point at its next node i.e. at the node with data member value, 8 as shown in Figure 17. The value in the data member of the node pointed to by temp is traversed i.e. value 8 is displayed on the screen.

Figure 17 – The temp pointer is moved further to point at third node

After displaying the value 8, the temp pointer is moved further to point at its next node i.e. at headerNode. When temp pointer reaches the header node, the program terminates.

Code of the program of creating and displaying circular linked list with header

#include <stdio.h>

#include <stdlib.h>

struct node

{

  int data;

  struct node *next;

};

struct node *headerNode;

void createCircularLinkedList();

void displayCircularLinkedList();

 

int  main()

{

  headerNode=NULL;

  createCircularLinkedList();

  displayCircularLinkedList();

  return 0;

}

 

void createCircularLinkedList()

{

  struct node *newNode,*temp;

  char k=’y’;

  while(k==’y’ || k==’Y’)

  {

    if(headerNode==NULL)

    {

      headerNode=(struct node *)malloc(sizeof(struct node));

      newNode=(struct node *)malloc(sizeof(struct node));

      printf(“Enter an integer value:”);

      scanf(“%d”,&newNode->data);

      headerNode->next = newNode;

      newNode->next=headerNode;

      temp=newNode;

    }

    else

    {

      newNode=(struct node *)malloc(sizeof(struct node));

      printf(“Enter an integer value:”);

      scanf(“%d”,&newNode->data);

      temp->next = newNode;

      newNode->next=headerNode;

      temp=newNode;

    }

    printf(“Want to add more y/n?”);

    scanf(” %c”,&k);

  }

  printf(“Linked list is created\n”);

}

void displayCircularLinkedList()

{

  struct node *temp;

  temp=headerNode;

  if(temp !=NULL)

  {

    temp=temp->next;

    printf(“\nThe content in the circular linked list with

      header are :\n”);

    while(temp!=headerNode)

    {

      printf(“%d\n”,temp->data);

      temp=temp->next;

      /* pointer temp is set to point at the node where its next

      pointer is pointing. That is, pointer temp is set to point

      at its next successive node */

    }

  }

  else

    printf(“Linked list is empty\n”);

}