Insert at front of a Doubly Linked List

Problem Statement: Given a doubly-linked list, insert a node at the begin of the doubly linked list.

Examples:

Example 1:
Input:  List : 1 <--> 2 <--> 3 <--> 4 <--> 5
	K :  6
Output: List :  6 <--> 1 <--> 2 <--> 3 <--> 4 <--> 5
Explanation: the value given in k is inserted at 
the font of the doubly linked lists.

Example 2:
Input:  List : null
	K : 2
Output:	List : 2
Explanation: The list is empty so it will become 
the first node.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition:

To insert at the front of the linked list we can point the new node where the head pointer points and point the previous new node to the head. Then put the head pointer towards the new node.

Approach:

To insert at the first of the linked list, we will first create a new node. The new node is always added before the head of the given Linked List. And newly added node becomes the new head of DLL.

There are four steps:

create a new node .
assign the next of node to head pointer.
if head is not null then, Assign the prev of head to the new node.
assign head to the new node

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;

class node              // creating a node
{
  public:
    int data;
  node * next;
  node * prev;
  node(int val) {
    data = val;
    next = NULL;
    prev = NULL;
  }
};

void insertAtHead(node * & head, int val) {
  node * ptr = new node(val);
  ptr -> next = head;
  if (head != NULL) {
    head -> prev = ptr;
  }
  head = ptr;
}

void display(node * head)               // to print the linked list
{
  node * temp = head;
  while (temp != NULL) {
    cout << temp -> data << "<-->";
    temp = temp -> next;
  }
  cout << "NULL\n";
}

int main() {
  node* head=NULL;
  insertAtHead(head,1);
  insertAtHead(head,2);
  insertAtHead(head,3);
  insertAtHead(head,4);
  insertAtHead(head,5);
  display(head);

}

Output: 5<–>4<–>3<–>2<–>1<–>NULL

Time Complexity: O(1), as we are inserting in the front so we are not traversing through the list

Space Complexity: O(1), as we do not need extra space to store the node.

Java Code

import java.util.*;

class Node              // creating a node
{
  int data;
  Node  next;
  Node  prev;
  Node(int val) {
    data = val;
    next = null;
    prev = null;
  }
}

class TUF{
static Node insertAtHead(Node head, int val) {
  Node  ptr = new Node(val);
  ptr . next = head;
  if (head != null) {
    head . prev = ptr;
  }
  head = ptr;
  return head;
}

static void display(Node head)               // to print the linked list
{
  Node  temp = head;
  while (temp != null) {
    System.out.print(temp.data+"<-->");
    temp = temp . next;
  }
    System.out.println("NULL");
}

public static void main(String args[]) {
  Node head=null;
  head = insertAtHead(head,1);
  head = insertAtHead(head,2);
  head = insertAtHead(head,3);
  head = insertAtHead(head,4);
  head = insertAtHead(head,5);
  display(head);

}
}

Output: 5<–>4<–>3<–>2<–>1<–>NULL

Time Complexity: O(1), as we are inserting in the front so we are not traversing through the list

Space Complexity: O(1), as we do not need extra space to store the node.

Special thanks to Ayush Pandey for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article