Data Structures - Doubly Linked List Other Related Topics

Doubly Linked List - Insert a new node at the start



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

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

Doubly Linked List - Add Node At Start

The function push_front is created for this purpose. It is a 5-step process.

void push_front(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. Adjust the links and make the new
    //   node as head
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
  }    
}
void push_front(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. Adjust the links and make the new
    //   node as head
    (*head_ref)->prev = newNode;
    newNode->next = *head_ref;
    *head_ref = newNode;
  }
}
def push_front(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. Adjust the links and make the new
    #   node as head 
    self.head.prev = newNode
    newNode.next = self.head
    self.head = newNode
void push_front(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. Adjust the links and make the new
    //   node as head
    head.prev = newNode;
    newNode.next = head;
    head = newNode;
  }    
}
public void push_front(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. Adjust the links and make the new
    //   node as head
    head.prev = newNode;
    newNode.next = head;
    head = newNode;
  }    
}
public function push_front($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. Adjust the links and make the new
    //   node as head
    $this->head->prev = $newNode;
    $newNode->next = $this->head;
    $this->head = $newNode;
  }    
}

The below is a complete program that uses above discussed concept to insert new node at the start 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 start of the list
    void push_front(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
      } else {
        head->prev = newNode;
        newNode->next = head;
        head = newNode;
      }    
    }

    //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 start of the list.
  MyList.push_front(10);
  MyList.push_front(20);
  MyList.push_front(30);
  MyList.PrintList();
  
  return 0; 
}

The above code will give the following output:

The list contains: 30 20 10  
#include <stdio.h>
#include <stdlib.h>

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

//Add new element at the start of the list
void push_front(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 {  
    (*head_ref)->prev = newNode;
    newNode->next = *head_ref;
    *head_ref = newNode;
  }
}

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

  return 0; 
}

The above code will give the following output:

The list contains: 30 20 10  
# 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 start of the list
  def push_front(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      return
    else:
      self.head.prev = newNode
      newNode.next = self.head
      self.head = newNode

  #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 start of the list.
MyList.push_front(10)
MyList.push_front(20)
MyList.push_front(30)
MyList.PrintList()

The above code will give the following output:

The list contains: 30 20 10  
//node structure
class Node {
    int data;
    Node next;
    Node prev;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the start of the list
  void push_front(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null;
    newNode.prev = null; 
    if(head == null) {
      head = newNode;
    } else {
      head.prev = newNode;
      newNode.next = head;
      head = newNode;
    }    
  }

  //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 start of the list.
    MyList.push_front(10);
    MyList.push_front(20);
    MyList.push_front(30);
    MyList.PrintList(); 
  }
}

The above code will give the following output:

The list contains: 30 20 10  
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 start of the list
  public void push_front(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    newNode.prev = null;
    if(head == null) {
      head = newNode;
    } else {
      head.prev = newNode;
      newNode.next = head;
      head = newNode;
    }    
  }

  //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 start of the list.
    MyList.push_front(10);
    MyList.push_front(20);
    MyList.push_front(30);
    MyList.PrintList();   
  }
}

The above code will give the following output:

The list contains: 30 20 10  
<?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 start of the list
  public function push_front($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null;
    $newNode->prev = null; 
    if($this->head == null) {
      $this->head = $newNode;
    } else {
      $this->head->prev = $newNode;
      $newNode->next = $this->head;
      $this->head = $newNode;
    }    
  }

  //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 start of the list.
$MyList->push_front(10);
$MyList->push_front(20);
$MyList->push_front(30);
$MyList->PrintList();
?>

The above code will give the following output:

The list contains: 30 20 10