Introduction, Need, Node Structure, Memory Representation, Head & Tail, and Creating Nodes

Welcome to the Doubly Linked List series!

In our previous series, we learned everything about the Singly Linked List, including insertion, deletion, traversal, searching, updating, counting, and reversing.

Although Singly Linked Lists are powerful, they have one major limitation—they can only be traversed in one direction.

To overcome this limitation, computer scientists introduced the Doubly Linked List, a data structure where every node stores references to both the next node and the previous node.

In this tutorial, you’ll learn everything about the fundamentals of Doubly Linked Lists before we start performing insertion and deletion operations in the next part.

📚 Table of Contents

What is a Doubly Linked List?
Why Do We Need a Doubly Linked List?
Limitations of Singly Linked List
Advantages of Doubly Linked List
Structure of a Doubly Linked List
Components of a Node
Memory Representation
Head and Tail
Creating a Node in Java
Java Program – Creating Nodes
Time Complexity
Frequently Asked Questions
Conclusion

📖 What is a Doubly Linked List?

A Doubly Linked List (DLL) is a linear data structure in which every node contains:

📦 Data
⬅️ Reference to the Previous Node
➡️ Reference to the Next Node

Unlike a Singly Linked List, where movement is possible only in the forward direction, a Doubly Linked List allows traversal in both forward and backward directions.

Visual representation:

NULL ← [Prev | 10 | Next] ⇄ [Prev | 20 | Next] ⇄ [Prev | 30 | Next] → NULL

Notice that every node knows both its previous and next neighbors.

🤔 Why Do We Need a Doubly Linked List?

Let’s consider a Singly Linked List.

10 → 20 → 30 → 40 → NULL

Suppose you are currently at node 30.

Now you want to move back to 20.

Can you?

❌ No.

Why?

Because node 30 only knows where 40 is.

It has no information about 20.

You would have to start from the head again.

This becomes inefficient for many applications.

❌ Limitations of Singly Linked List

Although Singly Linked Lists are useful, they have several limitations.

1️⃣ One-Way Traversal

10 → 20 → 30 → 40

You can move

10 → 20 → 30 → 40

But you cannot move

40 → 30 → 20

2️⃣ Deletion is More Difficult

Suppose we want to delete 30.

10 → 20 → 30 → 40

We first need to find 20, because only the previous node can change its next reference.

3️⃣ Backward Navigation is Impossible

Applications like:

Browser Back Button
Undo Operations
Music Playlist Previous Song

cannot be efficiently implemented using a Singly Linked List.

✅ Advantages of Doubly Linked List

A Doubly Linked List solves these problems.

✔ Forward Traversal

✔ Backward Traversal

✔ Easier Deletion

✔ Easier Insertion Before a Node

✔ Efficient Navigation

🌍 Real-Life Analogy

Imagine you’re reading a book.

You can:

➡️ Turn to the next page.

⬅️ Go back to the previous page.

This is exactly how a Doubly Linked List works.

Another example is a browser.

Google

↓

YouTube

↓

Wikipedia

You can press:

⬅️ Back

➡️ Forward

This is one of the biggest applications of a Doubly Linked List.

🔗 Structure of a Doubly Linked List

Every node contains three parts.

+---------+--------+---------+
| Previous|  Data  |  Next   |
+---------+--------+---------+

Unlike a Singly Linked List, every node stores two references.

🧩 Components of a Node

⬅️ Previous

Stores the reference of the previous node.

Example

Previous

📦 Data

Stores the actual information.

Example

➡️ Next

Stores the reference of the next node.

Complete node

+-----------+-------+-----------+
| Previous  | Data  |   Next    |
+-----------+-------+-----------+

🧠 Memory Representation

Suppose we have

10 ⇄ 20 ⇄ 30

Memory might look like this.

Address   Previous   Data   Next

100       NULL       10     250

250       100        20     400

400       250        30     NULL

Notice that

The first node has no previous node.
The last node has no next node.

Therefore,

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

📍 Understanding Head and Tail

A Doubly Linked List generally uses two important references.

🟢 Head

Points to the first node.

Head

↓

10 ⇄ 20 ⇄ 30

🔴 Tail

Points to the last node.

10 ⇄ 20 ⇄ 30

             ↑

           Tail

Having a Tail makes several operations more efficient, such as:

Insertion at the end
Backward traversal

🎨 Visual Representation

Head                                         Tail
 ↓                                            ↑
NULL ← [10] ⇄ [20] ⇄ [30] ⇄ [40] → NULL

🤔 Why Do We Need Tail?

Suppose we only have a Head.

To reach the last node,

we must traverse the entire list.

Time Complexity

O(n)

Now suppose we also have a Tail.

Tail

↓

40

We can directly access the last node.

Time Complexity

O(1)

💻 Creating a Node in Java

Every node is represented using a class.

class Node {

    int data;

    Node prev;

    Node next;

    Node(int data) {

        this.data = data;

        prev = null;

        next = null;

    }

}

📝 Explanation

int data;

Stores the value.

