Doubly Linked List : Insert, Append and Delete

Doubly linked list
- Doubly linked list consists of dynamically allocated nodes that are linked to each other.
- Every node in a doubly linked list has some data and 2 node pointers ( previous and next ).
     - Previous pointer of a node points to the previous node.
     - Next pointer of a node points to the next node.
- The nodes in a doubly linked list are not contiguous in memory but are located randomly in memory locations allocated at runtime.
- Since the nodes in a linked list are allocated memory at runtime, a linked list can grow or shink depending on the need.
Doubly_Linked_List

Insert Operation
To insert into a doubly-linked list, we need to know the node after which we need to insert a new_node.
1. Traverse the linked list and store the location of the node ( into current_node ) after which a new_node is to be inserted.
2. If the current_node is not Null then
      Create a new_node that is to be inserted.
      Store the location of the node that is next to the current_node i.e ( next_node = current . next )
      Update the next link of the current_node by pointing it to the new_node.
      Point new_node’s prev link to the current_node and new_node’s next link to next_node.
      If next_node is not Null then
             Update the prev link of the next_node to point it to the new_node.
Example : In the below doubly-linked list, a new node with data 80 is inserted after node (42). Insert_Into_A_DLL

Append Operation
To append to a doubly-linked list,
1. Traverse the linked list till the end. Store the location of the last node into current_node.
      Create a new_node to be appended.
      Update the next link of the current_node by pointing it to the new_node.
      Point new_node’s prev link to the current_node.

Delete Operation
(This algorithm deletes the first node with the matching data.)
1. If the node to be deleted matches with the head node i.e head.data = data to be deleted, then
      Store the location of the node to the right of head into next_node.
      Delete the head node
      Update the left link of next_node by pointing it to NULL.
      next_node now become the head node. i.e head = next_node.
2. Else travere the list from the head node till the node to be deleted (current_node) is found.
      If current_node is not NULL then
         Update the next link of the node that is previous to the current_node to point at current_node’s next node.
         If the node next to the current_node is not NULL then
              Update the prev link of the node next to the current_node to point at current_node’s previous node.
         Delete the current_node.
Example : In the below doubly-linked list node with data 42 is deleted. Delete_From_A_DLL

C++ Program to demonstrate create, insert, append and delete operations on a doubly linked list.

#include<iostream>

using namespace std;

class Node {

    public:
    int data;
    Node* next;
    Node* prev;
    Node (int arg_data) : data (arg_data), next (nullptr), prev (nullptr)
    {}
};

class DoublyLinkedList {

    private:
    Node * head;
    public:

    DoublyLinkedList () {
        head = nullptr;
    }

    // Return the head node.
    Node * GetHead () {
        return head;        
    }

    // Create a head node of the doubly linked list.
    void CreateHead (int data) {
        head = new Node(data); 
    }

    // Insert a new node into the doubly-linked list after the first found node.
    void Insert (int data, int after) {

        Node* current = head;

        // Traverse the linked list till the node is found after 
        // which the data is to be insert
        while (current != nullptr && current->data != after) {
            current = current->next;
        }

        if (current != nullptr) {
            Node * temp = new Node(data);
            // Save the location of node after current in next_node.
            Node * next_node = current->next;
            // Point current's link to the new node to be inserted.
            current->next = temp;

            // Point new node's next link (to the next node location previously stored).
            // left link to the current node.
            temp->prev  = current;
            temp->next = next_node;

            // Point next node's prev to the newly added node i.e temp.
            if (next_node != nullptr)
                next_node->prev = temp;
        }
    }

    // Delete the first node matching the data from the doubly linked list.
    void Delete (int data_to_be_deleted ) {

        // If the head node is to be deleted, then the node to the next of head becomes the head node.
        if (head->data == data_to_be_deleted ) {
            Node * temp = head->next;
            delete head;
            head = temp;
            head->prev = nullptr;
        } else {
            Node * current = head;
            while (current->data != data_to_be_deleted ) {
                current = current->next;
            }
            // current is to be deleted.
            if (current != nullptr) {
                current->prev->next = current->next; // Update the next link of the node previous of current
                if (current->next != nullptr) {
                    current->next->prev = current->prev; // Update the previous link of the node to the next of current
                }
                delete current;
            }
        }
    }

    // Append a node to the doubly linked list.
    void Append (int data) {

        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        Node* temp = new Node(data);
        current->next = temp;
        temp->prev = current;
    }

    // Display all the nodes in the doubly linked list.
    void Display () {

        Node* current = head;
        cout << "[ ";
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << "]";
    }

    // Free the linked list.
    void FreeList () {

        while (head != nullptr) {
            Node * temp = head->next;
            delete head;
            head = temp;
        }
    }
};

int main() {

    DoublyLinkedList s;
    int data, after, opt = 0;

    while (opt != 5) {
        cout << "\n\nOptions" << endl;
        cout << "0. Create head." << endl;
        cout << "1. Insert node." << endl;
        cout << "2. Append node." << endl;
        cout << "3. Delete node." << endl;
        cout << "4. Free the linked list." << endl;
        cout << "5. Exit." << endl;
        cout << "Enter Option : ";
        cin >> opt;
        switch (opt) {

        case 0:
            cout << "Linked list ";
            s.Display();
            if (s.GetHead() != nullptr) {
                cout << "\nHead exist." << endl;
            } else {
                cout << "\nEnter head node (data) : ";
                cin >> data;
                s.CreateHead(data);
                s.Display();
            }
            break;

        case 1:
            cout << "Linked list ";
            s.Display();
            cout << "\nEnter new node (data) : ";
            cin >> data;
            cout << "After node : ";
            cin >> after;
            s.Insert(data, after);
            s.Display();
            break;

        case 2:
            cout << "Linked list ";
            s.Display();
            cout << "\nEnter new node (data) : ";
            cin >> data;
            s.Append(data);
            s.Display();
            break;

        case 3:
            cout << "Linked list ";
            s.Display();
            cout << "\nEnter node (data) to be deleted : ";
            cin >> data;
            s.Delete(data);
            s.Display();
            break;

        case 4:
            cout << "Freeing the linked list." << endl;
            s.FreeList();
            break;
        }
    }
    return 0;
}

Output

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 0
Linked list [ ]
Enter head node (data) : 10
[ 10 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 2
Linked list [ 10 ]
Enter new node (data) : 42
[ 10 42 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 1
Linked list [ 10 42 ]
Enter new node (data) : 50
After node : 10
[ 10 50 42 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 1
Linked list [ 10 50 42 ]
Enter new node (data) : 80
After node : 42
[ 10 50 42 80 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 3
Linked list [ 10 50 42 80 ]
Enter node (data) to be deleted : 10
[ 50 42 80 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 3
Linked list [ 50 42 80 ]
Enter node (data) to be deleted : 42
[ 50 80 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 2
Linked list [ 50 80 ]
Enter new node (data) : 100
[ 50 80 100 ]

Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 4
Freeing the linked list.


Options
0. Create head.
1. Insert node.
2. Append node.
3. Delete node.
4. Free the linked list.
5. Exit.
Enter Option : 5



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.