Doubly Linked List - Insert a new node at the end
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.
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; } }
void push_back(struct Node** head_ref, int newElement) { //1. allocate node struct Node *newNode, *temp; newNode = (struct Node*)malloc(sizeof(struct 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_ref == NULL) { *head_ref = newNode; } else { //5. Else, traverse to the last node temp = *head_ref; while(temp->next != NULL) { temp = temp->next; } //6. Adjust the links temp->next = newNode; newNode->prev = temp; } }
def push_back(self, newElement): #1 & 2 & 3. allocate node, assign data element, assign # null to the next and prev of the new node newNode = Node(newElement) #4. Check the list is empty or not, # if empty make the new node as head if(self.head == None): self.head = newNode return else: #5. Else, traverse to the last node temp = self.head while(temp.next != None): temp = temp.next #6. Adjust the links temp.next = newNode newNode.prev = temp
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 = new Node(); temp = head; while(temp.next != null) temp = temp.next; //6. Adjust the links temp.next = newNode; newNode.prev = temp; } }
public 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 = new Node(); temp = head; while(temp.next != null) temp = temp.next; //6. Adjust the links temp.next = newNode; newNode.prev = temp; } }
public function push_back($newElement) { //1. allocate 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($this->head == null) { $this->head = $newNode; } else { //5. Else, traverse to the last node $temp = new Node(); $temp = $this->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<<"\n"; } 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
#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; struct Node* prev; }; //Add new element at the end of the list void push_back(struct Node** head_ref, int newElement) { struct Node *newNode, *temp; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = newElement; newNode->next = NULL; newNode->prev = NULL; if(*head_ref == NULL) { *head_ref = newNode; } else { temp = *head_ref; while(temp->next != NULL) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } } //display the content of the list void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) { printf("The list contains: "); while (temp != NULL) { printf("%i ",temp->data); temp = temp->next; } printf("\n"); } else { printf("The list is empty.\n"); } } // test the code int main() { struct Node* MyList = NULL; //Add three elements at the end of the list. push_back(&MyList, 10); push_back(&MyList, 20); push_back(&MyList, 30); PrintList(MyList); return 0; }
The above code will give the following output:
The list contains: 10 20 30
# node structure class Node: def __init__(self, data): self.data = data self.next = None self.prev = None #class Linked List class LinkedList: def __init__(self): self.head = None #Add new element at the end of the list def push_back(self, newElement): newNode = Node(newElement) if(self.head == None): self.head = newNode return else: temp = self.head while(temp.next != None): temp = temp.next temp.next = newNode newNode.prev = temp #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (temp != None): print(temp.data, end=" ") temp = temp.next print() else: print("The list is empty.") # test the code MyList = LinkedList() #Add three elements at the end of the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30
//node structure class Node { int data; Node next; Node prev; }; class LinkedList { Node head; 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 = new 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 = new Node(); temp = this.head; if(temp != null) { System.out.print("The list contains: "); while(temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } else { System.out.println("The list is empty."); } } }; // test the code public class Implementation { public static void main(String[] args) { LinkedList MyList = new LinkedList(); //Add three elements at the end of the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30
using System; //node structure class Node { public int data; public Node next; public Node prev; }; class LinkedList { Node head; public LinkedList(){ head = null; } //Add new element at the end of the list public 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 = new Node(); temp = head; while(temp.next != null) temp = temp.next; temp.next = newNode; newNode.prev = temp; } } //display the content of the list public void PrintList() { Node temp = new Node(); temp = this.head; if(temp != null) { Console.Write("The list contains: "); while(temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } else { Console.WriteLine("The list is empty."); } } }; // test the code class Implementation { static void Main(string[] args) { LinkedList MyList = new LinkedList(); //Add three elements at the end of the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.PrintList(); } }
The above code will give the following output:
The list contains: 10 20 30
<?php //node structure class Node { public $data; public $next; public $prev; } class LinkedList { public $head; public function __construct(){ $this->head = null; } //Add new element at the end of the list public function push_back($newElement) { $newNode = new Node(); $newNode->data = $newElement; $newNode->next = null; $newNode->prev = null; if($this->head == null) { $this->head = $newNode; } else { $temp = new Node(); $temp = $this->head; while($temp->next != null) { $temp = $temp->next; } $temp->next = $newNode; $newNode->prev = $temp; } } //display the content of the list public function PrintList() { $temp = new Node(); $temp = $this->head; if($temp != null) { echo "The list contains: "; while($temp != null) { echo $temp->data." "; $temp = $temp->next; } echo "\n"; } else { echo "The list is empty.\n"; } } }; // test the code $MyList = new LinkedList(); //Add three elements at the end of the list. $MyList->push_back(10); $MyList->push_back(20); $MyList->push_back(30); $MyList->PrintList(); ?>
The above code will give the following output:
The list contains: 10 20 30