How to create a circular linked list with helper methods in C++
Data structures are specialized formats for storing, processing, and organizing data. Linked lists are one of the most popular data structures. They specialize in holding onto a dynamic set of data elements. There are two kinds of basic linked lists: singly and doubly linked lists. Both of these have another particular variation called a circular linked list. In a circular linked list, all linked list nodes connect to form a circle. This means that the last node connects with the first node (and the first node with the last if it is a circular doubly linked list).
The following figure shows the structure of a circular singly linked list where each node has a data element and a pointer pointing to the next node. The last node's pointer indicates the head node for a circular linked list. This then forms a circular formation of the linked list of data elements.
Similarly, the following figure shows the structure of a circular doubly linked list where each node has a data element, a next pointer, and a previous pointer. For this to be a circular linked list, the tail node's next pointer points to the head node, and the head node's previous pointer points to the tail node creating a circular formation of linked list data elements.
The following is a fully functional code for a singly linked list in C++ using helper methods such as insert and display functions.
#include <iostream>using namespace std;class Node{public:int data_value;Node* next;Node(int input_value){data_value = input_value;next = nullptr;}};class CircularLinkedList{Node* head;public:CircularLinkedList(){head = nullptr;}void insert(int data_value){Node* new_node = new Node(data_value);if (head == nullptr){head = new_node;new_node->next = head;return;}Node* traverse_node = head;while (traverse_node->next != head){traverse_node = traverse_node->next;}traverse_node->next = new_node;new_node->next = head;}void display(){if (head == nullptr){cout << "List is empty." <<endl;return;}Node* traverse_node = head;while (traverse_node != nullptr){cout << traverse_node->data_value << " ";traverse_node = traverse_node->next;if (traverse_node == head){cout << endl;break;}}}};int main(){CircularLinkedList circularList;// insertcircularList.insert(1);circularList.insert(2);circularList.insert(3);circularList.insert(4);// displaycircularList.display();return 0;}
Code explanation
To create this linked list, we require two classes;
NodeClass andCircularLinkedListclass.The
Nodeclass has:Lines 7–8: It creates an integer
data_valueelement and anextnodeLines 10–14: It has a parameterized constructor for creating a new node with a given data element.
The
CircularLinkedListclass has:Lines 22–25: Its default constructor initializes the linked list's head to a null pointer.
insertfunction:Lines 27: It takes a
data_valueelement as a parameter.Lines 28: It creates a
new_nodewith the given data element.Lines 30–35: If the head pointer is null, then it adds the
new_nodeto the head and sets itsnextpointer to itself.Lines 37–43: If not, traverse the linked list using a
traverse_node(temporary) pointer until the last element is reached.Lines 42–43: It attaches the
new_nodeto the end of the last node and points itsnextpointer to the head.
Time complexities
Finally, we come to the worst-case time complexities of our circular singly linked list. When creating our linked list, our insertion function has a time complexity of
Space complexity
The space complexity of a circular singly linked list is
Which of the following statements about circular singly linked lists is correct?
Circular singly linked lists have a beginning and an end and each node points to the previous node.
Circular singly linked lists have a beginning and an end and the last node points to the first node.
Circular singly linked lists have only one node, which points to itself.
Circular singly linked lists have a fixed size and cannot be dynamically resized.
