Circular Doubly Linked List in C++
This article will demonstrate how to implement a circular doubly linked list in C++.
Circular Doubly Linked List Data Structure from Scratch in C++
A doubly linked list is a data structure where each node stores pointers to both the next and the previous nodes. This makes it an optimal choice to implement std::deque-like containers. It would be better to make a doubly linked list circular so that the last node’s next member points to the beginning of the list and the first node also points to the last node as its previous.
At first, we need to declare a struct named ListNode used to construct a list. Next, we define a CircularList class with two data members of type ListNode* and three-member functions.
Note that we decided to include only one constructor that accepts a string value and initializes the first node, but this part can be modified as the programmer sees fit. Two data members - head and end- store the first and last nodes. We also have separate functions to add elements on each side of the list.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
struct ListNode *prev = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->prev = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
end = end->next;
return end;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
head = new_node;
return head;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
CircularList clist("Xenial");
clist.insertNodeHead("Saucy");
clist.insertNodeEnd("Quantal");
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.printNodes();
return EXIT_SUCCESS;
}
Output:
node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
-----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal
The general algorithm for element insertion entails allocating a new ListNode object, assigning corresponding node pointers to its members, and then modifying the head/end members as needed. We also include a printNodes function to display the list contents as we may need to inspect the correctness of the code. Note that one must not forget to deallocate all the memory after the list object goes out of scope. The latter function is implemented as a destructor.
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook