Insertion in between two nodes in Doubly Linked List

Insertion at the Beginning in Doubly Linked List:

Insertion at the End in Doubly Linked List:

1. Add a node after a given node in a Doubly Linked List:

We are given a pointer to a node as prev_node, and the new node is inserted after the given node. This can be done using the following steps:

Firstly create a new node (say new_node).
Now insert the data in the new node.
Point the next of new_node to the next of prev_node.
Point the next of prev_node to new_node.
Point the previous of new_node to prev_node.
Point the previous of next of new_node to new_node.

Below is the implementation of the steps to insert a node after a given node in the linked list:

C++

// Given a node as prev_node, insert a new node 
// after the given node
void insertAfter(Node* prev_node, int new_data)
{
    // Check if the given prev_node is NULL
    if (prev_node == NULL) {
        cout << "the given previous node cannot be NULL";
        return;
    }

    // 1. allocate new node
    Node* new_node = new Node();

    // 2. put in the data
    new_node->data = new_data;

    // 3. Make next of new node as next of prev_node
    new_node->next = prev_node->next;

    // 4. Make the next of prev_node as new_node
    prev_node->next = new_node;

    // 5. Make prev_node as previous of new_node
    new_node->prev = prev_node;

    // 6. Change previous of new_node's next node
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}

// Given a node as prev_node, insert a new node 
// after the given node
void insertAfter(struct Node* prev_node, int new_data)
{
    // Check if the given prev_node is NULL
    if (prev_node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }

    // 1. allocate new node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));

    // 2. put in the data
    new_node->data = new_data;

    // 3. Make next of new node as next of prev_node
    new_node->next = prev_node->next;

    // 4. Make the next of prev_node as new_node
    prev_node->next = new_node;

    // 5. Make prev_node as previous of new_node
    new_node->prev = prev_node;

    // 6. Change previous of new_node's next node
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}

Java

// Given a node as prev_node, insert a new node 
// after the given node
public void InsertAfter(Node prev_Node, int new_data)
{
    // Check if the given prev_node is NULL
    if (prev_Node == null) {
        System.out.println(
            "The given previous node cannot be NULL ");
        return;
    }

    // 1. allocate node
    // 2. put in the data 
    Node new_node = new Node(new_data);

    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;

    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;

    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;

    // 6. Change previous of new_node's next node
    if (new_node.next != null)
        new_node.next.prev = new_node;
}

// Given a node as prev_node, insert a new node 
// after the given node
public void InsertAfter(Node prev_Node, int new_data)
{
    // Check if the given prev_node is NULL
    if (prev_Node == null) {
        Console.WriteLine(
            "The given previous node cannot be NULL ");
        return;
    }

    // 1. allocate node
    // 2. put in the data
    Node new_node = new Node(new_data);

    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;

    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;

    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;

    // 6. Change previous of new_node's next node
    if (new_node.next != null)
        new_node.next.prev = new_node;
}

// This code is contributed by aashish1995

Javascript

<script>

function InsertAfter(prev_Node,new_data)
{
        // Check if the given prev_node is NULL
    if (prev_Node == null) {
        document.write("The given previous node cannot be NULL <br>");
        return;
    }

    // 1. allocate node 
    // 2. put in the data
    let new_node = new Node(new_data);

    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;

    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;

    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;

    // 6. Change previous of new_node's next node
    if (new_node.next != null)
        new_node.next.prev = new_node;
}


// This code is contributed by unknown2108

</script>

Python3

# Given a node as prev_node, insert
# a new node after the given node


def insertAfter(self, prev_node, new_data):

    # Check if the given prev_node is NULL
    if prev_node is None:
        print("This node doesn't exist in DLL")
        return

    # 1. allocate node  & 
    # 2. put in the data
    new_node = Node(data=new_data)

    # 3. Make next of new node as next of prev_node
    new_node.next = prev_node.next

    # 4. Make the next of prev_node as new_node
    prev_node.next = new_node

    # 5. Make prev_node as previous of new_node
    new_node.prev = prev_node

    # 6. Change previous of new_node's next node
    if new_node.next is not None:
        new_node.next.prev = new_node

#  This code is contributed by jatinreaper

Time Complexity: O(1)
Auxiliary Space: O(1)

2. Add a node before a given node in a Doubly Linked List:

Let the pointer to this given node be next_node. This can be done using the following steps.

Allocate memory for the new node, let it be called new_node.
Put the data in new_node.
Set the previous pointer of this new_node as the previous node of the next_node.
Set the previous pointer of the next_node as the new_node.
Set the next pointer of this new_node as the next_node.
Set the next pointer of the previous of new_node to new_node.

Below is the implementation of the above approach.

C++

