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
|
|