Problem Statement: Given a doubly linked list and an integer value, insert a new node with that value at the beginning (before the head) of the list. Return the updated head of the list.

Examples
```Example 1:
Input Format:DLL: 1 <-> 2 <-> 3Value to be Inserted : 0

Result: DLL: 0 <-> 1 <-> 2 <-> 3

Explanation: We need to insert the value 0 before the head of the given Doubly Linked List.
Example 2:
Input Format:
DLL: 5Value to be Inserted: 7

Result: DLL: 7 <-> 5

Explanation: In this case, the DLL initially contains only one node with a value of 5. We insert the value 7 before the head of the DLL, resulting in a DLL with two nodes.
```

### Solution

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

### Approach:

To insert a new node with a given value before the head of a doubly linked list, create a new node with its back pointer set to null and its front pointer pointing to the current head. Then, update the current head’s back pointer to point to the new node. Finally, return the new node as the updated head of the doubly linked list.

### Algorithm:

Step 1: Create a new node with the given value and set its back pointer to null and front pointer to the current head.

Step 2: Update the current head‘s back pointer to point to the new node.

Code:

## C++ Code

``````#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Define a Node class for doubly linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list (forward direction)
Node* next;
// Pointer to the previous node in the list (backward direction)
Node* back;

// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
Node(int data1, Node* next1, Node* back1) {
data = data1;
next = next1;
back = back1;
}

// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
Node(int data1) {
data = data1;
next = nullptr;
back = nullptr;
}
};

// Function to convert an array to a doubly linked list
Node* convertArr2DLL(vector<int> arr) {
// Create the head node with the first element of the array
// Initialize 'prev' to the head node

for (int i = 1; i < arr.size(); i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node* temp = new Node(arr[i], nullptr, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev->next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
}

// Function to print the elements of the doubly linked list
// Print the data in the current node
cout << head->data << " ";
// Move to the next node
}
}

// Function to insert new node before head
// Create new node with data as val

}

int main() {
vector<int> arr = {12, 5, 8, 7, 4};

cout << endl << "Doubly Linked List After Inserting 6 before head: " << endl;

return 0;
}
``````

Output:

12 5 8 7 4
6 12 5 8 7 4

Time Complexity: O(1) The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1)  The space complexity is also O(1) because a constant amount of extra space is used to create the new node.

## Java Code

``````public class DLinkedList {
public static class Node {
// Data stored in the node
public int data;
// Reference to the next node in the list (forward direction)
public Node next;
// Reference to the previous node in the list (backward direction)
public Node back;

// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
public Node(int data1, Node next1, Node back1) {
data = data1;
next = next1;
back = back1;
}

// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
public Node(int data1) {
data = data1;
next = null;
back = null;
}
}
private static Node convertArr2DLL(int[] arr) {
// Create the head node with the first element of the array
// Initialize 'prev' to the head node

for (int i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node temp = new Node(arr[i], null, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev.next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
}

private static void print(Node head) {
// Print the data in the current node
// Move to the next node
}
System.out.println();
}

// Create new node with data as val
}

public static void main(String[] args) {
int[] arr = {12, 5, 6, 8, 4};
// Convert the array to a doubly linked list
// Print the doubly linked list

}
}
``````

Output:

12 5 8 7 4
6 12 5 8 7 4

Time Complexity: O(1) The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1)  The space complexity is also O(1) because a constant amount of extra space is used to create the new node.

## Python Code

``````class Node:
def __init__(self, data, next_node=None, back_node=None):
self.data = data
self.next = next_node
self.back = back_node

def convert_arr_to_dll(arr):
# Create the head node with the first element of the array
# Initialize 'prev' to the head node

for i in range(1, len(arr)):
# Create a new node with data from the array and set its 'back' pointer to the previous node
temp = Node(arr[i], None, prev)
# Update the 'next' pointer of the previous node to point to the new node
prev.next = temp
# Move 'prev' to the newly created node for the next iteration
prev = temp

# Print the data in the current node
# Move to the next node
print()

# Create a new node with data as val and set its 'next' pointer to the old head

if __name__ == "__main__":
arr = [12, 5, 6, 8, 4]
# Convert the array to a doubly linked list
# Print the doubly linked list

# Insert a node before the head
val_to_insert = 6
``````

Output:

12 5 8 7 4
6 12 5 8 7 4

Time Complexity: O(1) The time complexity of this insertion operation is O(1) because only a constant number of pointer updates are being performed regardless of the size of the Doubly Linked List.

Space Complexity: O(1)  The space complexity is also O(1) because a constant amount of extra space is used to create the new node.

## JavaScript Code

``````class Node {
constructor(data, nextNode = null, backNode = null) {
this.data = data;
this.next = nextNode;
this.back = backNode;
}
}

// Create the head node with the first element of the array
// Initialize 'prev' to the head node

for (let i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
const temp = new Node(arr[i], null, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev.next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}

}

// Print the data in the current node
// Move to the next node
}
console.log();
}

// Create a new node with data as val and set its 'next' pointer to the old head
}
}

const arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
// Print the doubly linked list

// Insert a node before the head
const valToInsert = 6;
``````

Output:

12 5 8 7 4