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

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



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 tail: " << endl;
    head = insertBeforeTail(head, 6);
    print(head);

    return 0;
}

Output:

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

Time Complexity: O(n) The time complexity of this insertion operation is O(n) because we have to traverse the entire list to reach i’s tail. The complexity would be O(1) if we were given the tail node to start with.

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



    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 tail: ");
        
        head = insertBeforeTail(head, 6);
        print(head);
    }
}

Output:

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

Time Complexity: O(n) The time complexity of this insertion operation is O(n) because we have to traverse the entire list to reach i’s tail. The complexity would be O(1) if we were given the tail node to start with.

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.

# Define a Node class for a doubly linked list
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

# Function to convert an array to a doubly linked list
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

# Function to print the elements of the doubly linked list
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()

# Function to insert a new node before the head of the doubly linked list
def insert_before_head(head, val):
    # Create a new node with data as val
    new_head = Node(val, head, None)
    head.back = new_head
    return new_head

# Function to insert a new node before the tail of the doubly linked list
def insert_before_tail(head, val):
    # Edge case: if the DLL has only one element
    if head.next is None:
        # If only one element, insert before the head
        return insert_before_head(head, val)

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

    # Create a 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

# Main function
if __name__ == "__main__":
    arr = [12, 5, 8, 7, 4]
    head = convert_arr_to_dll(arr)

    print_dll(head)
    print("Doubly Linked List After Inserting 6 before tail:")
    head = insert_before_tail(head, 6)
    print_dll(head)

Output:

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

Time Complexity: O(n) The time complexity of this insertion operation is O(n) because we have to traverse the entire list to reach i’s tail. The complexity would be O(1) if we were given the tail node to start with.

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.

// Define a Node class for doubly linked list
class Node {
    constructor(data, next = null, back = null) {
        // Data stored in the node
        this.data = data;
        // Pointer to the next node in the list (forward direction)
        this.next = next;
        // Pointer to the previous node in the list (backward direction)
        this.back = back;
    }
}

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

// Function to insert a new node before the head
function insertBeforeHead(head, val) {
    // Create a new node with data as val
    let newHead = new Node(val, head, null);
    head.back = newHead;

    return newHead;
}

// Function to insert a new node before the tail
function insertBeforeTail(head, val) {
    // Edge case: if DLL has only one element
    if (head.next === null) {
        // If only one element, insert before the head
        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;
}

const arr = [12, 5, 8, 7, 4];
let head = convertArr2DLL(arr);

print(head);
console.log("\nDoubly Linked List After Inserting 6 before tail: ");
head = insertBeforeTail(head, 6);
print(head);

Output:

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

Time Complexity: O(n) The time complexity of this insertion operation is O(n) because we have to traverse the entire list to reach i’s tail. The complexity would be O(1) if we were given the tail node to start with.

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.