Facebook Page Twitter Page LinkedIn Page
× C# Data Structures - Doubly Linked List Other Related Topics


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.

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.");
    }       
  }
} 

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

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("\nThe list contains: ");
      while(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
    } else {
      Console.Write("\nThe 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