Doubly Linked List

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


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* right;
    Node* left;
    Node (int arg_data) : data (arg_data), right (nullptr), left (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 single linked list after the first found node.
    void Insert (int data, int after) {

        Node* current = head;

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

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

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

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

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

        // Check if the node to be deleted is the head node.
        if (head->data == data) {
            Node * temp = head->right;
            head->right = nullptr;
            delete head;
            head = temp;
        } else {
            Node * current = head;
            while (current->data != data) {
                current = current->right;
            }
            if (current != nullptr) {
                Node * temp = current->right; 
                current->left->right = temp;
                if (temp != nullptr) {
                    temp->left = current->left->left;
                }
                current->left = nullptr; // Reset the left and right links of the node to be deleted.
                current->right = nullptr;
                delete current;
            }
        }
    }

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

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

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

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

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

        while (head != nullptr) {
            Node * temp = head->right;
            head->left = nullptr;
            head->right = nullptr;
            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);
            }
            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


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) : 40
[ 10 40 ]

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 40 ]
Enter new node (data) : 80
[ 10 40 80 ]

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 40 80 ]
Enter new node (data) : 100
After node : 80
[ 10 40 80 100 ]

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 40 80 100 ]
Enter new node (data) : 55
After node : 40
[ 10 40 55 80 100 ]

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 40 55 80 100 ]
Enter new node (data) : 22
After node : 10
[ 10 22 40 55 80 100 ]

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 22 40 55 80 100 ]
Enter node (data) to be deleted : 40
[ 10 22 55 80 100 ]

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 22 55 80 100 ]
Enter node (data) to be deleted : 100
[ 10 22 55 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 22 55 80 ]
Enter node (data) to be deleted : 10
[ 22 55 80 ]

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 : 0
Linked list [ ]
Enter head node (data) : 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) : 99
[ 10 99 ]

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-2021, Algotree.org.
All rights reserved.