Insert before a given Node of a DLL

Introduction

Doubly Linked Lists (DLLs) are a versatile data structure that allows efficient insertion and deletion operations. In this blog post, we’ll delve into the intricacies of Insert before a given Node of a DLL. We’ll cover the basics of DLLs, explore the concept of inserting before a node, and provide step-by-step examples for better understanding.

Basics of Doubly Linked Lists

Before we dive into the “Insert Before” operation, let’s briefly recap the basics of Doubly Linked Lists.

What is a Doubly Linked List?

A Doubly Linked List is a data structure composed of nodes, where each node contains data and two pointers – one pointing to the next node in the sequence (next pointer) and another pointing to the previous node (prev pointer). This bidirectional linkage allows traversal in both forward and backward directions.

Node Structure in a DLL

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

Here, data represents the information stored in the node, next points to the next node, and prev points to the previous node.

Understanding “Insert Before”

The “Insert Before” operation involves adding a new node before a specified node in the linked list. This operation requires adjusting the pointers of the neighboring nodes to accommodate the new node. The general steps for inserting before a given node in a DLL are:

1. Create a new node with the desired data.
2. Adjust the next and prev pointers of the new node to point to the current node and its predecessor, respectively.
3. Update the next pointer of the predecessor node to point to the new node.
4. Update the prev pointer of the current node to point to the new node.

Implementation of “Insert Before” in C

Let’s implement the “Insert Before” operation in C to solidify our understanding. Assume we have a Doubly Linked List and want to insert a new node with data X before a node with data Y.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// Function to insert a node before a given node
void insertBefore(struct Node** headRef, int newData, int targetData) {
    // Create a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    // Traverse the list to find the target node
    struct Node* current = *headRef;
    while (current != NULL && current->data != targetData) {
        current = current->next;
    }

    // If the target node is not found, display an error
    if (current == NULL) {
        printf("Node with data %d not found in the list.\n", targetData);
        free(newNode); // Free the allocated memory for the new node
        return;
    }

    // Adjust pointers to insert the new node before the target node
    newNode->prev = current->prev;
    newNode->next = current;
    current->prev = newNode;

    // If the new node is not the first in the list, update the predecessor's next pointer
    if (newNode->prev != NULL) {
        newNode->prev->next = newNode;
    } else {
        // If the new node is the first in the list, update the head pointer
        *headRef = newNode;
    }
}

// Function to display the contents of the DLL
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Driver program for testing
int main() {
    struct Node* head = NULL;

    // Create a sample DLL: 1 <-> 2 <-> 3 <-> 4
    for (int i = 4; i >= 1; i--) {
        insertBefore(&head, i, 2); // Insert each element before the node with data 2
    }

    // Display the modified DLL: 1 <-> 4 <-> 2 <-> 3
    printf("Doubly Linked List after insertion: ");
    displayList(head);

    return 0;
}

Step-by-Step Explanation

Let’s break down the key components of the implementation:

1. Creating a New Node:

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = newData;

Here, we dynamically allocate memory for a new node and assign the desired data to it.

2. Finding the Target Node:

   struct Node* current = *headRef;
   while (current != NULL && current->data != targetData) {
       current = current->next;
   }

We traverse the list to find the target node with data equal to targetData.

3. Adjusting Pointers:

   newNode->prev = current->prev;
   newNode->next = current;
   current->prev = newNode;

The prev pointer of the new node is set to the prev pointer of the target node, and its next pointer is set to the target node. The prev pointer of the target node is updated to point to the new node.

4. Updating Predecessor’s Next Pointer:

   if (newNode->prev != NULL) {
       newNode->prev->next = newNode;
   } else {
       *headRef = newNode;
   }

If the new node is not the first in the list, we update the next pointer of the predecessor node to point to the new node. If the new node is the first in the list, we update the head pointer.

Example: Inserting Before a Specific Node

Let’s walk through an example to illustrate how the “Insert Before” operation works. Consider the following DLL:

Original DLL: 1 <-> 2 <-> 3 <-> 4

Now, we want to insert a new node with data X before the node with data Y (let’s say Y = 3). We will use the insertBefore function to perform this operation.

Initial State:

• Head: 1
• DLL: 1 <-> 2 <-> 3 <-> 4

Operation:

insertBefore(&head, X, Y);

• We create a new node with data X.
• We traverse the list to find the target node with data Y (3).
• We adjust pointers to insert the new node before the target node.

Final State:

• Head: 1
• DLL: 1 <-> X <-> 2 <-> 3 <-> 4

Conclusion

In this blog post, we explored the “Insert Before” operation in a Doubly Linked Lists (DLLs). We covered the fundamentals of DLLs, the concept of inserting before a given node, and provided a step-by-step implementation in C. The example illustrated how to use the operation to modify a DLL and showcased its practical application.

Understanding these fundamental operations is crucial for mastering data structures and algorithms. The “Insert Before” operation, with its bidirectional traversal and pointer adjustments, demonstrates the elegance and efficiency of Doubly Linked Lists. Consider practicing the implementation with different scenarios to deepen your comprehension and enhance your programming skills. Happy coding!

Read More –

Find the Length of a Linked List – https://kamleshsingad.com/find-the-length-of-a-linked-list/

Convert an array to a Linked List – https://kamleshsingad.com/convert-an-array-to-a-linked-list/

Classes and Structures in C++ – https://kamleshsingad.com/classes-and-structures-in-c/