Table of contents
1.
Introduction
2.
Doubly Linked List Representation in C++
3.
Implementation of Doubly Linked List in C++
4.
Basic Operations on C++ Doubly Linked List
4.1.
1. Insertion at the Front
4.2.
2. Insertion at the End
4.3.
3. Deletion from the Front:
4.4.
4. Deletion from the End:
4.5.
5. Traversal and Printing
5.
C++ Program to Implement Doubly Linked List
6.
Doubly Linked List Complexity
6.1.
Time Complexity
6.2.
Space Complexity
7.
Advantages of Doubly Linked List in C++
8.
Disadvantages of Doubly Linked List in C++
9.
Doubly Linked List Applications
10.
Difference between singly linked lists and doubly linked lists
11.
Frequently Asked Questions
11.1.
Can a doubly linked list be implemented using a circular structure?
11.2.
Is it possible to remove a node from a doubly linked list in constant time?
11.3.
How does the time complexity of searching for an element in a doubly linked list compare to that of an array?
12.
Conclusion
Last Updated: Dec 10, 2024
Easy

Double Linked List Program in C++

Author Rahul Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A double-linked list is a type of data structure that's especially useful when you need to organize and manage data efficiently. It consists of a series of elements called nodes, each containing data and two references (or links) connecting them to the next and the previous node. This setup allows you to move both forward and backward through the list, which is not possible with a singly linked list that only goes one way. Double-linked lists are crucial for creating more complex data structures like queues, stacks, and even more advanced forms like graphs. This flexibility makes them ideal for applications where navigation in both directions is frequently required, like navigating through a music playlist or undo stacks in software applications. 

Double Linked List Program in C++

In this article, we will discuss the representation, implementation, basic operations, complexity analysis, advantages, disadvantages, and applications of doubly linked lists in C++. 

Doubly Linked List Representation in C++

In a doubly linked list, each node contains three parts: a data value, a pointer to the next node & a pointer to the previous node. The head node's previous pointer points to NULL, while the last node's next pointer points to NULL. 

Let’s see how we can represent a node in a doubly linked list using a struct in C++:

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


Each `Node` has an integer `data` field to store a value, a `prev` pointer to the previous node & a `next` pointer to the next node in the list.

Implementation of Doubly Linked List in C++

To implement a doubly linked list in C++, we'll create a `DoublyLinkedList` class that contains a private `Node* head` pointer to keep track of the first node. The class will also have public methods to perform various operations on the list.

This is a basic skeleton for the `DoublyLinkedList` class:

class DoublyLinkedList {
private:
    Node* head;
public:
    DoublyLinkedList() {
        head = NULL;
    }


    // Other methods for insertion, deletion, traversal, etc.
};


The constructor initializes the `head` pointer to `NULL` when a new `DoublyLinkedList` object is created.

We'll implement the following key methods:

  • `insertFront(int data)`: Insert a new node at the beginning of the list.
     
  • `insertEnd(int data)`: Insert a new node at the end of the list.
     
  • `deleteFront()`: Delete the first node of the list.
     
  • `deleteEnd()`: Delete the last node of the list.
     
  • `printList()`: Traverse & print the elements of the list.

Basic Operations on C++ Doubly Linked List

1. Insertion at the Front

To insert a new node at the beginning of the list, we follow these steps:

  • Create a new node with the given data.
     
  • If the list is empty, make the new node the head.
     
  • Otherwise, set the new node's next pointer to the current head & the current head's prev pointer to the new node.
     
  • Update the head to point to the new node.
void insertFront(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = head;
  if (head != NULL)
        head->prev = newNode;
    head = newNode;
}

2. Insertion at the End

To insert a new node at the end of the list, we follow these steps:

  • Create a new node with the given data.
     
  • If the list is empty, make the new node the head.
     
  • Otherwise, traverse to the last node & set its next pointer to the new node.
     
  • Set the new node's prev pointer to the last node & its next pointer to NULL.
void insertEnd(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    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;
}

3. Deletion from the Front:

To delete the first node of the list, we follow these steps:

  • If the list is empty, return.
     
  • Otherwise, store the head node in a temporary pointer.
     
  • Update the head to point to the next node.
     
  • If the new head is not NULL, set its prev pointer to NULL.
     
  • Delete the temporary pointer to free memory.
