Insertion at the Beginning in Doubly Linked List

Insertion in between two nodes in Doubly Linked List:

To insert a new node at the beginning of the doubly list, we can use the following steps:

Allocate memory for a new node (say new_node) and assign the provided value to its data field.
Set the previous pointer of the new_node to nullptr.
If the list is empty:
- Set the next pointer of the new_node to nullptr.
- Update the head pointer to point to the new_node.
If the list is not empty:
- Set the next pointer of the new_node to the current head.
- Update the previous pointer of the current head to point to the new_node.
- Update the head pointer to point to the new_node.

Below is the implementation of the 5 steps to insert a node at the front of the linked list:

C++

// Given a reference (pointer to pointer) to the head 
// of a list and an int, inserts a new node 
// on the front of the list.
void push(Node** head_ref, int new_data)
{
    // 1. allocate node
    Node* new_node = new Node();

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

    // 3. Make next of new node as head
    // and previous as NULL
    new_node->next = (*head_ref);
    new_node->prev = NULL;

    // 4. change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    // 5. move the head to point to the new node
    (*head_ref) = new_node;
}

// This code is contributed by shivanisinghss2110

// Given a reference (pointer to pointer) to the head
// of a list and an int, inserts a new node
// on the front of the list.
void push(struct Node** head_ref, int new_data)
{
    // 1. allocate 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 head and previous as NULL
    new_node->next = (*head_ref);
    new_node->prev = NULL;

    // 4. change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    // 5. move the head to point to the new node
    (*head_ref) = new_node;
}

Java

// Adding a node at the front of the list
public void push(int new_data)
{
    // 1. allocate node
    // 2. put in the data */
    Node new_Node = new Node(new_data);

    // 3. Make next of new node as head and previous as NULL
    new_Node.next = head;
    new_Node.prev = null;

    // 4. change prev of head node to new node
    if (head != null)
        head.prev = new_Node;

    // 5. move the head to point to the new node
    head = new_Node;
}

// Adding a node at the front of the list
public void push(int new_data)
{
    // 1. allocate node
    // 2. put in the data
    Node new_Node = new Node(new_data);

    // 3. Make next of new node as head and previous as NULL
    new_Node.next = head;
    new_Node.prev = null;

    // 4. change prev of head node to new node
    if (head != null)
        head.prev = new_Node;

    // 5. move the head to point to the new node
    head = new_Node;
}

// This code is contributed by aashish1995

Javascript

// Adding a node at the front of the list
function push(new_data)
{
    // 1. allocate node 
    // 2. put in the data
    let new_Node = new Node(new_data);

    // 3. Make next of new node as head and previous as NULL
    new_Node.next = head;
    new_Node.prev = null;

    // 4. change prev of head node to new node
    if (head != null)
        head.prev = new_Node;

    // 5. move the head to point to the new node
    head = new_Node;
}

// This code is contributed by saurabh_jaiswal.

Python3

# Adding a node at the front of the list
def push(self, new_data):

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

    # 3. Make next of new node as head and previous as NULL
    new_node.next = self.head
    new_node.prev = None

    # 4. change prev of head node to new node
    if self.head is not None:
        self.head.prev = new_node

    # 5. move the head to point to the new node
    self.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

Insertion in between two nodes in Doubly Linked List:

Insertion at the Beginning in Doubly Linked List

Insertion in a Doubly Linked List

Similar Reads