Doubly Linked List ek linear data structure hai jisme har node two pointers rakhta hai:

• Ek pointer previous node ko point karta hai (prev)
• Ek pointer next node ko point karta hai (next)

Yeh singly linked list se zyada powerful hai kyunki isme aap forward aur backward dono direction me traverse kar sakte ho.

Advantages of Doubly Linked List

1. Two-Way Traversal Possible: Doubly linked list mein forward (next) aur backward (prev) ja sakte hai, unlike singly linked list.
2. Easier Deletion: Kisi bhi node ko directly delete kar sakte hai, agar uska pointer mil jaaye, pichle node ka reference already hota hai.
3. Insert/Delete from Both Ends Efficiently: Head ya tail, dono taraf se operations karne easy hote hai.
4. Reversing the List is Simple: Reverse karna simple hai, kyunki prev pointer already hota hai har node ke paas.
5. More Flexible Navigation: Backtracking, undo features jaise operations me kaafi helpful hai.

Disadvantages of Doubly Linked List

1. Extra Memory Usage: Har node me 2 pointers hote hain (next and prev), toh memory singly list se zyada lagti hai.
2. More Complex Implementation: Insert/delete karte time 2 pointers update karne padte hain, toh galti hone ke chance zyada hote hai.
3. Slightly Slower than Singly List: Extra pointer manage karne ki wajah se kuch operations me performance thodi slow ho sakti hai.
4. Debugging Issues: Agar next ya prev galat ho gaya toh list corrupt ho sakti hai.
5. Higher Maintenance: Head, tail, prev-next sab sahi se maintain karna padta hai, varna segmentation fault ho sakta hai.

Applications of Doubly Linked List

1. Web Browser’s Forward and Backward Navigation

• Jab aap browser me “Back” ya “Forward” button click karte ho, wo pages ko track karta hai using DLL (Doubly Linked List).
• Har page ek node hai, jisme prev aur next pointers stored hote hain.

YouTube ← Google ← ChatGPT → GitHub

2. Undo and Redo Functionality

• Text editors, Photoshop, MS Word etc. me Undo-Redo features DLL se banaye jaate hain.
• prev → undo
• next → redo

3. MRU/LRU Cache (Most/Least Recently Used)

• Caching algorithms like LRU (Least Recently Used) DLL + HashMap ka use karte hain.
• DLL se fast insert & delete karte hain from both ends.

4. Playlist Navigation in Music Apps

• DLL ka use music players me hota hai, jahan previous aur next song pe easily jaa sakte ho.
• Har song ek node hota hai.

5. Train Reservation Systems

• Multiple bookings me forward and backward seat linking maintain karne ke liye DLL ka use hota hai.

Structure of Doubly Linked List

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


    Node(int val) {
        data = val;
        prev = NULL;
        next = NULL;
    }
};

class Node { ... };

• Yeh ek user-defined structure hai jise hum Node banane ke liye use karte hain.
• Har Node ek block of memory hai jo value ke saath 2 pointers bhi rakhta hai:
• Ek previous node ke liye (prev)
• Ek next node ke liye (next)

int data;

• Is variable me actual value store hoti hai.
• Jaise agar aap DLL me 10 insert karte ho, toh data = 10 hoga.

Node* prev;

• Yeh pointer previous node ka address rakhta hai.
• DLL ka yeh major feature hai, peeche jaane ke liye yeh pointer help karta hai.

Node* next;

• Yeh pointer next node ka address rakhta hai.
• Same as singly linked list, aage badhne ke liye use hota hai.

Node(int val) → Constructor

Yeh ek constructor function hai jo new node create karte time call hota hai.

Inside this constructor:

data = val;

• Jo bhi value aap pass karte ho (val), wo data me store ho jaati hai.

prev = NULL;
next = NULL;

• Jab node banaya jata hai, initially uska prev aur next dono NULL hote hain.
• Baad me jab aap node ko list me insert karte ho, tab yeh pointers update hote hain.

Linked List Creation Full Code

#include <iostream>
using namespace std;

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

    Node(int val)
    {
        data = val;
        prev = NULL;
        next = NULL;
    }
};

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

int main(int argc, char const *argv[])
{
    Node *head = new Node(10);
    Node *second = new Node(20);
    Node *third = new Node(30);
    Node *fourth = new Node(40);
    Node *fifth = new Node(50);

    head->prev = NULL; // Optional because this already initialize in Node constructor
    head->next = second;

    second->prev = head;
    second->next = third;

    third->prev = second;
    third->next = fourth;

    fourth->prev = third;
    fourth->next = fifth;

    fifth->prev = fourth;
    fifth->next = NULL; // Optional because this already initialize in Node constructor

    cout << "Straight Linked List: ";
    printLL(head);

    cout << "Reversed Linked List: ";
    printReverseLL(fifth);

    return 0;
}

Code Explanation:

1. Node Class

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

    Node(int val) {
        data = val;
        prev = NULL;
        next = NULL;
    }
};

• Har node ke paas:
• data: value (like 10, 20, etc.)
• prev: pichle node ka pointer
• next: agle node ka pointer
• Jab bhi new node banta hai, prev aur next dono NULL hote hain by default.

2. printLL (Forward Print)

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

• Head se start karta hai.
• Jab tak head != NULL, data print karta hai.
• Har baar head = head->next — aage jaata hai.

3. printReverseLL (Backward Print)

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

• Yahan hum list ko peeche se print kar rahe hain.
• Jab tak head != NULL, data print hota hai.
• head = head->prev, previous node pe jaata hai.

4. Main Function (Linking Logic)

Node* head = new Node(10);
Node* second = new Node(20);
Node* third = new Node(30);
Node* fourth = new Node(40);
Node* fifth = new Node(50);

• 5 alag nodes banaye jaate hain.

Linking Step-by-Step

head->next = second;
second->prev = head;

• head ka next → second
• second ka prev → head

head → second

second->next = third;
third->prev = second;

head → second → third
        ↑        ↓
        ← ← ← ← ← 

third->next = fourth;
fourth->prev = third;

fourth->next = fifth;
fifth->prev = fourth;

Ab final linking:

NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 → NULL

• ⇄ means prev and next dono link.
• First node ka prev = NULL
• Last node ka next = NULL

5. Print Output

printLL(head);        // Forward
printReverseLL(fifth); // Backward

Output:

Straight Linked List: 10->20->30->40->50->NULL  
Reversed Linked List: 50->40->30->20->10->NULL