C++ Program to Implement a Doubly Linked List

A doubly linked list is a type of linked list in which each node contains two pointers: one pointing to the next node and another pointing to the previous node. This bidirectional nature of doubly linked lists allows for more efficient traversal and manipulation of the list, especially when backward traversal is required. In this article, we will explore the implementation of a doubly linked list in C++, demonstrating various operations with detailed examples and their outputs.

Table of Contents

Prerequisites

Before diving into the implementation, you should have:

Basic understanding of C++ programming.
Familiarity with pointers and dynamic memory allocation.
Knowledge of linked lists and their basic operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Basic Doubly Linked List Implementation

1.1 Node Structure and List Initialization

Let’s start by defining the structure of a node in the doubly linked list and initializing the list.

C++

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node* prev;

    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr) {}

    void insertAtEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->prev = temp;
        }
    }

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

private:
    Node* head;
};

int main() {
    DoublyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Doubly Linked List: ";
    list.display();

    return 0;
}

1.2 Output Explanation

In this example, the doubly linked list is structured as follows:

C++

10 <-> 20 <-> 30 <-> 40

The output will display: 10 20 30 40

2. Advanced Doubly Linked List Operations

2.1 Insertion at Beginning

Let’s add a method to insert a node at the beginning of the list.

C++

class DoublyLinkedList {
    // ... (previous code remains the same)

public:
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }
};

int main() {
    DoublyLinkedList list;
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtBeginning(10);
    list.insertAtEnd(40);
    list.insertAtBeginning(5);

    std::cout << "Doubly Linked List after insertions: ";
    list.display();

    return 0;
}

2.2 Output Explanation

In this example, the doubly linked list after the insertions is structured as follows:

C++

5 <-> 10 <-> 20 <-> 30 <-> 40

The output will display: 5 10 20 30 40

3. Deletion in Doubly Linked List

3.1 Deletion of a Specific Node

Next, we will implement a method to delete a specific node from the list.

C++

class DoublyLinkedList {
    // ... (previous code remains the same)

public:
    void deleteNode(int key) {
        Node* temp = head;

        while (temp != nullptr && temp->data != key) {
            temp = temp->next;
        }

        if (temp == nullptr) return;  // Node not found

        if (temp->prev != nullptr) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next;
        }

        if (temp->next != nullptr) {
            temp->next->prev = temp->prev;
        }

        delete temp;
    }
};

int main() {
    DoublyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Doubly Linked List: ";
    list.display();

    list.deleteNode(20);
    std::cout << "List after deleting 20: ";
    list.display();

    list.deleteNode(10);
    std::cout << "List after deleting 10: ";
    list.display();

    return 0;
}

3.2 Output Explanation

In this example, the doubly linked list after the deletions is structured as follows:

After deleting 20:10 <-> 30 <-> 40 The output will display: 10 30 40
After deleting 10:30 <-> 40 The output will display: 30 40

4. Reversal of Doubly Linked List

4.1 Reversal Method

Let’s implement a method to reverse the doubly linked list.

C++

class DoublyLinkedList {
    // ... (previous code remains the same)

public:
    void reverse() {
        Node* temp = nullptr;
        Node* current = head;

        while (current != nullptr) {
            temp = current->prev;
            current->prev = current->next;
            current->next = temp;
            current = current->prev;
        }

        if (temp != nullptr) {
            head = temp->prev;
        }
    }
};

int main() {
    DoublyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Doubly Linked List: ";
    list.display();

    list.reverse();
    std::cout << "Reversed Doubly Linked List: ";
    list.display();

    return 0;
}

4.2 Output Explanation

In this example, the doubly linked list after reversal is structured as follows:

C++

40 <-> 30 <-> 20 <-> 10

The output will display: 40 30 20 10

Conclusion

A C++ program to implement a doubly linked list involves defining the node structure and implementing various operations such as insertion, deletion, traversal, and reversal. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality