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

// This function was explain in prevoius articles 
// Please refer there
// 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;
}


// This function was explain in prevoius articles 
// Please refer there
Node* insertBeforeTail(Node* head, int val){
    // Edge case, if dll has only one elements
    if(head->next==NULL){
        // If only one element
        return insertBeforeHead(head, val);
    }
    
    // Create pointer tail to traverse to the end of list
    Node* tail = head;
    while(tail->next!=NULL){
        tail = tail->next;
    }
    // Keep track of node before tail using prev
    Node* prev = tail->back;
    
    // Create new node with value val
    Node* newNode = new Node(val, tail, prev);
    
    // Join the new node into the doubly linked list
    prev->next = newNode;
    tail->back = newNode;
    
    // Return the updated linked list
    return head;
}


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


int main() {
    vector<int> arr = {12, 5, 8, 7, 4};
    Node* head = convertArr2DLL(arr);
    
    print(head);
    cout << endl << "Doubly Linked List After Inserting val on the kth position: " << endl;
    head = insertBeforeKthElement(head, 2, 10);
    print(head);

    return 0;
}

Output:

12 5 8 7 4 
Doubly Linked List After Inserting 6 before tail: 
12 10 5 8 7 4

Time Complexity: O(K) The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

Space Complexity: O(1) The space complexity is also O(1) because we are using a constant amount of extra space 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;
    }
    
    private static Node insertBeforeTail(Node head, int val){
    // Edge case, if dll has only one elements
    if(head.next==null){
        // If only one element
        return insertBeforeHead(head, val);
    }
    
    // Create pointer tail to traverse to the end of list
    Node tail = head;
    while(tail.next!=null){
        tail = tail.next;
    }
    // Keep track of node before tail using prev
    Node prev = tail.back;
    
    // Create new node with value val
    Node newNode = new Node(val, tail, prev);
    
    // Join the new node into the doubly linked list
    prev.next = newNode;
    tail.back = newNode;
    
    // Return the updated linked list
    return head;
    }
    
    // Function to insert before the Kth node 
    private static 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;
}
    



    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 val on the kth position: ");
        
        head = insertBeforeKthElement(head, 2, 10);
        print(head);
    }
}

Output:

12 5 8 7 4 
Doubly Linked List After Inserting 6 before tail: 
12 10 5 8 7 4

Time Complexity: O(K) The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

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

class Node:
    def __init__(self, data1, next1=None, back1=None):
        # Data stored in the node
        self.data = data1
        # Reference to the next node in the list (forward direction)
        self.next = next1
        # Reference to the previous node in the list (backward direction)
        self.back = back1

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 new node with data as val
    new_head = Node(val, head)
    # Set old head's back pointer to the new Head
    head.back = new_head
    # Return the new head
    return new_head

def insert_before_tail(head, val):
    # Edge case, if dll has only one element
    if head.next is None:
        # If only one element
        return insert_before_head(head, val)

    # Create pointer tail to traverse to the end of list
    tail = head
    while tail.next is not None:
        tail = tail.next
    # Keep track of node before tail using prev
    prev = tail.back

    # Create new node with value val
    new_node = Node(val, tail, prev)

    # Join the new node into the doubly linked list
    prev.next = new_node
    tail.back = new_node

    # Return the updated linked list
    return head

def insert_before_kth_element(head, k, val):
    if k == 1:
        # K = 1 means node has to be inserted before the head
        return insert_before_head(head, val)

    # temp will keep track of the node
    temp = head

    # count so that the Kth element can be reached
    count = 0
    while temp is not None:
        count += 1
        # 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
    prev = temp.back

    # create new node with data as val
    new_node = Node(val, temp, prev)

    # join the new node in between prev and temp
    prev.next = new_node
    temp.back = new_node

    # Set newNode's pointers to prev and temp
    new_node.next = temp
    new_node.back = prev

    # Return the head of the updated doubly linked list
    return 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("Original Doubly Linked List:")
    print_dll(head)

    print("\nDoubly Linked List After Inserting 10 before the 2nd position:")
    head = insert_before_kth_element(head, 2, 10)
    print_dll(head)

Output:

12 5 8 7 4 
Doubly Linked List After Inserting 6 before tail: 
12 10 5 8 7 4

Time Complexity: O(K) The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

Space Complexity: O(1) The space complexity is also O(1) because we are using a constant amount of extra space 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 to convert an array to a doubly linked list
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 to print the elements of the doubly linked list
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;
    }
    console.log();
}

// Function to insert before the Kth node
function insertBeforeKthElement(head, k, val) {
    if (k === 1) {
        // K = 1 means node has to be inserted before the head
        return insertBeforeHead(head, val);
    }

    // temp will keep track of the node
    let temp = head;

    // count so that the Kth element can be reached
    let 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
    let prev = temp.back;

    // create a new node with data as val
    let 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 before the head of the doubly linked list
function insertBeforeHead(head, val) {
    // Create a new node with data as val
    let newHead = new Node(val, head, null);
    // Set the old head's back pointer to the new Head
    head.back = newHead;
    // Return the new head
    return newHead;
}

// Function to insert before the tail of the doubly linked list
function insertBeforeTail(head, val) {
    // Edge case, if dll has only one element
    if (head.next === null) {
        // If only one element
        return insertBeforeHead(head, val);
    }

    // Create a pointer tail to traverse to the end of the list
    let tail = head;
    while (tail.next !== null) {
        tail = tail.next;
    }
    // Keep track of the node before tail using prev
    let prev = tail.back;

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

    // Join the new node into the doubly linked list
    prev.next = newNode;
    tail.back = newNode;

    // Return the updated linked list
    return head;
}

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

// Print the doubly linked list
console.log("Original Doubly Linked List:");
print(head);

console.log("Doubly Linked List After Inserting 10 before the 2nd position:");
head = insertBeforeKthElement(head, 2, 10);
print(head);

Output:

12 5 8 7 4 
Doubly Linked List After Inserting 6 before tail: 
12 10 5 8 7 4

Time Complexity: O(K) The time complexity of this operation is O(K) in the worst case because it may involve traversing K nodes in the Doubly Linked List to reach the Kth element. In the best case, when K is 0 (insertion at the head), the time complexity is O(1) as it involves a constant number of operations. In the average case, it’s O(K).

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