Doubly Linked List in Data Structure

---

Last Updated on: 2nd Jan 2026 22:53:11 PM

A Doubly Linked List is an advanced form of a linked list that allows traversal in both forward and backward directions. It overcomes some limitations of singly linked lists by storing an extra pointer for the previous node, making deletion and reverse traversal more efficient.

 

This tutorial explains the structure, creation, operations, advantages, limitations, and applications of a Doubly Linked List using simple explanations, real-life examples, and C++ programs suitable for students, exams, and interviews.

 

What is a Doubly Linked List?

A Doubly Linked List is a linear data structure in which each node contains three parts:

1. Previous pointer – stores the address of the previous node

2. Data – stores the actual value

3. Next pointer – stores the address of the next node

 

The first node’s previous pointer is NULL, and the last node’s next pointer is NULL.

 

Real-Life Example

Consider a music playlist where you can move to the next song or go back to the previous song. This forward and backward movement is exactly how a doubly linked list works.

 

Structure of Doubly Linked List

Each node is connected to both its previous and next nodes. This two-way connection allows efficient navigation in both directions.

C++ Structure Code

struct Node {
    int data;
    Node* prev;
    Node* next;
};

 

Creation of Doubly Linked List

A doubly linked list is created dynamically using nodes. Initially, the list is empty, and the head pointer is set to  NULL . Nodes are created using the  new  keyword and linked using  prev  and next pointers.

 

Real-Life Example

Starting a new notebook with no pages. Pages are added one by one as needed.

 

Operations on Doubly Linked List

 

1. Insertion in Doubly Linked List

Insertion is the process of adding a new node to the doubly linked list. It can be done at different positions.

 

Types of Insertion

• Insertion at the Beginning

• Insertion at the End

 

A. Insertion at the Beginning

The new node is placed before the first node. The new node’s next pointer points to the current head, and the head’s previous pointer points back to the new node.

 

Real-Life Example

Adding a new page at the front of a book.

 

Code Example

void insertAtBeginning(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = head;

    if (head != NULL)
        head->prev = newNode;

    head = newNode;
}

 

Time Complexity: O(1)

 

B. Insertion at the End

The list is traversed to the last node, and the new node is added after it. Both previous and next pointers are updated.

 

Real-Life Example

Adding a new customer at the end of a service queue.

 

 

Example

void insertAtEnd(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;
}

 

Time Complexity :O(n)

 

2. Deletion in Doubly Linked List

Deletion is the process of removing a node from the list and updating the links properly.

 

Types of Deletion

• Deletion from the Beginning

• Deletion from the End

 

A. Deletion from the Beginning

The first node is removed, and the head pointer is updated to the next node. The new head’s previous pointer is set to NULL.

 

Real-Life Example

Removing the first task from a task list after completion.

 

Example

void deleteFromBeginning() {
    if (head == NULL)
        return;

    Node* temp = head;
    head = head->next;

    if (head != NULL)
        head->prev = NULL;

    delete temp;
}

 

Time Complexity : O(1)

 

B. Deletion from the End

The list is traversed to the last node. The second-last node’s next pointer is set to NULL.

 

Real-Life Example

Removing the last item from a shopping list.

 

Example 

void deleteFromEnd() {
    if (head == NULL)
        return;

    Node* temp = head;

    while (temp->next != NULL)
        temp = temp->next;

    if (temp->prev != NULL)
        temp->prev->next = NULL;
    else
        head = NULL;

    delete temp;
}

 

Time Complexity : O(n)

 

3. Traversal of Doubly Linked List

Traversal is the process of visiting each node to access its data.

 

Forward Traversal

 

Real-Life Example

Reading a book from first page to last page.

void traverseForward() {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " <-> ";
        temp = temp->next;
    }
    cout << "NULL\n";
}

 

Backward Traversal

 

Real-Life Example

Flipping pages from the last page to the first.

void traverseBackward() {
    if (head == NULL)
        return;

    Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    while (temp != NULL) {
        cout << temp->data << " <-> ";
        temp = temp->prev;
    }
    cout << "NULL\n";
}

 

Time Complexity : O(n)

 

Complete Menu-Driven Program for Doubly Linked List (C++)

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
};

Node* head = NULL;

/* Insert at Beginning */
void insertAtBeginning(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = head;

    if (head != NULL)
        head->prev = newNode;

    head = newNode;
}

/* Insert at End */
void insertAtEnd(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;
}

/* Delete from Beginning */
void deleteFromBeginning() {
    if (head == NULL) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;
    head = head->next;

    if (head != NULL)
        head->prev = NULL;

    delete temp;
    cout << "Node deleted from beginning\n";
}

/* Delete from End */
void deleteFromEnd() {
    if (head == NULL) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    if (temp->prev != NULL)
        temp->prev->next = NULL;
    else
        head = NULL;

    delete temp;
    cout << "Node deleted from end\n";
}

/* Traverse Forward */
void traverseForward() {
    if (head == NULL) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;
    cout << "Forward Traversal: ";
    while (temp != NULL) {
        cout << temp->data << " <-> ";
        temp = temp->next;
    }
    cout << "NULL\n";
}

