Doubly Linked List Implementation in C++

A doubly linked list is a Linked List with the nodes linked bidirectionally. So, each node contains the link to its previous and next node along with the data. Doubly Linked List is useful for Navigation systems where both front and back navigation is required.

1. Representation of Doubly Linked List

// Linked list node representation
struct Node
{
    int element;
    Node* prev;
    Node* next;
};

// Head of the list
Node* head;

Properties

• Head: The starting point of the linked list
• Node: A node consists of the data element and the pointer to the Previous and Next node
• Element: The actual data (provided as 10, 20, and 30)
• Prev: Pointer to the previous node
• Next: Pointer to the next node

Pros

• Provides the ability to traverse the list backward since it has the link to previous node.
• Also supports faster deletion with the Node pointer. Whereas, the Singly Linked List requires the previous Node pointer to be available for deletion.
• Faster insertion before the given Node pointer. Whereas, the Singly list requires the previous Node pointer to be available.
• Reversing the doubly linked list is simple and straightforward.

Cons

• However, a doubly linked list requires additional memory to store the Prev pointers. (This is addressed in the XOR linked list by keeping the single pointer for both “Prev” and “Next”. The bitwise XOR value of the Prev and the Next pointer is calculated and stored in the node. So, this helps to perform both forward and reverse navigations.)
• Also, it has the operations overhead to keep the Prev pointer up to date.

Applications

• Image Viewer to show previous and next images.
• Browser’s forward and backward navigation.
• Implement Undo and Redo functionalities.
• Construct the MRU (Most Recently Used) and LRU (Least Recently Used) cache.
• In addition, it is useful to Implement other data structures like Stack, Queue, Hash, and Binary Tree.

2. Implementation of Doubly Linked List in C++

/**
 * C++ example to demonstrate the Doubly Linked List
 */
#include <iostream>
using namespace std;

// Linked list node representation
struct Node
{
    int element;
    Node* prev;
    Node* next;
};

/**
 * Doubly Linked list implementation
 */
class DoublyList
{
    // Head of the list
    Node* head;

public:
    // Constructor
    DoublyList() : head(NULL) {}

    // Insert an element in front of the list
    // Returns the new node inserted
    Node* insert_front(int element);

    // Insert an element at the end of the list
    // Returns the new node inserted
    Node* insert_back(int element);

    // Insert an element before the given node
    // Returns the new node inserted
    Node* insert_before(Node* next, int element);

    // Insert an element after the given node
    // Returns the new node inserted
    Node* insert_after(Node* prev, int element);

    // Delete the front element
    // Returns the next node if available, NULL otherwise.
    Node* delete_front();

    // Delete the element from end of the list
    // Returns the previous node, NULL otherwise.
    Node* delete_back();

    // Delete the given node
    // Returns the next node if available, NULL otherwise.
    Node* delete_node(Node* target);

    // Search and delete the given element
    void remove(int element);

    // Search an element from the list
    // Returns the matching node if found, NULL otherwise.
    Node* search(int element);

    // Print the elements
    void print(const std::string& msg);
};

Node* DoublyList::insert_front(int element)
{
    // Step 1. Create the new node
    Node* new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node before the head node
    new_node->prev = NULL;
    new_node->next = head;
    if (head != NULL) {
        head->prev = new_node;
    }

    // Step 3. Change the head to point the new node
    head = new_node;

    return new_node;
}

Node* DoublyList::insert_before(Node* next, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node before the given node
    new_node->prev = next->prev;
    new_node->next = next;
    next->prev = new_node;
    if (new_node->prev != NULL) {
        new_node->prev->next = new_node;
    }

    return new_node;
}

Node* DoublyList::insert_after(Node* prev, int element)
{
    // Step 1. Create the new node
    Node *new_node = new Node();
    new_node->element = element;

    // Step 2. Link the new node after the given node
    new_node->prev = prev;
    new_node->next = prev->next;
    prev->next = new_node;
    if (new_node->next != NULL) {
        new_node->next->prev = new_node;
    }

    return new_node;
}

Node* DoublyList::insert_back(int element)
{
    // Step 1. Check if the list is empty. If true, perform insert_front() and return.
    if (head == NULL) {
        return insert_front(element);
    }

    // Step 2. Traverse the list and find the last node
    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }

    // Step 3. Perform insert_after() with the last node found
    return insert_after(p, element);
}

Node* DoublyList::delete_front()
{
    // Step 1. Store the reference to head as target and
    // move the head to next node if available, NULL otherwise.
    Node* target = head;
    head = head->next;

    // Step 2. Disconnect the target node from the list
    if (head != NULL) {
        head->prev = NULL;
    }

    // Step 3. Delete the target node
    delete target;

    return head;
}