// Given a node as prev_node, insert a new node 
// after the given node
void insertBefore(Node* next_node, int new_data)
{
    // Check if the given next_node is NULL
    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
        return;
    }

    // 1. Allocate new node
    Node* new_node = new Node();

    // 2. Put in the data
    new_node->data = new_data;

    // 3. Make previous of new node as previous of next_node
    new_node->prev = next_node->prev;

    // 4. Make the previous of next_node as new_node
    next_node->prev = new_node;

    // 5. Make next_node as next of new_node
    new_node->next = next_node;

    // 6. Change next of new_node's previous node
    if (new_node->prev != NULL)
        new_node->prev->next = new_node;
    else
        head = new_node;
}

// Given a node as prev_node, insert a new node 
// after the given node
void insertBefore(struct Node* next_node, int new_data)
{
    // Check if the given next_node is NULL
    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
        return;
    }

    // 1. Allocate new node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));

    // 2. Put in the data
    new_node->data = new_data;

    // 3. Make previous of new node as previous of next_node
    new_node->prev = next_node->prev;

    // 4. Make the previous of next_node as new_node
    next_node->prev = new_node;

    // 5. Make next_node as next of new_node
    new_node->next = next_node;

    // 6. Change next of new_node's previous node
    if (new_node->prev != NULL)
        new_node->prev->next = new_node;
    else
        head = new_node;
}

Java

// Given a node as prev_node, insert a new node 
// after the given node
public void InsertBefore(Node next_Node, int new_data)
{
    // Check if the given next_node is NULL
    if (next_Node == null) {
        System.out.println(
            "The given next node cannot be NULL ");
        return;
    }

    // 1. Allocate node
    // 2. Put in the data 
    Node new_node = new Node(new_data);

    // 3. Make previous of new node as previous of prev_node
    new_node.prev = next_Node.prev;

    // 4. Make the prev of next_node as new_node
    next_Node.prev = new_node;

    // 5. Make next_node as next of new_node
    new_node.next = next_Node;

    // 6. Change next of new_node's previous node
    if (new_node.prev != null)
        new_node.prev.next = new_node;
    else
        head = new_node;
}

// Given a node as prev_node, insert a new node 
// after the given node
public void InsertAfter(Node next_Node, int new_data)
{
    // Check if the given next_node is NULL
    if (next_Node == null) {
        Console.WriteLine(
            "The given next node cannot be NULL ");
        return;
    }

    // 1. Allocate node
    // 2. Put in the data
    Node new_node = new Node(new_data);

    // 3. Make previous of new node as previous of next_node
    new_node.prev = next_Node.prev;

    // 4. Make the previous of next_node as new_node
    next_Node.prev = new_node;

    // 5. Make next_node as next of new_node
    new_node.next = next_Node;

    // 6. Change next of new_node's previous node
    if (new_node.prev != null)
        new_node.prev.next = new_node;
    else
        head = new_node;
}

// This code is contributed by aashish1995

Javascript

<script>

function InsertAfter(next_Node,new_data)
{
        // Check if the given next_Node is NULL
    if (next_Node == null) {
        document.write("The given next node cannot be NULL <br>");
        return;
    }

    // 1. Allocate node 
    // 2. Put in the data
    let new_node = new Node(new_data);

    // 3. Make previous of new node as previous of next_node
    new_node.prev = next_Node.prev;

    // 4. Make the previous of next_node as new_node
    next_Node.prev = new_node;

    // 5. Make next_node as next of new_node
    new_node.next = next_Node;

    // 6. Change next of new_node's previous node
    if (new_node.prev != null)
        new_node.prev.next = new_node;
    else
        head = new_node;
}


// This code is contributed by unknown2108

</script>

Python3

# Given a node as prev_node, insert
# a new node after the given node


def insertAfter(self, next_node, new_data):

    # Check if the given next_node is NULL
    if next_node is None:
        print("This node doesn't exist in DLL")
        return

    # 1. Allocate node  & 
    # 2. Put in the data
    new_node = Node(data=new_data)

    # 3. Make previous of new node as previous of prev_node
    new_node.prev = next_node.prev

    # 4. Make the previous of next_node as new_node
    next_node.prev = new_node

    # 5. Make next_node as next of new_node
    new_node.next = next_node

    # 6. Change next of new_node's previous node
    if new_node.prev is not None:
        new_node.prev.next = new_node
    else:
        head = new_node

#  This code is contributed by jatinreaper

Time Complexity: O(1)
Auxiliary Space: O(1)

Insertion in a Doubly Linked List

Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in four ways:

At the front of the DLL.
In between two nodes
- After a given node.
- Before a given node.
At the end of the DLL.

Tags:

#doubly linked list #Visa #Data Structures #DSA #Linked List #Visa #Data Structures #Linked List