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::cout; using std::cin;
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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - C++ Data Structure

  • Insert a Node in Singly Linked List C++
  • Implement the Binary Tree Data Structure in C++