This article contains insertion of the node of doubly-linked list at various position:

1. Insert node before head in DLL.
2. Insert node before tail in DLL.
3. Insert node before (kth node) in DLL.
4. Insert before given node in DLL.

1️⃣ Insert Node Before Head in DLL

Problem Statement

Given the head of a doubly linked list and an integer X, insert a node with value X before the head of the linked list and return the head of the modified list.

Examples

Example 1:

Input: head -> 1 <-> 2 <-> 3, X = 3
Output: head -> 3 <-> 1 <-> 2 <-> 3

Explanation: 3 was added before the 1st node. Note that the head's value is changed.

Example 2:

Input: head -> 5, X = 7
Output: head -> 7 <-> 5

Intuition:

Insert a new node at the beginning of a doubly linked list, create a new node, link it to the current head, make the new node the head, and adjust the previous pointer of the original head.

Approach:

1. Create a new node with the given value and set its back pointer to null and front pointer to the current head.
2. Update the current head's back pointer to point to the new node.
3. Return the new node as the updated head of the doubly linked list.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    /* Function to insert a node before 
    head in a doubly linked list */
    ListNode* insertBeforeHead(ListNode* head, int X) {
        // Create new node which will be the new head
        ListNode* newHead = new ListNode(X, head, nullptr);
        
        // Point the current head back to new one
        head->prev = newHead;

        return newHead; // Return new head
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {2, 3, 4, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    /* Function call to insert a node before 
    head in a doubly linked list */
    head = sol.insertBeforeHead(head, 1);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: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) as no extra space is used.

2️⃣ Insert Node Before Tail in DLL

Problem Statement

Given the head of a doubly linked list and an integer X, insert a node with value X before the tail of the linked list and return the head of the modified list.

Examples

Example 1:

Input: head -> 1 <-> 2 <-> 4, X = 3
Output: head -> 1 <-> 2 <-> 3 <-> 4

Explanation: 3 was added before the last node.

Example 2:

Input: head -> 4, X = 6
Output: head -> 6 <-> 4

Explanation: 6 was added before 4, note that the head was changed as a result.

Intuition:

Inserting a node before the tail of a doubly linked list involves traversing the list to locate the second-to-last node. Once found, a new node is created, and the pointers of the adjacent nodes are updated to place the new node correctly before the tail. This maintains the list structure and ensures the new node is properly integrated.

Approach:

1. Traverse to the tail of the linked list, keeping track of both the tail and the node previous to the tail.
2. Create a new node with the given value, setting its next pointer to the tail and its back pointer to the previous node.
3. Update the next pointer of the previous 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:

#include <bits/stdc++.h>
using namespace std;

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    // Function to insert a node before tail of a doubly linked list
    ListNode* insertBeforeTail(ListNode* head, int X) {
        // Edge case
        if (head->next == nullptr) {
            // Create new node with data as X
            ListNode* newHead = new ListNode(X, head, nullptr);
            head->prev = newHead;
            return newHead;
        }

        // Create pointer tail
        ListNode* tail = head;
        while (tail->next != nullptr) {
            tail = tail->next;
        }
        // Keep track of node before tail using prev
        ListNode* prev = tail->prev;

        // Create new node with value X
        ListNode* newNode = new ListNode(X, tail, prev);

        // Join the new node 
        prev->next = newNode;
        tail->prev = newNode;

        // Return updated linked list
        return head;
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    /* Function call to insert a node
    before tail of a doubly linked list */
    head = sol.insertBeforeTail(head, 4);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) where N is the length of the array. We iterate through the input array exactly once and at each element perform constant time operations.
• Space Complexity:O(1) as no extra space is used.

3️⃣ Insert Node Before (kth node) in DLL

Problem Statement:

Given the head of a doubly linked list and two integers X and K, insert a new node with value X, before the Kth node of the linked list and return the head of the modified linked list.

Examples:

Example 1:

Input: head -> 1 <-> 3 <-> 5, X = 7, K = 2
Output: head -> 1 <-> 7 <-> 3 <-> 5

Explanation: A node with value 7 was added before the 2nd node.

Example 2:

Input: head -> 1 <-> 3 <-> 5, X = 7, K = 2
Output: head -> 1 <-> 7 <-> 3 <-> 5

Explanation: A node with value 7 was added before the 2nd node.

Intuition:

Inserting a node in front of the Kth node in a doubly linked list involves first locating the Kth node by counting up to the Kth position. Then, adjust the pointers of the adjacent nodes to insert the new node before the Kth node.

Approach:

1. Traverse the doubly linked list until reaching the Kth node, keeping a count. When the count reaches K, stop the traversal. Use a temporary pointer to mark the Kth node.
2. Identify the node before the Kth node and prepare a new node with the required data, setting its previous and next pointers to the appropriate nodes.
3. Update the next pointer of the node before the Kth node to point to the new node, and update the back pointer of the Kth node to point to the new node.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    /* Function to insert a node before the
    Kth node in a doubly linked list */
    ListNode* insertBeforeKthPosition(ListNode* head, int X, int K) {
        // If node has to be inserted before the head
        if (K == 1) {
            ListNode* newHead = new ListNode(X, head, nullptr);
            head->prev = newHead;
            return newHead;
        }

        // Temporary pointer 
        ListNode* temp = head;

        // Reach kth node
        int count = 0;
        while (temp != nullptr) {
            count++;
            
            // If kth node is reached, Break out of the loop
            if (count == K) break;
            
            // Otherwise Keep moving temp forward
            temp = temp->next;
        }
        
        // Track the node 
        ListNode* prev = temp->prev;

        // Create new node with data as X
        ListNode* newNode = new ListNode(X, temp, prev);

        // Join new node 
        prev->next = newNode;
        temp->prev = newNode;

        // Return head 
        return head;
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    /* Function call to insert a node before the
    Kth node in a doubly linked list */
    head = sol.insertBeforeKthPosition(head, 4, 4);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N is the number of nodes in the Linked List. In the worst case, it involves traversing N nodes in the Doubly Linked List to reach the last 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) as no extra space is used.

4️⃣ Insert Before Given Node in DLL

Given a node's reference within a doubly linked list and an integer X, insert a node with value X before the given node in the linked list while preserving the list's integrity.

You will only be given the node's reference, not the head of the list. It is guaranteed that the given node will not be the head of the list.

Examples:

Example 1:

Input: head -> 1 <-> 2 <-> 6, node = 2, X = 7
Output: head -> 1 <-> 7 <-> 2 <-> 6

Explanation: Note that the head was not given to the function.

Example 2:

Input: head -> 7 <-> 5 <-> 5, node = 5 (node 3), X = 10
Output: head -> 7 <-> 5 <-> 10 <-> 5

Explanation: The last node with value 5 was referenced, thus the new node was added before the last node.

Intuition:

Identify the preceding node, create a new node and insert it between the identified node and its successor, then readjust links.

Approach:

1. Track the node to which the back pointer of the referenced node is pointing, and call it the previous node.
2. Create a new node with its data as the given value, its back pointer as the previous node, and its next pointer as the referenced node.
3. Update the next pointer of the previous node to point to the newly created node.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    /* Function to insert a new node before
    given node in a doubly linked list */
    void insertBeforeGivenNode(ListNode* node, int X) {
        // Get node before the given node
        ListNode* prev = node->prev;
        
        // Create new node 
        ListNode* newNode = new ListNode(X, node, prev);
        
        // Connect newNode
        prev->next = newNode;
        node->prev = newNode;
        
        // void function to just update
        return;
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 4, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Node before which the new node must be inserted
    ListNode* node = head-> next-> next;
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    /* Function call to insert a new node before
    given node in a doubly linked list */
    sol.insertBeforeGivenNode(node, 3);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: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) as no extra space is used.