C++ Linked List Exercises: Insert a node at the beginning of a Doubly Linked List

Last update on December 20 2024 12:23:49 (UTC/GMT +8 hours)

Write a C++ program to insert a new node at the beginning of a Doubly Linked List.

Test Data:
Doubly linked list is as follows:
------------------------------
Traversal in Forward direction: Orange White Green Red
Traversal in Reverse direction: Red Green White Orange
Insert a new node at the beginning of a Doubly Linked List:
-------------------------------------------------------------
Traversal in Forward direction: Pink Orange White Green Red
Traversal in Reverse direction: Red Green White Orange Pink

Sample Solution:

C++ Code:

#include <iostream> // Including input-output stream header file

using namespace std; // Using standard namespace

// A doubly linked list node
struct Node {
   string data; // Data field to store string data
   struct Node* next; // Pointer to the next node
   struct Node* prev; // Pointer to the previous node
};

// Function to append data at the front of the doubly linked list
void append_data(Node** head, string new_data)
{
   // Create a new node and allocate memory.
   struct Node* newNode = new Node;

   // Assign data to the new node
   newNode->data = new_data;

   // A new node has been added with the name head and the previous node 
   // set to null, since it is being added at the front.
   newNode->next = (*head);
   newNode->prev = NULL;

   // Previous head is the new node
   if ((*head) != NULL)
   (*head)->prev = newNode;

   // Head points to new node
   (*head) = newNode;
}

// Function to insert a new node at the beginning of the doubly linked list
void NodeInsertatBegin(Node** head, string text)
{
    struct Node* newnode;
    if(head == NULL)
    {
        cout<<"Empty List...!\n"; // Display message if the list is empty
    } 
    else {
        struct Node* newNode = new Node;
        newNode->data = text;
        newNode->next = *head;  
        newNode->prev = NULL;     
        (*head)->prev = newNode;   
        (*head) = newNode;          
    }
}

// Function to display contents of the doubly linked list
void displayDlList(Node* head)
{
    Node* last_node;
    cout << "\nTraversal in Forward direction: ";
    while (head != NULL) {
        cout << " " << head->data << " "; // Displaying data in forward direction
        last_node = head;
        head = head->next;
    }
    cout << "\nTraversal in Reverse direction: ";
    while (last_node != NULL) {
        cout << " " << last_node->data << " "; // Displaying data in reverse direction
        last_node = last_node->prev;
    }
}

// Main program
int main() {
   /* Start with the empty list */
   struct Node* head = NULL; // Initializing the head of the linked list as NULL
   append_data(&head, "Red"); // Appending "Red" at the front of the list
   append_data(&head, "Green"); // Appending "Green" at the front of the list
   append_data(&head, "White"); // Appending "White" at the front of the list
   append_data(&head, "Orange"); // Appending "Orange" at the front of the list  
   cout<<"Doubly linked list is as follows: ";
   cout<<"\n------------------------------";
   displayDlList(head); // Displaying the doubly linked list
   cout<<"\n\nInsert a new node at the beginning of a Doubly Linked List:";
   cout<<"\n-------------------------------------------------------------";
   NodeInsertatBegin(&head, "Pink"); // Inserting "Pink" node at the beginning of the list
   displayDlList(head); // Displaying the updated doubly linked list
   return 0; // Returning from the main function
}

Sample Output:

Doubly linked list is as follows:
------------------------------
Traversal in Forward direction:  Orange  White  Green  Red
Traversal in Reverse direction:  Red  Green  White  Orange

Insert a new node at the beginning of a Doubly Linked List:
-------------------------------------------------------------
Traversal in Forward direction:  Pink  Orange  White  Green  Red
Traversal in Reverse direction:  Red  Green  White  Orange  Pink

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Count number of nodes in a doubly linked list.
Next C++ Exercise: Insert a new node at the end of a Doubly Linked List.