Understanding Doubly Linked Lists

A doubly linked list is a type of linked list in which each node contains three components:

1. Data: The value stored in the node.
2. Next Pointer: A pointer to the next node in the list.
3. Previous Pointer: A pointer to the previous node in the list.

Unlike a singly linked list, a doubly linked list allows traversal in both directions — forward and backward — making it a versatile data structure for a variety of applications.

Advantages of Doubly Linked Lists

1. Bidirectional Traversal: You can traverse the list in both forward and backward directions.
2. Ease of Deletion: Given a pointer to a node, it is easier to delete that node since you can access its predecessor.
3. More Flexibility: Useful in scenarios like implementing undo operations in software, navigating back and forth between web pages, etc.

Implementation of Doubly Linked List

Doubly Linked List is quite similar to Singly Linked List except it contains extra pointer to previous node. Similar to Singly Linked List we can implement Doubly Linked List using either structure or class.

1️⃣ Using Structure:

// Define the Node structure for a doubly linked list
struct Node {
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* prev;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Complete Example:

// Example program
#include <iostream>
#include <string>

using namespace std;

struct Node{
    int data;
    Node* next;
    Node* previous;
    
    Node(int data) {
        this->data = data;
        next = nullptr;
        previous = nullptr;
    }

};

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

int main()
{
  Node* head = new Node(0);
  
  Node* first = new Node(1);
  
  Node* second = new Node(2);
  
  Node* third = new Node(3);
  
  Node* fourth  = new Node(4);
  
  Node* fifth = new Node(5);
  
  head->next = first;

  first->next = second;
  first->previous = head;
  
  second->next = third;
  second->previous = first;
  
  third->next = fourth;
  third->previous = second;
  
  fourth->next = fifth;
  fourth->previous = third;

  traverse(head);
  
}

2️⃣ Using Class:

// Define the Node class for a doubly linked list
class Node {
public:
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* prev;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Complete Example:

// Example program
#include <iostream>
#include <string>

using namespace std;

// Define the Node class for a doubly linked list
class Node {
public:
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* previous;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), previous(nullptr) {}
};

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

int main()
{
  Node* head = new Node(0);
  
  Node* first = new Node(1);
  
  Node* second = new Node(2);
  
  Node* third = new Node(3);
  
  Node* fourth  = new Node(4);
  
  Node* fifth = new Node(5);
  
  head->next = first;

  first->next = second;
  first->previous = head;
  
  second->next = third;
  second->previous = first;
  
  third->next = fourth;
  third->previous = second;
  
  fourth->next = fifth;
  fourth->previous = third;

  traverse(head);
  
}