← Back to DSA Course | Chapter 4: Linked Lists | Lesson 2 of 8

Doubly Linked List क्या है

एक doubly linked list एक train जैसी है जहां हर car आगे वाली और पीछे वाली दोनों से jook है, इसलिए आप किसी भी direction में चल सकते हैं।

In this page:

  1. What is a Doubly Linked List
  2. Backward Traversal
  3. Insertion
  4. Deletion
  5. Uses
Syntax
markup 
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

What is a Doubly Linked List

एक doubly linked list singly linked list को extend करती है हर node को एक के बजाय दो pointers देकर: एक अगले node के लिए और एक पिछले node के लिए, आपको किसी भी direction में list में move करने देते हुए।

उदाहरण: What is a Doubly Linked List

#include <iostream>
using namespace std;
struct Node { int data; Node* next; Node* prev; };
int main() {
    Node* a = new Node{1, nullptr, nullptr};
    Node* b = new Node{2, nullptr, a};
    a->next = b;
    cout << "a.next=" << a->next->data << ", b.prev=" << b->prev->data << endl;
    return 0;
}
class Node { int data; Node next, prev; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.prev = a;
        System.out.println("a.next=" + a.next.data + ", b.prev=" + b.prev.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

a, b = Node(1), Node(2)
a.next = b
b.prev = a
print(f"a.next={a.next.data}, b.prev={b.prev.data}")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next, *prev; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1; a->prev = NULL;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2; b->next = NULL;
    a->next = b; b->prev = a;
    printf("a.next=%d, b.prev=%d\n", a->next->data, b->prev->data);
    return 0;
}

Backward Traversal

Previous pointer का मतलब है आप किसी भी node से head की ओर पीछे चल सकते हैं बिना शुरुआत से traversal restart किए, कुछ जो एक singly linked list बिल्कुल नहीं कर सकती।

उदाहरण: Backward Traversal

#include <iostream>
using namespace std;
struct Node { int data; Node* next; Node* prev; };
int main() {
    Node* a = new Node{1, nullptr, nullptr};
    Node* b = new Node{2, nullptr, a};
    Node* c = new Node{3, nullptr, b};
    a->next = b; b->next = c;
    for (Node* cur = c; cur; cur = cur->prev) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next, prev; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.prev = a; b.next = c; c.prev = b;
        for (Node cur = c; cur != null; cur = cur.prev) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

a, b, c = Node(1), Node(2), Node(3)
a.next, b.prev = b, a
b.next, c.prev = c, b
cur = c
while cur:
    print(cur.data, end=" ")
    cur = cur.prev
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next, *prev; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1; a->prev = NULL;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *cur = c; cur; cur = cur->prev) printf("%d ", cur->data);
    printf("\n");
    return 0;
}

Insertion

एक नया node insert करने का मतलब है carefully कुल चार pointers update करना: नए node का next और previous, साथ ही इससे पहले वाले node का next pointer और बाद वाले node का previous pointer।

उदाहरण: Insertion

#include <iostream>
using namespace std;
struct Node { int data; Node* next; Node* prev; };
int main() {
    Node* a = new Node{1, nullptr, nullptr};
    Node* c = new Node{3, nullptr, a};
    a->next = c;
    Node* b = new Node{2, c, a};
    a->next = b; c->prev = b;
    for (Node* cur = a; cur; cur = cur->next) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next, prev; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), c = new Node(3);
        a.next = c; c.prev = a;
        Node b = new Node(2);
        b.next = c; b.prev = a;
        a.next = b; c.prev = b;
        for (Node cur = a; cur != null; cur = cur.next) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

a, c = Node(1), Node(3)
a.next, c.prev = c, a
b = Node(2)
b.next, b.prev = c, a
a.next, c.prev = b, b
cur = a
while cur:
    print(cur.data, end=" ")
    cur = cur.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next, *prev; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1; a->prev = NULL;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = c; c->prev = a;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2; b->next = c; b->prev = a;
    a->next = b; c->prev = b;
    for (struct Node *cur = a; cur; cur = cur->next) printf("%d ", cur->data);
    printf("\n");
    return 0;
}

Deletion

एक node delete करना similarly दो-तरफ़ा है: इससे पहले वाले node को इसका next pointer update करके हटाए गए node को skip करना चाहिए, और बाद वाले node को इसका previous pointer उसी तरह update करना चाहिए।

उदाहरण: Deletion

#include <iostream>
using namespace std;
struct Node { int data; Node* next; Node* prev; };
int main() {
    Node* a = new Node{1, nullptr, nullptr};
    Node* b = new Node{2, nullptr, a};
    Node* c = new Node{3, nullptr, b};
    a->next = b; b->next = c;
    a->next = c; c->prev = a;
    for (Node* cur = a; cur; cur = cur->next) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next, prev; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.prev = a; b.next = c; c.prev = b;
        a.next = c; c.prev = a;
        for (Node cur = a; cur != null; cur = cur.next) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

a, b, c = Node(1), Node(2), Node(3)
a.next, b.prev = b, a
b.next, c.prev = c, b
a.next, c.prev = c, a
cur = a
while cur:
    print(cur.data, end=" ")
    cur = cur.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next, *prev; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1; a->prev = NULL;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    a->next = c; c->prev = a;
    for (struct Node *cur = a; cur; cur = cur->next) printf("%d ", cur->data);
    printf("\n");
    return 0;
}

Uses

Doubly linked lists सही choice हैं जब भी आपको efficient backward traversal या किसी node को हटाने की ज़रूरत हो जिसका reference आपके पास पहले से है, जैसे एक LRU cache या browser की back/forward history में।

उदाहरण: Uses

#include <iostream>
using namespace std;
struct Node { int data; Node* next; Node* prev; };
int main() {
    Node* a = new Node{1, nullptr, nullptr};
    Node* b = new Node{2, nullptr, a};
    Node* c = new Node{3, nullptr, b};
    a->next = b; b->next = c;
    Node* target = b;
    target->prev->next = target->next;
    target->next->prev = target->prev;
    cout << "Removed " << target->data << " in O(1)" << endl;
    for (Node* cur = a; cur; cur = cur->next) cout << cur->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next, prev; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.prev = a; b.next = c; c.prev = b;
        Node target = b;
        target.prev.next = target.next;
        target.next.prev = target.prev;
        System.out.println("Removed " + target.data + " in O(1)");
        for (Node cur = a; cur != null; cur = cur.next) System.out.print(cur.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

a, b, c = Node(1), Node(2), Node(3)
a.next, b.prev = b, a
b.next, c.prev = c, b
target = b
target.prev.next = target.next
target.next.prev = target.prev
print(f"Removed {target.data} in O(1)")
cur = a
while cur:
    print(cur.data, end=" ")
    cur = cur.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next, *prev; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1; a->prev = NULL;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    struct Node *target = b;
    target->prev->next = target->next;
    target->next->prev = target->prev;
    printf("Removed %d in O(1)\n", target->data);
    for (struct Node *cur = a; cur; cur = cur->next) printf("%d ", cur->data);
    printf("\n");
    return 0;
}
Related Topics

Singly Linked List क्या है · Circular Linked List क्या है · Linked List को Reverse करना · Linked List का Middle ढूँढना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. सिर्फ next pointers update करना और prev भूल जाना, इसलिए list पीछे traverse होने पर टूट जाती है।
  2. Tail पर insert या delete करते समय एक null next पर next->prev सेट करना।
  3. पहले इसके neighbours को एक-दूसरे से link किए बिना एक node delete करना।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Singly Linked List Next Lesson → Circular Linked List

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.