Doubly Linked List Implementation in CPP

1. Introduction

A Doubly Linked List is an enhanced version of a singly linked list where each node not only has a reference to the next node but also to the previous node. This bidirectional linkage allows traversal in both forward and backward directions. In this blog post, we will cover a basic implementation of a doubly linked list in C++.

2. Implementation Steps

1. Declare a Node class to represent individual elements in the list. This class will have three members: data, next pointer, and prev pointer.

2. Declare a DoublyLinkedList class that will encapsulate the list behavior.

3. Define methods to add an item at the end (append), at the beginning (prepend), remove an item (remove), and display the list (display).

4. Demonstrate the usage of the DoublyLinkedList class.

3. Implementation in C++ Programming

#include<iostream>
class Node {
public:
    int data;          // Data to be stored
    Node* next;        // Pointer to the next node
    Node* prev;        // Pointer to the previous node
    Node(int value) {
        data = value;
        next = nullptr;
        prev = nullptr;
    }
};
class DoublyLinkedList {
private:
    Node* head;
public:
    DoublyLinkedList() {
        head = nullptr;
    }
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
    void prepend(int value) {
        Node* newNode = new Node(value);
        if (head != nullptr) {
            head->prev = newNode;
            newNode->next = head;
        }
        head = newNode;
    }
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " <-> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
    void remove(int value) {
        if (head == nullptr) return;
        Node* temp = head;
        while (temp != nullptr && temp->data != value) {
            temp = temp->next;
        }
        if (temp == nullptr) return;
        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 dll;
    dll.append(10);
    dll.append(20);
    dll.prepend(5);
    std::cout << "Doubly Linked List: ";
    dll.display();
    dll.remove(10);
    std::cout << "After removing 10: ";
    dll.display();
    return 0;
}

Output:

Doubly Linked List: 5 <-> 10 <-> 20 <-> nullptr
After removing 10: 5 <-> 20 <-> nullptr

Explanation:

1. The Node class represents individual elements of the doubly linked list. Each node contains data and pointers to both the next and previous nodes.

2. DoublyLinkedList class provides the basic behavior of the list.

3. append(int value): Adds a node with the provided value to the end of the list.

4. prepend(int value): Adds a node with the provided value to the beginning of the list.

5. display(): Traverses and prints each node's data.

6. remove(int value): Searches for a node with the given value and removes it from the list, ensuring that the links of surrounding nodes are updated correctly.

7. main(): Demonstrates the usage of the doubly linked list by adding nodes both at the beginning and the end, and then removing a node.