A common misconception is that doubly linked lists are difficult to understand and work with. This is not the case! In fact, they can be quite easy to use once you get the hang of it. In this article, we will be discussing the basics of doubly linked lists in C++.

What is a Doubly Linked List?

A doubly linked list is a data structure that consists of a set of nodes that are linked together in a linear fashion. Each node contains two pointers: one that points to the next node in the list, and one that points to the previous node in the list. The first and last node have their previous and next pointing to null, respectively. This allows for bidirectional traversal of the list.

Creating a Doubly Linked List in C++

Creating a doubly linked list in C++ is fairly simple. First, we need to define a node class:

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

Next, we need to create a function that will add a new node to the list:

void addNode(Node* &head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    newNode->prev = nullptr;
    if (head != nullptr)
        head->prev = newNode;
    head = newNode;
}

Now that we have a function to add nodes, we can create a doubly linked list by calling this function multiple times:

Node* head = nullptr;
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);
addNode(head, 4);
addNode(head, 5);

We can print the list by traversing it and printing each node's data:

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

Putting everything together, we have the following program:

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

void addNode(Node* &head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    newNode->prev = nullptr;
    if (head != nullptr)
        head->prev = newNode;
    head = newNode;
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = nullptr;
    addNode(head, 1);
    addNode(head, 2);
    addNode(head, 3);
    addNode(head, 4);
    addNode(head, 5);
    printList(head);
    return 0;
}

Running this program produces the following output:

5 4 3 2 1

You can also print the list in reverse by traversing it from the end and printing each node's data:

void printListReverse(Node* head) {
    while (head->next != nullptr)
        head = head->next;
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->prev;
    }
    cout << endl;
}

If we add this function to our program and call it, we get the following output:

1 2 3 4 5

Conclusion

Doubly linked lists are a powerful data structure that can be used to store data in a linear fashion while still allowing for quick traversal in both directions. In C++, they can be easily created and manipulated using the built-in node class.