#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 before the Kth element 
Node* insertBeforeKthElement(Node* head, int k, int val){
    
    if(k==1){
        // K = 1 means node has to be insert before the head
        return insertBeforeHead(head, val);
    }
    
    // temp will keep track of the node
    Node* temp = head;
    
    // count so that the Kth element can be reached
    int count = 0;
    while(temp!=NULL){
        count ++;
        // On reaching the Kth position, break out of the loop
        if(count == k) break;
        // keep moving temp forward till count != K
        temp = temp->next;
    }
    // track the node before the Kth node
    Node* prev = temp->back;
    
    // create new node with data as val
    Node* newNode = new Node(val, temp, prev);
    
    //join the new node in between prev and temp
    prev->next = newNode;
    temp->back = newNode;
    
    // Set newNode's pointers to prev and temp
    newNode->next = temp;
    newNode->back = prev;
    
    // Return the head of the updated doubly linked list
    return head;
}

// Function to insert a new node before a given node 
void insertBeforeNode(Node*node, int val){
    // Get the node before the given node
    Node* prev = node->back;
    
    // Create a new node with the given val
    Node* newNode = new Node(val, node, prev);
    
    // Connect the newNode to the doubly linked List
    prev->next = newNode;
    node->back = newNode;
    
    // void function to just update
    return;
}


int main() {
    vector<int> arr = {12, 5, 8, 7, 4};
    Node* head = convertArr2DLL(arr);
    
    print(head);
    cout << endl << "Doubly Linked List After Inserting before the node with value 8: " << endl;
    insertBeforeNode(head->next->next, 100);
    print(head);

    return 0;
}

Output:

12 5 8 7 4 
Doubly Linked List After Inserting before the node with value 8: 
12 5 100 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();
    }

    // Function to insert a new node before a given node
    private static void insertBeforeNode(Node node, int val) {
        // Get the node before the given node
        Node prev = node.back;

        // Create a new node with the given val
        Node newNode = new Node(val, node, prev);

        // Connect the newNode to the doubly linked list
        prev.next = newNode;
        node.back = newNode;

    }

    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 before the node with value 8:");

        insertBeforeNode(head.next.next, 100);
        print(head);
    }
}

Output:

12 5 8 7 4 
Doubly Linked List After Inserting before the node with value 8: 
12 5 100 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 DLinkedList:
    class Node:
        def __init__(self, data, next_node=None, back_node=None):
            # Data stored in the node
            self.data = data
            # Reference to the next node in the list (forward direction)
            self.next = next_node
            # Reference to the previous node in the list (backward direction)
            self.back = back_node

    @staticmethod
    def convertArr2DLL(arr):
        # Create the head node with the first element of the array
        head = DLinkedList.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 = DLinkedList.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

    @staticmethod
    def print_linked_list(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()

    @staticmethod
    def insert_before_node(node, val):
        # Get the node before the given node
        prev = node.back

        # Create a new node with the given val
        new_node = DLinkedList.Node(val, node, prev)

        # Connect the new_node to the doubly linked list
        prev.next = new_node
        node.back = new_node

if __name__ == "__main__":
    arr = [12, 5, 6, 8, 4]
    # Convert the array to a doubly linked list
    head = DLinkedList.convertArr2DLL(arr)
    # Print the doubly linked list
    DLinkedList.print_linked_list(head)

    print("Doubly Linked List After Inserting before the node with value 8:")

    # Insert a new node before the node with value 8
    DLinkedList.insert_before_node(head.next.next, 100)
    # Print the updated doubly linked list
    DLinkedList.print_linked_list(head)

Output:

12 5 8 7 4 
Doubly Linked List After Inserting before the node with value 8: 
12 5 100 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 {
    // Data stored in the node
    constructor(data1, next1, back1) {
        this.data = data1;
        this.next = next1;
        this.back = back1;
    }

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

function convertArr2DLL(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
        let 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 print(head) {
    while (head !== null) {
        // Print the data in the current node
        console.log(head.data + " ");
        // Move to the next node
        head = head.next; // Move to the next node
    }
    console.log();
}

// Function to insert a new node before a given node
function insertBeforeNode(node, val) {
    // Get the node before the given node
    let prev = node.back;

    // Create a new node with the given val
    let newNode = new Node(val, node, prev);

    // Connect the newNode to the doubly linked list
    prev.next = newNode;
    node.back = newNode;
}

// Main function
let arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
let head = convertArr2DLL(arr);
// Print the doubly linked list
print(head);

console.log("Doubly Linked List After Inserting before the node with value 8:");

insertBeforeNode(head.next.next, 100);
print(head);

Output:

12 5 8 7 4 
Doubly Linked List After Inserting before the node with value 8: 
12 5 100 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