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

Doubly Linked List - Insert a new node at the given position

In this method, a new element is inserted at the specified position in the doubly linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.

First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not. In case of null, the specified position does not exist. In other case, update the links. The below figure describes the process, if the insert node is other than the head node.

Doubly Linked List - Add Node At End

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

void push_at(int newElement, int position) {
  
  //1. allocate node to new element
  Node* newNode = new Node(); 
  newNode->data = newElement;
  newNode->next = NULL;
  newNode->prev = NULL;

  //2. check if the position is > 0
  if(position < 1) {
    cout<<"\nposition should be >= 1.";
  } else if (position == 1) {
  
  //3. if the position is 1, make new node as head
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
  } else {

   //4. Else, make a temp node and traverse to the 
   //   node previous to the position
    Node* temp = head;
    for(int i = 1; i < position-1; i++) {
      if(temp != NULL) {
        temp = temp->next;
      }
    }
 
    //5. If the previous node is not null, adjust 
    //   the links
    if(temp != NULL) {
      newNode->next = temp->next;
      newNode->prev = temp;
      temp->next = newNode;
      if(newNode->next != NULL)
        newNode->next->prev = newNode;  
    } else {
      
      //6. When the previous node is null
      cout<<"\nThe previous node is null.";
    } 
  }
}

void push_at(struct Node** head_ref, int newElement, int position) {     
  
  //1. allocate node to new element
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;
  newNode->next = NULL;
  newNode->prev = NULL;

  //2. check if the position is > 0
  if(position < 1) {
    printf("\nposition should be >= 1.");
  } else if (position == 1) {
    
    //3. if the position is 1, make new node as head
    newNode->next = *head_ref;
    (*head_ref)->prev = newNode;
    *head_ref = newNode;
  } else {
    
    //4. Else, make a temp node and traverse to the 
    //   node previous to the position
    temp = *head_ref;
    for(int i = 1; i < position-1; i++) {
      if(temp != NULL) {
        temp = temp->next;
      }
    }
 
    //5. If the previous node is not null, adjust 
    //   the links
    if(temp != NULL) {
      newNode->next = temp->next;
      newNode->prev = temp;
      temp->next = newNode; 
      if(newNode->next != NULL)
        newNode->next->prev = newNode;  
    } else {
      
      //6. When the previous node is null
      printf("\nThe previous node is null.");
    }       
  }
}      

def push_at(self, newElement, position):     
  
  #1. allocate node to new element
  newNode = Node(newElement)

  #2. check if the position is > 0 
  if(position < 1):
    print("\nposition should be >= 1.")
  elif (position == 1):
    
    #3. if the position is 1, make new node as head
    newNode.next = self.head
    self.head.prev = newNode
    self.head = newNode
  else:    
    
    #4. Else, make a temp node and traverse to the 
    #   node previous to the position
    temp = self.head
    for i in range(1, position-1):
      if(temp != None):
        temp = temp.next   
    
    #5. If the previous node is not null, adjust 
    #   the links
    if(temp != None):
      newNode.next = temp.next
      newNode.prev = temp
      temp.next = newNode  
      if (newNode.next != None):
        newNode.next.prev = newNode
    else:
      
      #6. When the previous node is null
      print("\nThe previous node is null.")

void push_at(int newElement, int position) {     
  
  //1. allocate node to new element
  Node newNode = new Node(); 
  newNode.data = newElement;
  newNode.next = null;
  newNode.prev = null;

  //2. check if the position is > 0
  if(position < 1) {
    System.out.print("\nposition should be >= 1.");
  } else if (position == 1) {
    
    //3. if the position is 1, make new node as head
    newNode.next = head;
    head.prev = newNode;
    head = newNode;
  } else {
    
    //4. Else, make a temp node and traverse to the 
    //   node previous to the position
    Node temp = new Node();
    temp = head;
    for(int i = 1; i < position-1; i++) {
      if(temp != null) {
        temp = temp.next;
      }
    }
 
    //5. If the previous node is not null, adjust 
    //   the links
    if(temp != null) {
      newNode.next = temp.next;
      newNode.prev = temp;
      temp.next = newNode;  
      if(newNode.next != null)
        newNode.next.prev = newNode;
    } else {
      
      //6. When the previous node is null
      System.out.print("\nThe previous node is null.");
    }       
  }
}  

