# Insert before the tail of a Doubly Linked List

Problem Statement:  Given a node and a doubly linked list, insert the node before the tail of the doubly linked list and return the updated list.

Examples
```Example 1:
Input Format:
DLL: 1 <-> 2 <-> 3Value to be Inserted: 4  Result: DLL: 1 <-> 2 <-> 4 <->3  Explanation: We need to insert the value 4 before the tail of the given Doubly Linked List, which is node 3.
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 tail 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 before the tail of a Doubly Linked List (DLL), traverse the list until reaching the tail, while also tracking the node before it. Create a new node with the given value, set its next to the tail and back to the previous node. Update the previous node’s next to the new node and the tail’s back to maintain the doubly linked structure.

An edge case to be mindful of is if there is only one node in the entire doubly linked list then the head would also serve as the tail. In this case, the steps to insert a node before the head of a doubly linked list can be done.

Algorithm:

Step 1: Traverse to the tail of the linked list and keep track of it using the tailpointer. Also, keep track of the node previous to the tail using the prev pointer.

Step 2: Create a new node with the given value. Set its next pointer to point to the tail and its back pointer to point to the prev node.

Step 3: Update the next pointer of the prev node to point to the new node and the back pointer of the tail to point to the new node, effectively inserting the new node before the tail.

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

// This function was explain in prevoius articles
// Function to insert new node before head
// Create new node with data as val

}

// Edge case, if dll has only one elements
// If only one element
}

// Create pointer tail to traverse to the end of list
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
}

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

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

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.

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

private static Node insertBeforeTail(Node head, int val){
// Edge case, if dll has only one elements
// If only one element
}

// Create pointer tail to traverse to the end of list
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
}

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

System.out.println("Doubly Linked List After Inserting 6 before tail: ");

}
}
``````

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.

## Python Code

``````# 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
# 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

# Function to print the elements of the doubly linked list
# Print the data in the current node
# Move to the next node
print()

# Function to insert a new node before the head of the doubly linked list
# Create a new node with data as val

# Function to insert a new node before the tail of the doubly linked list
# Edge case: if the DLL has only one element
# If only one element, insert before the head

# Create a pointer 'tail' to traverse to the end of the list
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

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

print("Doubly Linked List After Inserting 6 before tail:")
``````

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.

## JavaScript Code

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

// Function to print the elements of the doubly linked list
// Print the data in the current node
// Move to the next node
}
}

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

}

// Function to insert a new node before the tail
// Edge case: if DLL has only one element
// If only one element, insert before the head
}

// Create a pointer 'tail' to traverse to the end of the list
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
}

const arr = [12, 5, 8, 7, 4];

console.log("\nDoubly Linked List After Inserting 6 before tail: ");
``````

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.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.