C++ Data Structures - Doubly Linked List Other Related Topics

C++ - Insert a new node at the end of the Doubly Linked List



In this method, a new node is inserted at the end of the doubly linked list. For example - if the given List is 10->20->30 and a new element 100 is added at the end, the List becomes 10->20->30->100.

Inserting a new node at the end of the doubly linked list is very easy. First, a new node with given element is created. It is then added at the end of the list by linking the last node to the new node.

Doubly Linked List - Add Node At End

The function push_back is created for this purpose. It is a 6-step process.

void push_back(int newElement) {
  
  //1. allocate node
  Node* newNode = new Node();
  
  //2. assign data element
  newNode->data = newElement;
  
  //3. assign null to the next and prev
  //   of the new node
  newNode->next = NULL; 
  newNode->prev = NULL;

  //4. Check the list is empty or not,
  //   if empty make the new node as head 
  if(head == NULL) {
    head = newNode;
  } else {
    
    //5. Else, traverse to the last node
    Node* temp = head;
    while(temp->next != NULL)
      temp = temp->next;
    
    //6. Adjust the links
    temp->next = newNode;
    newNode->prev = temp;
  }    
}

The below is a complete program that uses above discussed concept to insert new node at the end of the doubly linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
      } else {
        Node* temp = head;
        while(temp->next != NULL)
          temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
      }    
    }

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }    
};

// test the code 
int main() {
  LinkedList MyList;

  //Add three elements at the end of the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.PrintList();
  
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 

5