by Jasleen Chhabra | Updated on 24 August 2024

A doubly linked list is an advanced data structure where each node contains pointers to both its previous and next nodes. This allows for more efficient operations compared to a singly linked list, especially when traversing in both directions.

Key Operations on Doubly Linked Lists

1. Insertion
2. Deletion
3. Traversal
4. Searching

Insertion: Adding a New Node to the Doubly Linked List

Insertion in a doubly linked list can occur at the beginning, end, or any position within the list.

At the Beginning

Algorithm:

1. Create a new node.
2. Set the new node’s next pointer to the current head.
3. Set the current head’s previous pointer to the new node (if the list is not empty).
4. Update the head to the new node.

C++ Implementation:

struct Node {

    int data;

    Node* next;

    Node* prev;

};

 

void insertAtBeginning(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = head;

    newNode->prev = nullptr;

 

    if (head != nullptr) {

        head->prev = newNode;

    }

 

    head = newNode;

}

At the End

Algorithm:

1. Create a new node.
2. Traverse to the last node.
3. Set the last node’s next pointer to the new node.
4. Set the new node’s previous pointer to the last node.

C++ Implementation:

void insertAtEnd(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = nullptr;

 

    if (head == nullptr) {

        newNode->prev = nullptr;

        head = newNode;

        return;

    }

 

    Node* last = head;

    while (last->next != nullptr) {

        last = last->next;

    }

    last->next = newNode;

    newNode->prev = last;

}

At a Specific Position

Algorithm:

1. Create a new node.
2. Traverse to the node just before the desired position.
3. Set the new node’s next pointer to the next node.
4. Set the new node’s previous pointer to the current node.
5. Update the next node’s previous pointer to the new node (if not inserting at the end).
6. Update the current node’s next pointer to the new node.

C++ Implementation:

void insertAtPosition(Node*& head, int position, int newData) {

    if (position == 0) {

        insertAtBeginning(head, newData);

        return;

    }

 

    Node* newNode = new Node();

    newNode->data = newData;

 

    Node* current = head;

    for (int i = 0; current != nullptr && i < position - 1; i++) {

        current = current->next;

    }

 

    if (current == nullptr) return;

 

    newNode->next = current->next;

    newNode->prev = current;

 

    if (current->next != nullptr) {

        current->next->prev = newNode;

    }

 

    current->next = newNode;

}

---

Deletion: Removing an Existing Node from the Doubly Linked List

Deletion involves removing a node and adjusting the pointers accordingly.

First Node

Algorithm:

1. Update the head to the next node.
2. Set the new head’s previous pointer to null.
3. Delete the original first node.

C++ Implementation:

void deleteFirstNode(Node*& head) {

    if (head == nullptr) return;

 

    Node* temp = head;

    head = head->next;

 

    if (head != nullptr) {

        head->prev = nullptr;

    }

 

    delete temp;

}

Specific Node

Algorithm:

1. Traverse to the target node.
2. Update the previous node’s next pointer to skip the target node.
3. Update the next node’s previous pointer to skip the target node.
4. Delete the target node.

C++ Implementation:

void deleteNode(Node*& head, int key) {

    Node* temp = head;

 

    while (temp != nullptr && temp->data != key) {

        temp = temp->next;

    }

 

    if (temp == nullptr) return;

 

    if (temp->next != nullptr) {

        temp->next->prev = temp->prev;

    }

 

    if (temp->prev != nullptr) {

        temp->prev->next = temp->next;

    } else {

        head = temp->next;

    }

 

    delete temp;

}

Last Node

Algorithm:

1. Traverse to the last node.
2. Update the second-to-last node’s next pointer to null.
3. Delete the original last node.

C++ Implementation:

void deleteLastNode(Node*& head) {

    if (head == nullptr) return;

    if (head->next == nullptr) {

        delete head;

        head = nullptr;

        return;

    }

 

    Node* last = head;

    while (last->next != nullptr) {

        last = last->next;

    }

 

    last->prev->next = nullptr;

    delete last;

}

---

Traversal: Accessing Each Node in the Doubly Linked List

Traversal involves accessing each node in a sequential manner.

Algorithm:

1. Start from the head.
2. Access each node and move to the next until the end of the list.

C++ Implementation:

void traverseList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

    std::cout << std::endl;

}

---

Searching: Finding a Node with a Specific Value

Searching involves finding a node that contains a specific value.

Algorithm:

1. Start from the head.
2. Compare each node’s data with the target value.
3. If found, return the node; otherwise, continue until the end.

C++ Implementation:

Node* search(Node* head, int key) {

    Node* current = head;

    while (current != nullptr) {

        if (current->data == key) {

            return current;

        }

        current = current->next;

    }

    return nullptr;

}

This blog content provides a comprehensive overview of doubly linked lists, including key operations such as insertion, deletion, traversal, and searching, along with their algorithms and C++ implementations.

---