Node prev;

Stores the previous node reference.

Node next;

Stores the next node reference.

Node(int data)

Constructor

Creates a new node.

prev = null;

next = null;

Initially,

the node has no neighbors.

💻 Program 1 – Creating One Node

class Node {

    int data;
    Node prev;
    Node next;

    Node(int data) {

        this.data = data;
        prev = null;
        next = null;

    }

}

public class DoublyLinkedList {

    public static void main(String[] args) {

        Node head = new Node(10);

        System.out.println(head.data);

    }

}

Output

💻 Program 2 – Creating Three Nodes

class Node {

    int data;
    Node prev;
    Node next;

    Node(int data) {

        this.data = data;
        prev = null;
        next = null;

    }

}

public class DoublyLinkedList {

    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;

        System.out.println(first.data);

        System.out.println(second.data);

        System.out.println(third.data);

    }

}

Output

🎨 Visual Representation

NULL ← [10] ⇄ [20] ⇄ [30] → NULL

More detailed view

NULL ← +------+ ←→ +------+ ←→ +------+ → NULL
       | 10   |     | 20   |     | 30   |
       +------+     +------+     +------+

📈 Time Complexity

Creating one node

O(1)

Creating multiple nodes

O(n)

because one node is created at a time.

💾 Space Complexity

Each node stores

One integer
Previous reference
Next reference

Overall memory

O(n)

⚖️ Singly vs Doubly Linked List

Feature	Singly Linked List	Doubly Linked List
Previous Pointer	❌ No	✅ Yes
Next Pointer	✅ Yes	✅ Yes
Forward Traversal	✅ Yes	✅ Yes
Backward Traversal	❌ No	✅ Yes
Memory Usage	Less	More
Insertion Before a Node	Difficult	Easy
Deletion	Moderate	Easier

❓ Frequently Asked Questions

Q1. What is a Doubly Linked List?

A Doubly Linked List is a linked list in which every node stores references to both the previous and next nodes.

Q2. Why is it called “Doubly”?

Because each node has two links:

Q3. What is the advantage over a Singly Linked List?

The biggest advantage is bidirectional traversal. You can move both forward and backward through the list.

Q4. Why does a Doubly Linked List use more memory?

Each node stores an additional prev reference compared to a Singly Linked List.

Q5. Why do many implementations use a Tail pointer?

A Tail pointer provides direct access to the last node, making operations like insertion at the end and backward traversal more efficient.

🎯 Key Takeaways

🔗 A Doubly Linked List stores previous and next references.
⬅️ It supports backward traversal.
➡️ It supports forward traversal.
📦 Each node contains three fields: prev, data, and next.
📍 The Head points to the first node.
📍 The Tail points to the last node.
💾 It uses more memory than a Singly Linked List but offers greater flexibility.
🚀 It is widely used in browser history, undo/redo systems, and navigation-based applications.

🎉 Conclusion

A Doubly Linked List is an enhanced version of a Singly Linked List that overcomes the limitation of one-way traversal by introducing a previous reference in every node. This additional link makes operations like backward traversal, deletion, and insertion before a node much easier and more efficient.

In this part, you learned the fundamental concepts of Doubly Linked Lists, including why they are needed, how a node is structured, how memory is organized, the purpose of the Head and Tail pointers, and how to create nodes in Java.

👉 In Part 1B, we’ll continue by learning how to:

🚶 Traverse a Doubly Linked List in the forward direction.
🔙 Traverse it in the backward direction.
🏗️ Build a complete Doubly Linked List in Java.
💻 Write complete Java programs with detailed dry runs and complexity analysis.

Introduction, Need, Node Structure, Memory Representation, Head & Tail, and Creating Nodes

📚 Table of Contents

📖 What is a Doubly Linked List?

🤔 Why Do We Need a Doubly Linked List?

❌ Limitations of Singly Linked List

1️⃣ One-Way Traversal

2️⃣ Deletion is More Difficult

3️⃣ Backward Navigation is Impossible

✅ Advantages of Doubly Linked List

🌍 Real-Life Analogy

🔗 Structure of a Doubly Linked List

🧩 Components of a Node

⬅️ Previous

📦 Data

➡️ Next

🧠 Memory Representation

📍 Understanding Head and Tail

🟢 Head

🔴 Tail

🎨 Visual Representation

🤔 Why Do We Need Tail?

💻 Creating a Node in Java

📝 Explanation

💻 Program 1 – Creating One Node

Output

💻 Program 2 – Creating Three Nodes

Output

🎨 Visual Representation

📈 Time Complexity

💾 Space Complexity

⚖️ Singly vs Doubly Linked List

❓ Frequently Asked Questions

Q1. What is a Doubly Linked List?

Q2. Why is it called “Doubly”?

Q3. What is the advantage over a Singly Linked List?

Q4. Why does a Doubly Linked List use more memory?

Q5. Why do many implementations use a Tail pointer?

🎯 Key Takeaways

🎉 Conclusion

Comments

Leave a Reply Cancel reply