/* Traverse Backward */
void traverseBackward() {
    if (head == NULL) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    cout << "Backward Traversal: ";
    while (temp != NULL) {
        cout << temp->data << " <-> ";
        temp = temp->prev;
    }
    cout << "NULL\n";
}

/* Main Function */
int main() {
    int choice, value;

    while (true) {
        cout << "\n--- Doubly Linked List Menu ---\n";
        cout << "1. Insert at Beginning\n";
        cout << "2. Insert at End\n";
        cout << "3. Delete from Beginning\n";
        cout << "4. Delete from End\n";
        cout << "5. Traverse Forward\n";
        cout << "6. Traverse Backward\n";
        cout << "7. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                cout << "Enter value: ";
                cin >> value;
                insertAtBeginning(value);
                break;

            case 2:
                cout << "Enter value: ";
                cin >> value;
                insertAtEnd(value);
                break;

            case 3:
                deleteFromBeginning();
                break;

            case 4:
                deleteFromEnd();
                break;

            case 5:
                traverseForward();
                break;

            case 6:
                traverseBackward();
                break;

            case 7:
                cout << "Exiting program\n";
                return 0;

            default:
                cout << "Invalid choice\n";
        }
    }
}

 

Sample Output

--- Doubly Linked List Menu ---
1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse Forward
6. Traverse Backward
7. Exit
Enter your choice: 1
Enter value: 10

--- Doubly Linked List Menu ---
Enter your choice: 2
Enter value: 20

--- Doubly Linked List Menu ---
Enter your choice: 2
Enter value: 30

--- Doubly Linked List Menu ---
Enter your choice: 5
Forward Traversal: 10 <-> 20 <-> 30 <-> NULL

--- Doubly Linked List Menu ---
Enter your choice: 6
Backward Traversal: 30 <-> 20 <-> 10 <-> NULL

--- Doubly Linked List Menu ---
Enter your choice: 4
Node deleted from end

--- Doubly Linked List Menu ---
Enter your choice: 5
Forward Traversal: 10 <-> 20 <-> NULL

--- Doubly Linked List Menu ---
Enter your choice: 3
Node deleted from beginning

--- Doubly Linked List Menu ---
Enter your choice: 5
Forward Traversal: 20 <-> NULL

--- Doubly Linked List Menu ---
Enter your choice: 7
Exiting program

 

Time Complexity Analysis of Doubly Linked List Operations

Time complexity describes how the execution time of an operation increases with the number of nodes (n) in the doubly linked list.

 

Let n = total number of nodes in the list.

 

1. Insert at Beginning

Operation Performed

• A new node is created.

• The new node’s next points to the current head.

• The current head’s prev is updated.

• Head is moved to the new node.

 

Time Complexity

O(1)

 

Reason

• No traversal is required.

• Only constant pointer updates are performed.

 

2. Insert at End

Operation Performed

• The list is traversed from head to the last node.

• The new node is linked using prev and next pointers.

 

Time Complexity

O(n)

 

Reason

• Traversal of all nodes is required to reach the last node.

• Time increases linearly with list size.

 

3. Delete from Beginning

Operation Performed

• The head node is removed.

• Head is updated to the next node.

• prev pointer of the new head is set to NULL.

 

Time Complexity

O(1)

 

Reason

• No traversal is needed.

• Deletion occurs directly at the head.

 

4. Delete from End

Operation Performed

• The list is traversed to reach the last node.

• The second-last node’s next is set to NULL.

• The last node is deleted.

 

Time Complexity

O(n)

 

Reason

• The program must traverse the entire list to find the last node.

 

5. Traverse Forward

Operation Performed

• Each node is visited from head to tail.

 

Time Complexity

O(n)

 

Reason

• Every node is accessed exactly once.

 

6. Traverse Backward

Operation Performed

• The list is first traversed to the last node.

• Nodes are then visited in reverse order using prev.

 

Time Complexity

O(n)

 

Reason

• Although traversal is backward, each node is still visited once.

 

Best, Average, and Worst Case

Operation	Best Case	Average Case	Worst Case
Insert at Beginning	O(1)	O(1)	O(1)
Insert at End	O(n)	O(n)	O(n)
Delete from Beginning	O(1)	O(1)	O(1)
Delete from End	O(n)	O(n)	O(n)
Traversal	O(n)	O(n)	O(n)

 

Advantages of Doubly Linked List

• Allows traversal in both directions

• Deletion of a specific node is easier

• No need to traverse from head to find the previous node

 

Limitations of Doubly Linked List

• Requires extra memory for previous pointer

• Implementation is more complex than singly linked list

• Slightly higher memory overhead

 

Applications of Doubly Linked List

• Browser forward and backward navigation

• Music and video playlists

• Undo and redo operations in editors

• Implementation of deque

• Memory management systems

 

Conclusion

A Doubly Linked List provides greater flexibility compared to a singly linked list by allowing two-way traversal. Although it uses extra memory, its advantages make it suitable for applications that require frequent insertion, deletion, and backward navigation.

 

Keep practicing — you're doing amazing!

Happy Coding!    

---