Basic operations on Doubly LinkedList - 1

Insertion in a Doubly LinkedList

A Doubly LinkedList is a data structure that consists of nodes connected in a linear fashion, with each node containing a value and references to both the previous and next nodes.

The insertion of nodes in a Doubly LinkedList involves adding a new node at a specific position within the list, ensuring that the previous and next pointers of the adjacent nodes are appropriately updated.

This flexibility and efficiency make Doubly LinkedLists a popular choice for scenarios that involve frequent insertions and deletions at arbitrary positions within a collection of data.

In this article, we will explore the process of inserting nodes in a Doubly LinkedList and understand the necessary steps involved.

There are four possible ways to insert a node in a Doubly Linked List:

Inserting at the front of the DLL: Add a new node at the beginning of the list, making it the new head node.
Inserting after a given node: Insert a new node immediately after a specified node in the DLL, updating the relevant pointers.
Inserting before a given node: Add a new node just before a specified node in the DLL, ensuring the appropriate pointers are adjusted.
Inserting at the end of the DLL: Add a new node at the end of the list, making it the new tail node.

⭐Insertion at the front of Doubly LinkedList

To insert a new node before the head of a given Doubly LinkedList, the following steps can be followed:

Create a new node (let's call it new_node) and allocate memory for it.
Assign the desired data to the new_node.
Set the "next" pointer of the new_node to point to the current head of the doubly linked list. This ensures that the new_node comes before the existing head.
Set the "previous" pointer of the current head node to point to the new_node. This establishes the link between the new_node and the previous head.
Finally, update the head pointer of the doubly linked list to point to the new_node. This makes the new_node the new head of the list.

By following these steps, a new node can be successfully inserted before the head of the given Doubly LinkedList, allowing for efficient data management and traversal.

Diagrammatic representation :

See the below diagram where D is being inserted at the beginning of the doubly linked list.

Here is the code snippet for adding a node at the front of the Doubly LinkedList :

public void push(int new_data) {
    // Allocate a new node and assign the provided data to it
    Node new_Node = new Node(new_data);
    
    // Set the "next" pointer of the new node to the current head of the LinkedList
    new_Node.next = head;
    
    // Set the "previous" pointer of the new node to NULL or appropriate value
    new_Node.prev = null;
    
    // Update the "previous" pointer of the current head if it exists
    if (head != null) {
        head.prev = new_Node;
    }
    
    // Update the head pointer to the new node
    head = new_Node;
}

⭐Insertion of node after a given node(in between) of the Doubly Linked List

Here are the steps to insert a new node after a given node in a Doubly LinkedList:

Generate a new node, referred to as new_node.
Input the desired data into the new_node.
Assign the "next" pointer of new_node to the same value as the "next" pointer of the prev_node.
Update the "next" pointer of the prev_node to point to the new_node.
Set the "previous" pointer of the new_node to refer to the prev_node.
Modify the "previous" pointer of the node succeeding the new_node to point back to the new_node.

By following these steps, a new node can be successfully inserted after a given node in a Doubly LinkedList, ensuring the appropriate connections between the nodes are maintained.

Here is the code snippet for inserting a node between two nodes of the Doubly LinkedList :

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

// Create a new node and assign the provided new_data to it
Node new_node = new Node(new_data);

// Set the "next" pointer of the new_node to the "next" pointer of prev_Node
new_node.next = prev_Node.next;

// Set the "next" pointer of prev_Node to the new_node
prev_Node.next = new_node;

// Set the "previous" pointer of the new_node to the prev_Node
new_node.prev = prev_Node;

// Update the "previous" pointer of the new_node's next node if it exists
if (new_node.next != null) {
new_node.next.prev = new_node;
}
}

Homework

Learn about the following:

Inserting before a given node
Inserting at the end of the Doubly LinkedList

Hope you enjoyed reading

Happy learning

Now what?

Check the following blog for LinkedList

Introduction to LinkedList

https://madalgos.in/blog-space/27

https://madalgos.in/blog-space/28

https://madalgos.in/blog-space/29

Basic opertaions on LinkedList

https://madalgos.in/blog-space/30

https://madalgos.in/blog-space/32

https://madalgos.in/blog-space/33