void deleteFront() {
    if (head == NULL)
        return;
    Node* temp = head;
    head = head->next;
    if (head != NULL)
        head->prev = NULL;
    delete temp;
}

4. Deletion from the End:

To delete the last node of the list, we follow these steps:

  • If the list is empty, return.
     
  • If the list has only one node, delete it & set head to NULL.
     
  • Otherwise, traverse to the second-to-last node.
     
  • Set its next pointer to NULL & delete the last node.
void deleteEnd() {
    if (head == NULL)
        return;
    if (head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }
    Node* temp = head;
    while (temp->next->next != NULL)
        temp = temp->next;


    delete temp->next;
    temp->next = NULL;
}

5. Traversal and Printing

To traverse & print the elements of the list, we start from the head & move forward until we reach the end (NULL).

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

C++ Program to Implement Doubly Linked List

Now, let's put together a complete C++ program that shows the implementation and use of a doubly linked list.

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
class DoublyLinkedList {
private:
    Node* head;
public:
    DoublyLinkedList() {
        head = NULL;
    }
    void insertFront(int data) {
    }
    void insertEnd(int data) {
    }
    void deleteFront() {
    }
    void deleteEnd() {
    }


    void printList() {
    }
};

int main() {
    DoublyLinkedList list;

    list.insertEnd(5);
    list.insertFront(2);
    list.insertEnd(8);
    list.insertFront(1);

    cout << "Original List: ";
    list.printList();

    list.deleteFront();
    list.deleteEnd();

    cout << "Modified List: ";
    list.printList();

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output:

Original List: 1 2 5 8
Modified List: 2 5


In this program, we create a `DoublyLinkedList` object & perform insertions at the front & end of the list using the `insertFront()` & `insertEnd()` methods. We then print the original list using the `printList()` method.

Next, we delete nodes from the front and end of the list using the `deleteFront()` and `deleteEnd()` methods, respectively. Finally, we print the modified list to see its updated contents.

Doubly Linked List Complexity

Time Complexity

  • Insertion at the front or end: O(1) 
    - Inserting a new node at the beginning or end of the list takes constant time since we have direct access to the head & can easily update the pointers.
     
  • Deletion from the front or end: O(1)
    - Deleting a node from the beginning or end of the list also takes constant time as we can quickly update the head or the pointers of the second-to-last node.
     
  • Accessing or searching for an element: O(n)
    - In the worst case, we may need to traverse the entire list to access or search for an element, resulting in a linear time complexity.

Space Complexity

  • The space complexity of a doubly linked list is O(n), where n is the number of nodes in the list.
  • Each node in the list requires additional space to store the prev & next pointers, along with the data.

Overall, doubly linked lists provide efficient insertion & deletion at both ends, but accessing or searching for elements requires traversing the list, resulting in a linear time complexity.

Advantages of Doubly Linked List in C++

1. Efficient insertion & deletion: Inserting or deleting nodes at both ends of the list takes constant time, as we have direct access to the head & tail pointers.
 

2. Bidirectional traversal: With doubly linked lists, we can traverse the list in both forward & backward directions efficiently, as each node contains pointers to its previous & next nodes.
 

3. No need for extra space: Unlike arrays, doubly linked lists don't require contiguous memory allocation, making them more flexible in terms of memory usage.
 

4. Dynamic size: Doubly linked lists can grow or shrink dynamically during runtime, allowing for efficient memory utilization.
 

5. Suitable for certain algorithms: Doubly linked lists are particularly useful in scenarios where constant-time insertion, deletion, or bidirectional traversal is required, such as in implementing undo/redo functionality or in certain caching algorithms.

Disadvantages of Doubly Linked List in C++

1. Extra memory usage: Each node in a doubly linked list requires additional memory to store the previous & next pointers, resulting in higher memory consumption compared to singly linked lists or arrays.
 

2. Complexity in implementation: Implementing a doubly linked list is slightly more complex than implementing a singly linked list due to the need to manage both the previous and next pointers during insertions, deletions, and traversals.
 

3. Inefficient random access: Unlike arrays, doubly linked lists do not provide efficient random access to elements. Accessing an element at a specific index requires traversing the list from the beginning or end, resulting in a linear time complexity.
 

4. Cache-unfriendly: Doubly linked lists are not cache-friendly because the nodes are scattered in memory, leading to potential cache misses & slower memory access compared to contiguous data structures like arrays.
 

5. Overhead for small datasets: For small datasets, the overhead of maintaining the previous & next pointers in each node may outweigh the benefits of using a doubly linked list, making other data structures like arrays or singly linked lists more efficient.

Doubly Linked List Applications

Doubly linked lists find applications in various scenarios where efficient insertion, deletion, and bidirectional traversal are required. Some common applications are:

1. Undo/Redo functionality: Doubly linked lists can be used to implement undo and redo operations in text editors or graphics applications. Each action can be stored as a node, and the previous and next pointers allow easy navigation between actions.
 

2. Browser history: Web browsers use doubly linked lists to maintain the history of visited pages. The previous and next pointers enable efficient navigation through history.
 

3. Music or video playlists: Doubly linked lists can be used to create playlists where songs or videos are connected in both forward and reverse order, allowing easy navigation and reordering of the playlist.
 

4. Caching algorithms: Some caching algorithms, such as the Least Recently Used (LRU) cache, can be implemented using a doubly linked list. The list keeps track of the order in which elements are accessed, making it easy to remove the least recently used element when the cache is full.
 

5. Memory management: Operating systems and memory managers may use doubly linked lists to keep track of free and allocated memory blocks. The previous and next pointers allow efficient coalescing of adjacent free blocks during memory deallocation.

Difference between singly linked lists and doubly linked lists

ParametersSingly Linked ListDoubly Linked List
Node StructureEach node in a singly linked list contains a data value and a pointer to the next node only.In addition to the data value and next pointer, each node in a doubly linked list also includes a pointer to the previous node.
Memory UsageSingly linked lists are more memory-efficient compared to doubly linked lists because they require less space per node.Doubly linked lists consume more memory as each node needs to store an additional pointer to the previous node, resulting in higher memory overhead.
TraversalSingly linked lists allow traversal only in the forward direction, starting from the head node and moving towards the tail.Doubly linked lists enable traversal in both forward and backward directions, providing more flexibility in accessing elements.
Insertion and DeletionInserting or deleting a node in a singly linked list requires updating only the next pointer of the previous node.In a doubly linked list, insertion and deletion operations involve updating both the next and previous pointers of the neighboring nodes, making the process slightly more complex.
Reverse TraversalSingly linked lists do not provide an efficient way to traverse the list in reverse order without using additional data structures or recursion.Doubly linked lists allow efficient traversal in the reverse direction by following the previous pointers, making it easier to navigate backwards through the list.
SuitabilitySingly linked lists are suitable for scenarios where backward traversal is not required and memory efficiency is a priority.Doubly linked lists are preferred when bidirectional traversal and efficient insertion/deletion at both ends of the list are necessary, despite the higher memory usage.

Frequently Asked Questions

Can a doubly linked list be implemented using a circular structure?

Yes, a doubly linked list can be implemented as a circular structure where the last node's next pointer points to the first node and the first node's previous pointer points to the last node.

Is it possible to remove a node from a doubly linked list in constant time?

Yes, removing a node from a doubly linked list can be done in constant time O(1) if we have direct access to the node that needs to be removed.

How does the time complexity of searching for an element in a doubly linked list compare to that of an array?

Searching for an element in a doubly linked list has a time complexity of O(n) in the worst case, as we may need to traverse the entire list. In contrast, accessing an element in an array by its index takes constant time O(1).

Conclusion

In this article, we discussed the basics of doubly linked lists in C++. We learned about the representation of a doubly linked list, its implementation, and the basic operations such as insertion, deletion, and traversal. We also explained the advantages and disadvantages of doubly linked lists and compared them with singly linked lists. Doubly linked lists provide efficient insertion and deletion at both ends and allow bidirectional traversal, which makes them suitable for various applications where such operations are frequently required.

You can also check out our other blogs on Code360.

Live masterclass