Traversal in Circular Linked List

Traversal is a technique to access all nodes. Linear linked lists, like single and double linked lists, are easy to traverse because they access every node and stop when NULL is detected.

However, this is not possible with circular linked lists. In a circular linked list, walk through each node, starting after the first node, the last node. It will stop when it reaches the first node again.

To start from the last pointer and traverse the circular linked list, check if the last pointer itself is null. If this condition is false, check if there is only one item. Otherwise, hover over the temporary pointer until the last pointer is reached again, or as many times as necessary, as shown in the GIF below.

traversal

Algorithm for traversing a list:

  • Start at the top of the list. If it is not null, access the content of the main node.
  • Then go to the next node (if there is one) to access the node information
  • Continue until there are no more nodes left (that is, until you reach a null node).
void traverseLL(Node head) {
    while(head != NULL)
    {
        print(head.data)
        head = head.next
    }
}

Here is an implementation of a circular linked list operation using C ++. Here we have implemented insert, delete and traverse operations. For the sake of clarity, the linked circular list is shown below.

10-->20-->30-->40-->50-->10

Therefore, the first node, node 10, is reconnected to the last node 50, thus displaying it as a circular linked list.

For example:

traversal

traversal

traversal

traversal

traversal

traversal

Here Code:

#include<iostream>
using namespace std;
struct Node
{
   int data;
   struct Node *next;
};
struct Node *insertInEmpty(struct Node *last, int new_data)
{
   if (last != NULL)
   return last;
   struct Node *temp = new Node;
   temp -> data = new_data;
   last = temp;
   last->next = last;
   return last;
}
struct Node *insertAtBegin(struct Node *last, int new_data)
{
   if (last == NULL)
   return insertInEmpty(last, new_data);
   struct Node *temp = new Node;
   temp -> data = new_data;
   temp -> next = last -> next;
   last -> next = temp;
   return last;
}
struct Node *insertAtEnd(struct Node *last, int new_data)
{
   if (last == NULL)
   return insertInEmpty(last, new_data);
   struct Node *temp = new Node;
   temp -> data = new_data;
   temp -> next = last -> next;
   last -> next = temp;
   last = temp;
   return last;
}
struct Node *insertAfter(struct Node *last, int new_data, int after_item)
{
   if (last == NULL)
   return NULL;
   struct Node *temp, *p;
   p = last -> next;
   do
   {
      if (p ->data == after_item)
      {
         temp = new Node;
         temp -> data = new_data;
         temp -> next = p -> next;
         p -> next = temp;    
         if (p == last)
         last = temp;
         return last;
       }
   p = p -> next;
 } while(p != last -> next);
   cout << "The node with data "<<after_item << " is not present in the list." << endl;
   return last;
}
void traverseList(struct Node *last) {
   struct Node *p;
   if (last == NULL) {
      cout << "Circular linked List is empty." << endl;
      return;
      }
          p = last -> next;
do {
      cout << p -> data << "==>";
      p = p -> next;
      } while(p != last->next);
   if(p == last->next)
   cout<<p->data;
   cout<<"\n\n";
   }
void deleteNode(Node** head, int key)
{
   if (*head == NULL)
   return;
   if((*head)->data==key && (*head)->next==*head) {
      free(*head);
      *head=NULL;
      }
Node *last=*head,*d;
if((*head)->data==key) {
   while(last->next!=*head)
   last=last->next;
   last->next=(*head)->next;
   free(*head);
   *head=last->next;
   }
while(last->next!=*head&&last->next->data!=key) {
   last=last->next;
}
if(last->next->data==key) {
      d=last->next;
      last->next=d->next;
      cout<<"The node with data "<<key<<" deleted from the list"<<endl;
      free(d);
      cout<<endl;
      cout<<"Circular linked list after deleting "<<key<<" is as follows:"<<endl;
      traverseList(last);
      }
   else
   cout<<"The node with data "<< key << " not found in the list"<<endl;
   }
int main()
{
   struct Node *last = NULL;
   last = insertInEmpty(last, 30);
   last = insertAtBegin(last, 20);
   last = insertAtBegin(last, 10);
   last = insertAtEnd(last, 40);
   last = insertAtEnd(last, 60);
   last = insertAfter(last, 50,40 );
   cout<<"The circular linked list created is as follows:"<<endl;
   traverseList(last);
   deleteNode(&last,10);
   return 0;
}

Recommended Articles:

  1. How to split a circular linked list into two halves?
  2. C++ program to insert in a sorted circular linked list?
  3. How to reverse a string using stack?
  4. Insertion in Circular Singly Linked List
  5. How to reverse a linked list?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 114 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
17 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

trackback

[…] Traversal in Circular Linked List […]

You cannot copy content of this page
Scroll Up
17
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.