public void push_at(int newElement, int position) {     
  
  //1. allocate node to new element
  Node newNode = new Node(); 
  newNode.data = newElement;
  newNode.next = null;
  newNode.prev = null;

  //2. check if the position is > 0
  if(position < 1) {
    Console.Write("\nposition should be >= 1.");
  } else if (position == 1) {
    
    //3. if the position is 1, make new node as head
    newNode.next = head;
    head.prev = newNode;
    head = newNode;
  } else {
    
    //4. Else, make a temp node and traverse to the 
    //   node previous to the position
    Node temp = new Node();
    temp = head;
    for(int i = 1; i < position-1; i++) {
      if(temp != null) {
        temp = temp.next;
      }
    }
 
    //5. If the previous node is not null, adjust 
    //   the links
    if(temp != null) {
      newNode.next = temp.next;
      newNode.prev = temp;
      temp.next = newNode; 
      if(newNode.next != null)
        newNode.next.prev = newNode; 
    } else {
      
      //6. When the previous node is null
      Console.Write("\nThe previous node is null.");
    }       
  }
} 

public function push_at($newElement, $position) {     
  
  //1. allocate node to new element
  $newNode = new Node(); 
  $newNode->data = $newElement;
  $newNode->next = null;
  $newNode->prev = null;

  //2. check if the position is > 0
  if($position < 1) {
    echo "\nposition should be >= 1.";
  } else if ($position == 1) {
    
    //3. if the position is 1, make new node as head
    $newNode->next = $this->head;
    $this->head->prev = $newNode;
    $this->head = $newNode;
  } else {
    
    //4. Else, make a temp node and traverse to the 
    //   node previous to the position
    $temp = new Node();
    $temp = $this->head;
    for($i = 1; $i < $position-1; $i++) {
      if($temp != null) {
        $temp = $temp->next;
      }
    }
 
    //5. If the previous node is not null, adjust 
    //   the links
    if($temp != null) {
      $newNode->next = $temp->next;
      $newNode->prev = $temp;
      $temp->next = $newNode; 
      if($newNode->next != null)
        $newNode->next->prev = $newNode; 
    } else {
      
      //6. When the previous node is null
      echo "\nThe previous node is null.";
    }       
  }
}

The below is a complete program that uses above discussed concept to insert new node at a given position in 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;
      }    
    }

    //Inserts a new element at the given position 
    void push_at(int newElement, int position) {
      Node* newNode = new Node(); 
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL;
      if(position < 1) {
        cout<<"\nposition should be >= 1.";
      } else if (position == 1) {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
      } else {
        Node* temp = head;
        for(int i = 1; i < position-1; i++) {
          if(temp != NULL) {
            temp = temp->next;
          }
        }
        if(temp != NULL) {
          newNode->next = temp->next;
          newNode->prev = temp;
          temp->next = newNode;
          if(newNode->next != NULL)
            newNode->next->prev = newNode;  
        } else {
          cout<<"\nThe previous node is null.";
        } 
      }
    }

    //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 in the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.PrintList();

  //Insert an element at position 2
  MyList.push_at(100, 2);
  MyList.PrintList();

  //Insert an element at position 1
  MyList.push_at(200, 1);  
  MyList.PrintList();  
  
  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 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;
  }
}

//Inserts a new element at the given position
void push_at(struct Node** head_ref, int newElement, int position) {     
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;
  newNode->next = NULL;
  newNode->prev = NULL;
  if(position < 1) {
    printf("\nposition should be >= 1.");
  } else if (position == 1) {
    newNode->next = *head_ref;
    (*head_ref)->prev = newNode;
    *head_ref = newNode;
  } else {
    temp = *head_ref;
    for(int i = 1; i < position-1; i++) {
      if(temp != NULL) {
        temp = temp->next;
      }
    }
    if(temp != NULL) {
      newNode->next = temp->next;
      newNode->prev = temp;
      temp->next = newNode; 
      if(newNode->next != NULL)
        newNode->next->prev = newNode;   
    } else {
      printf("\nThe previous node is null.");
    }       
  }
}   

