Doubly Linked List

In a singly linked list, each node stores the data and a reference to the next node.

For example:

10 → 20 → 30 → null

If we're currently at 20, we can easily move forward to 30, but we can't directly move back to 10.

A doubly linked list solves this by giving each node two references: one to the next node and one to the previous node.

null ← 10 ⇄ 20 ⇄ 30 → null

This allows us to move through the list in both directions.

What is a Doubly Linked List?

A doubly linked list is a linked list where every node contains three things:

┌──────────┬──────────┬──────────┐
│ Previous │   Data   │   Next   │
└──────────┴──────────┴──────────┘

The previous reference points to the previous node, while next points to the next node.

For example:

null ← 10 ⇄ 20 ⇄ 30 → null

The first node has no previous node, so its previous is null.

The last node has no next node, so its next is null.

Creating a Node

In Java, we can create a node like this:

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

Each node now has:

data → stores the value
prev → points to the previous node
next → points to the next node

Connecting Nodes

Let's create three nodes:

Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);

Now we connect them:

first.next = second;

second.prev = first;
second.next = third;

third.prev = second;

The structure becomes:

null ← 10 ⇄ 20 ⇄ 30 → null

We can also keep a reference to the first node:

Node head = first;

and the last node:

Node tail = third;

So:

head                         tail
 ↓                            ↓
10 ⇄ 20 ⇄ 30

Traversing Forward

Because every node has a next reference, we can move from the beginning to the end.

Node current = head;

while (current != null) {
    System.out.println(current.data);
    current = current.next;
}

Output:

10
20
30

The movement looks like:

head
 ↓
10 → 20 → 30 → null

Traversing Backward

This is where a doubly linked list becomes more useful.

Because every node also has a prev reference, we can start from the tail and move backward.

Node current = tail;

while (current != null) {
    System.out.println(current.data);
    current = current.prev;
}

Output:

30
20
10

The movement is:

tail
 ↓
30 → 20 → 10 → null
      ←    ←

We can move in both directions.

Inserting at the Beginning

Suppose we have:

10 ⇄ 20 ⇄ 30

and we want to add 5 at the beginning.

First, create the new node:

Node newNode = new Node(5);

Then connect it to the current head:

newNode.next = head;
head.prev = newNode;
head = newNode;

Now the list becomes:

null ← 5 ⇄ 10 ⇄ 20 ⇄ 30 → null

Notice that we have to update both directions.

Inserting at the End

Suppose:

10 ⇄ 20 ⇄ 30

and we want to add 40.

If we have a tail reference, this is straightforward:

Node newNode = new Node(40);

tail.next = newNode;
newNode.prev = tail;

tail = newNode;

Now:

null ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → null

Keeping a tail reference makes inserting at the end efficient.

Inserting in the Middle

Suppose we have:

10 ⇄ 20 ⇄ 40

and want to insert 30 between 20 and 40.

We create the new node:

Node newNode = new Node(30);

Then we update the links:

newNode.prev = second;
newNode.next = second.next;

second.next.prev = newNode;
second.next = newNode;

The result is:

10 ⇄ 20 ⇄ 30 ⇄ 40

The important thing here is that multiple references need to be updated.

That's one of the things that makes doubly linked lists a little more complicated than singly linked lists.

Deleting a Node

Suppose we have:

10 ⇄ 20 ⇄ 30

and want to remove 20.

We need to connect 10 directly to 30.

10 ⇄ 30

We can do:

second.prev.next = second.next;
second.next.prev = second.prev;

Now:

10 ⇄ 30

The node containing 20 is no longer connected to the list.

Why Deletion Can Be Efficient

Imagine you already have a reference to the node you want to delete.

In a doubly linked list, that node knows both its neighbors:

10 ⇄ [20] ⇄ 30
      ↑
   target

So we can directly connect:

10 ⇄ 30

without having to search backward for the previous node.

This is one of the main advantages of a doubly linked list over a singly linked list.

Singly vs Doubly Linked List

Let's compare them.

A doubly linked list uses more memory because every node needs an additional prev reference.

Memory Usage

A singly linked node looks like:

┌──────┬──────┐
│ Data │ Next │
└──────┴──────┘

A doubly linked node looks like:

┌────────┬──────┬──────┐
│  Prev  │ Data │ Next │
└────────┴──────┴──────┘

So every doubly linked node stores one extra reference.

This means a doubly linked list generally uses more memory than a singly linked list.

Time Complexity

Common operations have approximately these complexities when we have the appropriate head or tail references:

The important detail is "known node".

If you first have to search for the node, the search itself can take O(n).

A Complete Implementation

Let's create a simple doubly linked list in Java:

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

class Main {
    public static void main(String[] args) {

        Node first = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);

        first.next = second;

        second.prev = first;
        second.next = third;

        third.prev = second;

        Node head = first;
        Node tail = third;

        System.out.println("Forward:");

        Node current = head;

        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }

        System.out.println("Backward:");

        current = tail;

        while (current != null) {
            System.out.println(current.data);
            current = current.prev;
        }
    }
}

Output:

Forward:
10
20
30

Backward:
30
20
10

This demonstrates the main advantage of a doubly linked list: we can traverse in both directions.

Real-Life Example

Think about a web browser's history.

Suppose you visit:

Google → YouTube → Wikipedia → GitHub

From GitHub, you can go back to Wikipedia.

You can also move forward again.

This kind of forward-and-backward navigation is similar to the idea behind a doubly linked list.

Another common example is a music playlist where you can move to the next song or go back to the previous song.

When Should You Use a Doubly Linked List?

A doubly linked list can be useful when:

• You need to move forward and backward.

• You frequently insert or delete elements.

• You already have references to nodes.

• You need efficient operations at both ends.

• The extra memory for the previous reference is acceptable.

However, if you only need forward movement, a singly linked list is simpler and uses less memory.

The main idea is:

A doubly linked list is a linked list where each node contains data, a reference to the next node, and a reference to the previous node.

So instead of:

10 → 20 → 30

we have:

10 ⇄ 20 ⇄ 30

That extra connection is what allows us to move through the list in both directions.