Software & Finance





C++ - Singly Linked Circular List





Singly Linked List, Doubly Linked List, Singly Linked Circular List and Doubly Linked Circular List are an important data structure used in C++ applications.

I have given here the sample code for singly linked circular list, filling elements and traversal in forward direction and counting the number of elements in the list. 


The main difference between singly linked list and singly linked circular list are the next node pointer of last node is NULL in case of singly linked list where as next node pointer of last node is first node in case of singly linked circular list.

If there is only one node in singly linked circular list, then this condition will be true (this == this->next)


Source Code


// Program for singly linked Circular list

 

#include <iostream>

#include <string>

 

struct SLinkCircularList

{

    std::string data;

    SLinkCircularList *next;

 

    SLinkCircularList() : data(""), next(this) { }

    SLinkCircularList(const char *value) : data(value), next(this) { }

 

    SLinkCircularList* InsertNext(const char *data)

    {

        SLinkCircularList *node = new SLinkCircularList(data);

        if(this->next == this) // only one node in the circular list

        {

            // Easy to handle, after the two lines of executions,

            // there will be two nodes in the circular list

            node->next = this;

            this->next = node;

        }

        else

        {

            // Insert in the middle

            SLinkCircularList *temp = this->next;

            node->next = temp;

            this->next = node;

        }

        return node;

    }

 

    bool DeleteNext()

    {

        if(this->next == this)

        {  

            std::cout << "\nThe node can not be deleted as there is only one node in the circular list\n";

            return false;

        }

        SLinkCircularList *pNode = this->next;

        this->next = this->next->next; 

        delete pNode;

    }

 

    void Traverse(SLinkCircularList *node = NULL)

    {

        if(node == NULL)

            node = this;

        std::cout << "\n\nTraversing in Forward Direction\n\n";

 

        SLinkCircularList *startnode = node;

        do

        {

            std::cout << node->data;

            std::cout << "\n";

            node = node->next;

        }

        while(node != startnode);

    }

 

    int GetNumberOfNodes(SLinkCircularList *node = NULL)

    {

        if(node == NULL)

            node = this;

        int count = 0;

        SLinkCircularList *startnode = node;

        do

        {

            count++;

            node = node->next;

        }

        while(node != startnode);

 

        std::cout << "\nCurrent Node Value: " << node->data.c_str();

        std::cout << "\nTotal nodes in Circular List: " << count;

        std::cout << "\n";

        return count;

    }

   

};

 

int main()

{

    SLinkCircularList *node1 = new SLinkCircularList("ONE");

    node1->DeleteNext(); // Delete will fail in this case.

    SLinkCircularList *node2 = node1->InsertNext("TWO");

    node1->DeleteNext(); // It will delete the node2.

    node2 = node1->InsertNext("TWO"); // Insert it again

    SLinkCircularList *node3 = node2->InsertNext("THREE");

    SLinkCircularList *node4 = node3->InsertNext("FOUR");

    SLinkCircularList *node5 = node4->InsertNext("FIVE");

 

    node1->GetNumberOfNodes();

    node3->GetNumberOfNodes();

    node5->GetNumberOfNodes();

 

    node1->Traverse();

    node3->DeleteNext(); // delete the node "FOUR"

    node2->Traverse();

    std::cout << "\n";  

 

    node1->GetNumberOfNodes();

    node3->GetNumberOfNodes();

    node5->GetNumberOfNodes();

 

    std::cout << "\n";

   

    return 0;

}

Output


The node can not be deleted as there is only one node in the circular list

 

Current Node Value: ONE

Total nodes in Circular List: 5

 

Current Node Value: THREE

Total nodes in Circular List: 5

 

Current Node Value: FIVE

Total nodes in Circular List: 5

 

 

Traversing in Forward Direction

 

ONE

TWO

THREE

FOUR

FIVE

 

 

Traversing in Forward Direction

 

TWO

THREE

FIVE

ONE

 

 

Current Node Value: ONE

Total nodes in Circular List: 4

 

Current Node Value: THREE

Total nodes in Circular List: 4

 

Current Node Value: FIVE

Total nodes in Circular List: 4