#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
    Node* head = new Node(arr[0]);
    // Initialize 'prev' to the head node
    Node* prev = head;            

    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;       
    }
    // Return the head of the doubly linked list
    return head;  
}

// Function to print the elements of the doubly linked list
void print(Node* head) {
    while (head != nullptr) {
        // Print the data in the current node
        cout << head->data << " ";  
         // Move to the next node
        head = head->next;         
    }
}

// Function to insert new node before head
Node* insertBeforeHead(Node* head, int val){
    // Create new node with data as val
    Node* newHead = new Node(val , head, nullptr);
    head->back = newHead;
    
    return newHead;
}



int main() {
    vector<int> arr = {12, 5, 8, 7, 4};
    Node* head = convertArr2DLL(arr);
    
    print(head);
    cout << endl << "Doubly Linked List After Inserting 6 before head: " << endl;
    head = insertBeforeHead(head, 6);
    print(head);

    return 0;
}

Output:

12 5 8 7 4
Doubly Linked List After Inserting 6 before head: 
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.

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
        Node head = new Node(arr[0]); 
         // Initialize 'prev' to the head node
        Node prev = head;

        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; 
        }
         // Return the head of the doubly linked list
        return head;
    }
    

    private static void print(Node head) {
        while (head != null) {
            // Print the data in the current node
            System.out.print(head.data + " "); 
            // Move to the next node
            head = head.next; // Move to the next node
        }
        System.out.println();
    }
    
    private static Node insertBeforeHead(Node head, int val){
        // Create new node with data as val
        Node newHead = new Node(val, head, null);
        // Set old head's back pointer to the new Head
        head.back = newHead;
        // Return the new head
        return newHead;
    }
    



    public static void main(String[] args) {
        int[] arr = {12, 5, 6, 8, 4};
        // Convert the array to a doubly linked list
        Node head = convertArr2DLL(arr); 
        // Print the doubly linked list
        print(head); 
        
        System.out.println("Doubly Linked List After Inserting 6 before head: ");
        
        print(head);
    }
}

Output:

12 5 8 7 4
Doubly Linked List After Inserting 6 before head: 
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.

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
    head = Node(arr[0])
    # Initialize 'prev' to the head node
    prev = head

    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

    # Return the head of the doubly linked list
    return head

def print_dll(head):
    while head is not None:
        # Print the data in the current node
        print(head.data, end=" ")
        # Move to the next node
        head = head.next
    print()

def insert_before_head(head, val):
    # Create a new node with data as val and set its 'next' pointer to the old head
    new_head = Node(val, head, None)
    # Set the old head's 'back' pointer to the new head
    if head is not None:
        head.back = new_head
    # Return the new head
    return new_head

if __name__ == "__main__":
    arr = [12, 5, 6, 8, 4]
    # Convert the array to a doubly linked list
    head = convert_arr_to_dll(arr)
    # Print the doubly linked list
    print("Doubly Linked List:")
    print_dll(head)

    # Insert a node before the head
    val_to_insert = 6
    head = insert_before_head(head, val_to_insert)
    print("\nDoubly Linked List After Inserting", val_to_insert, "before head:")
    print_dll(head)

Output:

12 5 8 7 4
Doubly Linked List After Inserting 6 before head: 
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.

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

function convertArrayToDoublyLinkedList(arr) {
    // Create the head node with the first element of the array
    let head = new Node(arr[0]);
    // Initialize 'prev' to the head node
    let prev = head;

    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;
    }

    // Return the head of the doubly linked list
    return head;
}

function printDoublyLinkedList(head) {
    while (head !== null) {
        // Print the data in the current node
        process.stdout.write(head.data + " ");
        // Move to the next node
        head = head.next;
    }
    console.log();
}

function insertBeforeHead(head, val) {
    // Create a new node with data as val and set its 'next' pointer to the old head
    const newHead = new Node(val, head, null);
    // Set the old head's 'back' pointer to the new head
    if (head !== null) {
        head.back = newHead;
    }
    // Return the new head
    return newHead;
}

const arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
let head = convertArrayToDoublyLinkedList(arr);
// Print the doubly linked list
console.log("Doubly Linked List:");
printDoublyLinkedList(head);

// Insert a node before the head
const valToInsert = 6;
head = insertBeforeHead(head, valToInsert);
console.log("\nDoubly Linked List After Inserting", valToInsert, "before head:");
printDoublyLinkedList(head);

Output:

12 5 8 7 4
Doubly Linked List After Inserting 6 before head: 
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.