Doubly Linked List Insertion at Given Position

Problem

Given a doubly-linked list, a position p, and an integer x. The task is to add a new node with value x at the position just after pth node in the doubly linked list.

Examples:

Example 1:

Input:
LinkedList: 2<->4<->5
p = 2, x = 6 
Output: 2 4 5 6
Explanation: p = 2, and x = 6. So, 6 is inserted after p, i.e, at position 3 (0-based indexing).

Example 2:

Input:
LinkedList: 1<->2<->3<->4
p = 0, x = 44
Output: 1 44 2 3 4
Explanation: p = 0, and x = 44 . So, 44 is inserted after p, i.e, at position 1 (0-based indexing).

Your task:

The task is to complete the function addNode() which head reference, position and data to be inserted as the arguments, with no return type.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^4$
• $0 <= p < N$

Solution

Python

def addNode(head, p, data):
    new_node = Node(data)
    if head is None:
        head = new_node
    else:
        temp = head
        count = 0
        while temp.next is not None and count < p:
            temp = temp.next
            count += 1
        if temp.next is None:
            temp.next = new_node
            new_node.prev = temp
        else:
            new_node.next = temp.next
            new_node.prev = temp
            temp.next = new_node
            if new_node.next is not None:
                new_node.next.prev = new_node

Java

void addNode(Node head_ref, int pos, int data) {
    Node new_node = new Node(data);
    if (head_ref == null) {
        head_ref = new_node;
    } 
    else {
        Node temp = head_ref;
        int count = 0;
        while (temp.next != null && count < pos) {
            temp = temp.next;
            count++;
        }
        if (temp.next == null) {
            temp.next = new_node;
            new_node.prev = temp;
        } 
        else {
            new_node.next = temp.next;
            new_node.prev = temp;
            temp.next = new_node;
            if (new_node.next != null) {
                new_node.next.prev = new_node;
            }
        }
    }
}

C++

void addNode(Node *head, int pos, int data) {
   Node* new_node = new Node(data);
    if (head == nullptr) {
        head = new_node;
    } 
    else {
        Node* temp = head;
        int count = 0;
        while (temp->next != nullptr && count < pos) {
            temp = temp->next;
            count++;
        }
        if (temp->next == nullptr) {
            temp->next = new_node;
            new_node->prev = temp;
        } 
        else {
            new_node->next = temp->next;
            new_node->prev = temp;
            temp->next = new_node;
            if (new_node->next != nullptr) {
                new_node->next->prev = new_node;
            }
        }
    }
}

C

void addNode(struct Node *head, int pos, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = NULL;
    if (head == NULL) {
        head = new_node;
    } 
    else {
        struct Node* temp = head;
        int count = 0;
        while (temp->next != NULL && count < pos) {
            temp = temp->next;
            count++;
        }
        if (temp->next == NULL) {
            temp->next = new_node;
            new_node->prev = temp;
        } 
        else {
            new_node->next = temp->next;
            new_node->prev = temp;
            temp->next = new_node;
            if (new_node->next != NULL) {
                new_node->next->prev = new_node;
            }
        }
    }
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$