//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 in the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  PrintList(MyList);

  //Insert an element at position 2
  push_at(&MyList, 100, 2);
  PrintList(MyList);  

  //Insert an element at position 1
  push_at(&MyList, 200, 1);
  PrintList(MyList); 

  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 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

  #Inserts a new element at the given position
  def push_at(self, newElement, position):     
    newNode = Node(newElement)
    if(position < 1):
      print("\nposition should be >= 1.")
    elif (position == 1):
      newNode.next = self.head
      self.head.prev = newNode
      self.head = newNode
    else:    
      temp = self.head
      for i in range(1, position-1):
        if(temp != None):
          temp = temp.next   
      if(temp != None):
        newNode.next = temp.next
        newNode.prev = temp
        temp.next = newNode  
        if (newNode.next != None):
          newNode.next.prev = newNode
      else:
        print("\nThe previous node is null.")  

  #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 in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()

#Insert an element at position 2
MyList.push_at(100, 2)
MyList.PrintList()

#Insert an element at position 1
MyList.push_at(200, 1)
MyList.PrintList()

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 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;
    }    
  }

  //Inserts a new element at the given position
  void push_at(int newElement, int position) {     
    Node newNode = new Node(); 
    newNode.data = newElement;
    newNode.next = null;
    newNode.prev = null;
    if(position < 1) {
      System.out.print("\nposition should be >= 1.");
    } else if (position == 1) {
      newNode.next = head;
      head.prev = newNode;
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      for(int i = 1; i < position-1; i++) {
        if(temp != null) {
          temp = temp.next;
        }
      }
      if(temp != null) {
        newNode.next = temp.next;
        newNode.prev = temp;
        temp.next = newNode;  
        if(newNode.next != null)
          newNode.next.prev = newNode;
      } else {
        System.out.print("\nThe previous node is null.");
      }       
    }
  }  

  //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 in the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.PrintList();

    //Insert an element at position 2
    MyList.push_at(100, 2);
    MyList.PrintList();

    //Insert an element at position 1
    MyList.push_at(200, 1);
    MyList.PrintList();    
  }
}

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 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;
    }    
  }

  //Inserts a new element at the given position
  public void push_at(int newElement, int position) {     
    Node newNode = new Node(); 
    newNode.data = newElement;
    newNode.next = null;
    newNode.prev = null;
    if(position < 1) {
      Console.Write("\nposition should be >= 1.");
    } else if (position == 1) {
      newNode.next = head;
      head.prev = newNode;
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      for(int i = 1; i < position-1; i++) {
        if(temp != null) {
          temp = temp.next;
        }
      }
      if(temp != null) {
        newNode.next = temp.next;
        newNode.prev = temp;
        temp.next = newNode; 
        if(newNode.next != null)
          newNode.next.prev = newNode; 
      } else {
        Console.Write("\nThe previous node is null.");
      }       
    }
  } 

  //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 in the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.PrintList(); 

    //Insert an element at position 2
    MyList.push_at(100, 2);
    MyList.PrintList();

    //Insert an element at position 1
    MyList.push_at(200, 1);
    MyList.PrintList();   
  }
}

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 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;
    }    
  }

  //Inserts a new element at the given position
  public function push_at($newElement, $position) {     
    $newNode = new Node(); 
    $newNode->data = $newElement;
    $newNode->next = null;
    $newNode->prev = null;
    if($position < 1) {
      echo "\nposition should be >= 1.";
    } else if ($position == 1) {
      $newNode->next = $this->head;
      $this->head->prev = $newNode;
      $this->head = $newNode;
    } else {
      $temp = new Node();
      $temp = $this->head;
      for($i = 1; $i < $position-1; $i++) {
        if($temp != null) {
          $temp = $temp->next;
        }
      }
      if($temp != null) {
        $newNode->next = $temp->next;
        $newNode->prev = $temp;
        $temp->next = $newNode; 
        if($newNode->next != null)
          $newNode->next->prev = $newNode; 
      } else {
        echo "\nThe previous node is null.";
      }       
    }
  }  

  //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 in the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->PrintList();

//Insert an element at position 2
$MyList->push_at(100, 2);
$MyList->PrintList();

//Insert an element at position 1
$MyList->push_at(200, 1);
$MyList->PrintList();  
?>

The above code will give the following output: 

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30
AlphaCodingSkills
AlphaCodingSkills Android App
Facebook Page Twitter Page LinkedIn Page
Learning Tutorials
Learning Tutorials
Useful Links
Python Libraries
About Us  |  Privacy Policy  |  Contact Us
AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.