Node* DoublyList::delete_node(Node* target)
{
    // Step 1. Check if the target node is head. If true, perform
    // delete_front() and return.
    if (target->prev == NULL) {
        return delete_front();
    }

    // Step 2. Disconnect the target node by directly linking its
    // previous and next node.
    Node *next = target->next;
    target->prev->next = next;
    if (next != NULL) {
        next->prev = target->prev;
    }

    // Step 3. Delete the target node
    delete target;

    return next;
}

Node* DoublyList::delete_back()
{
    // Step 1. Check if the list is empty and return if true.
    if (head == NULL) {
        return NULL;
    }

    // Step 2. Traverse the list and find the last node as target
    Node *target = head;
    while (target->next != NULL) {
        target = target->next;
    }
    Node* prev = target->prev;

    // Step 3. Delete the target node using delete_node()
    delete_node(target);
    
    return prev;
}

void DoublyList::remove(int element)
{
    // Step 1. Search the element in linked list from start to end.
    for (Node* p = head ; p != NULL ; p = p->next) {
        if (p->element == element) {
            // Step 2. If found, perform delete_node() and return.
            delete_node(p);
            return;
        }
    }

    return;
}

Node* DoublyList::search(int element)
{
    // Iterate the linked list from start to end
    for (Node* node = head ; node != NULL ; node = node->next) {
        if (node->element == element) {
            return node; // Found element
        }
    }
    return NULL; // Not found
}

// Print the linked list
void DoublyList::print(const std::string& msg)
{
    cout << msg << endl;
    cout << "HEAD --> ";
    // Iterate the linked list from start to end
    for (Node* node = head ; node != NULL ; node = node->next) {
        cout << node->element;
        cout << ((node->next == NULL)? " --> " : " <==> ");
    }
    cout << "NULL" << endl << endl;
}

int main()
{
    // Create a linked list
    DoublyList list;
    list.print("initial list");

    // Insert elements
    Node* node_10 = list.insert_front(10);
    list.print("insert_front(10)");

    Node* node_40 = list.insert_back(40);
    list.print("insert_back(40)");

    list.insert_after(node_10, 20);
    list.print("insert_after(node_10, 20)");

    list.insert_before(node_40, 30);
    list.print("insert_before(node_40, 30)");

    // Search an element
    Node *node_30 = list.search(30);
    cout << "search(30) matches node " << node_30->element << endl << endl;

    // Delete elements
    list.delete_front();
    list.print("delete_front()");

    list.delete_node(node_30);
    list.print("delete_node(node_30)");

    list.delete_back();
    list.print("delete_back()");

    list.remove(20);
    list.print("remove(20)");
}

Output

initial list
HEAD --> NULL

insert_front(10)
HEAD --> 10 --> NULL

insert_back(40)
HEAD --> 10 <==> 40 --> NULL

insert_after(node_10, 20)
HEAD --> 10 <==> 20 <==> 40 --> NULL

insert_before(node_40, 30)
HEAD --> 10 <==> 20 <==> 30 <==> 40 --> NULL

search(30) matches node 30

delete_front()
HEAD --> 20 <==> 30 <==> 40 --> NULL

delete_node(node_30)
HEAD --> 20 <==> 40 --> NULL

delete_back()
HEAD --> 20 --> NULL

remove(20)
HEAD --> NULL

3. Insertions on a Doubly Linked List

3.1. Insert Front

Insert the new node at the beginning of the list and update the Head pointer.

Algorithm

1. Create the new node
2. Link the new node before the head node
3. Change the head to point to the new node

Example

3.2. Insert Back

Insert the new node on the backside.

Algorithm

1. Create the new node
2. Traverse the list and find the last node
3. Perform insert_after() with the last node found

Example

3.3. Insert After

Insert the new node after the given Node and update the Previous and Next links

Algorithm

1. Create the new node
2. Link the new node after the given node

Example

3.4. Insert Before

Insert the new node before the given node and update the Previous and Next links.

Algorithm

1. Create the new node
2. Link the new node before the given node

Example

4. Deletions on a Doubly Linked List

4.1. Delete Front

Delete the front Node and move the Head to the next node.

Algorithm

1. Store the reference to head as target and move the head to the next node if available, NULL otherwise.
2. Disconnect the target node from the list

Example

4.2. Delete a Node

Delete the Node with the given pointer.

Algorithm

1. Check if the target node is the head. If true, perform delete_front() and return.
2. Disconnect the target node by directly linking its previous and next nodes.
3. Finally, delete the target node

Example

4.3. Delete Back

Delete a Node from the backside.

Algorithm

1. Check if the list is empty and return if true.
2. Traverse the list and find the last node as the target
3. Delete the target node using delete_node()

Example

5. References

• std::list – C++ standard library for the doubly linked list.