C++ Program to Implement a Doubly Linked List

1. Introduction

Doubly linked lists are an extension of the simple linked list, where each node points to both its next node and its previous node. This bidirectional linkage allows for easier traversal in both forward and backward directions. In this blog post, we will create a basic doubly linked list in C++ and implement basic operations like insertion, deletion, and display.

2. Program Overview

Our program will:

1. Define a Node structure for the doubly linked list.

2. Implement a DoublyLinkedList class with functions to:

- Add elements to the end of the list.

- Remove elements from the list.

- Display elements in the list in both forward and reverse order.

3. Code Program

#include<iostream>
using namespace std;

// Node structure for Doubly Linked List
class Node {
public:
    int data;
    Node* prev;
    Node* next;

    // Constructor to initialize a new node
    Node(int val) {
        data = val;
        prev = nullptr;
        next = nullptr;
    }
};

class DoublyLinkedList {
private:
    Node* head;

public:
    DoublyLinkedList() {
        head = nullptr;
    }

    // Function to append a new node at the end
    void append(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next) {
                temp = temp->next; // Traverse to the last node
            }
            temp->next = newNode;
            newNode->prev = temp;
        }
    }

    // Function to delete a node by value
    void deleteNode(int value) {
        Node* temp = head;
        while (temp) {
            if (temp->data == value) {
                if (temp->prev) temp->prev->next = temp->next;
                if (temp->next) temp->next->prev = temp->prev;
                if (temp == head) head = head->next;
                delete temp;
                return;
            }
            temp = temp->next;
        }
    }

    // Function to display the list forward
    void displayForward() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " <-> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }

    // Function to display the list in reverse
    void displayReverse() {
        Node* temp = head;
        while (temp && temp->next) {
            temp = temp->next; // Move to the last node
        }
        while (temp) {
            cout << temp->data << " <-> ";
            temp = temp->prev;
        }
        cout << "NULL" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(10);
    dll.append(20);
    dll.append(30);
    cout << "Doubly Linked List forward: ";
    dll.displayForward();
    cout << "Doubly Linked List reverse: ";
    dll.displayReverse();
    dll.deleteNode(20);
    cout << "After deletion of 20: ";
    dll.displayForward();
    return 0;
}

Output:

Doubly Linked List forward: 10 <-> 20 <-> 30 <-> NULL
Doubly Linked List reverse: 30 <-> 20 <-> 10 <-> NULL
After deletion of 20: 10 <-> 30 <-> NULL

4. Step By Step Explanation

1. We've defined a Node class which represents an element in our doubly linked list, with pointers to the next and previous nodes.

2. Our DoublyLinkedList class provides functions to append data to the list, delete nodes, and display the list in both directions.

3. In the append method, if the list is empty, the new node becomes the head. Otherwise, it's attached at the end.

4. The deleteNode method searches for a node by value and adjusts the pointers of the adjacent nodes before deleting it.

5. We've also provided a demonstration in the main function, where we create a list, display it, and then delete a node.