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

Doubly Linked List

In this page:

  1. What is a Doubly Linked List
  2. Backward Traversal
  3. Insertion
  4. Deletion
  5. Uses

What is a Doubly Linked List

A doubly linked list extends the singly linked list by giving each node two pointers instead of one: one to the next node and one to the previous node, letting you move through the list in either direction.

Example: 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

The previous pointer means you can walk backward from any node toward the head without needing to restart traversal from the beginning, something a singly linked list simply can't do.

Example: 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

Inserting a new node means carefully updating four pointers total: the new node's next and previous, plus the next pointer of the node before it and the previous pointer of the node after it.

Example: 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

Deleting a node is similarly two-sided: the node before it needs its next pointer updated to skip over the removed node, and the node after it needs its previous pointer updated the same way.

Example: 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 are the right choice whenever you need efficient backward traversal or O(1) removal of a node you already have a reference to, such as in an LRU cache or a browser's back/forward history.

Example: 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;
}
🔒

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.