Inserting a Node Before a Given Node in a Doubly Linked List: A Detailed Exploration

Working with Doubly Linked Lists (DLL) is a cornerstone of data structure mastery in programming. Unlike Singly Linked Lists, a doubly linked list provides a bidirectional traversal capability, where each node contains references to both its previous and next nodes. This two-way linkage simplifies certain operations, such as insertion and deletion.

In this post, we will delve deeply into the problem of inserting a new node before a given node in a doubly linked list and break down the step-by-step procedure to achieve this efficiently.

What is a Doubly Linked List?

A Doubly Linked List is a linear data structure composed of nodes, where each node consists of three fields:

• Data Field: Holds the actual data of the node.
• Previous Pointer (prev): Points to the previous node in the list (or NULL for the head node).
• Next Pointer (next): Points to the next node in the list (or NULL for the tail node).

The two-pointer mechanism allows traversal in both directions: from the head to the tail and vice versa. This is particularly advantageous when compared to Singly Linked Lists, where traversal is restricted to a single direction.

Problem Statement

The task is to insert a new node, containing a specified data value, before a given node in a doubly linked list.

Example 1:

• Input:
  Linked List: 1 <-> 3 <-> 4
  New Node Data: 2
  Key Node: 3
• Output:
  Linked List: 1 <-> 2 <-> 3 <-> 4

Explanation:

We locate the node with data 3, create a new node with data 2, and insert it right before 3. This involves adjusting the prev and next pointers of the relevant nodes to maintain the doubly linked structure.

Example 2:

• Input:
  Linked List: 2 <-> 3
  New Node Data: 1
  Key Node: 2
• Output:
  Linked List: 1 <-> 2 <-> 3

Explanation:

Here, the new node with data 1 becomes the head of the list, as it is inserted before the node with data 2.

Approach to Solve the Problem

To tackle the insertion operation, we can follow these detailed steps. These steps ensure that the integrity of the doubly linked list is preserved, even after modifications.

Step-by-Step Explanation:

• Locate the Given Node (Key):
  Begin by traversing the doubly linked list from the head. Continue moving forward until you find the node whose data matches the given key. If the key node is not found, terminate the process and return the original linked list.
• Create a New Node:
  Once the key node is identified, create a new node to store the new data value. This node will eventually be inserted before the located key node.
• Update Pointers for the New Node:
  Set the prev pointer of the new node to point to the key node’s previous node (if any) and its next pointer to the key node.
  • new_node->prev = curr->prev
  • new_node->next = curr
• Adjust the Previous Node (If Exists):
  Check if the key node is the head node.
  • If it is the head, update the head of the linked list to point to the new node.
  • If it is not the head, update the next pointer of the key node’s previous node to point to the new node:
    • new_node->prev->next = new_node
• Update the Key Node’s Previous Pointer:
  Finally, modify the prev pointer of the key node to point to the new node:
  • curr->prev = new_node

Code Implementation

Below is a Python implementation of the discussed approach:

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_before(self, key, new_data):
        # Step 1: Traverse the list to find the key node
        curr = self.head
        while curr and curr.data != key:
            curr = curr.next

        # If key node is not found, return
        if not curr:
            print("Key node not found.")
            return

        # Step 2: Create a new node
        new_node = Node(new_data)

        # Step 3: Update new_node's pointers
        new_node.next = curr
        new_node.prev = curr.prev

        # Step 4: Adjust the previous node
        if curr.prev:
            curr.prev.next = new_node
        else:
            # If the key node is the head, update the head
            self.head = new_node

        # Step 5: Update key node's previous pointer
        curr.prev = new_node

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data, end=" <-> ")
            curr = curr.next
        print("NULL")

# Example Usage:
dll = DoublyLinkedList()
dll.head = Node(1)
second = Node(3)
third = Node(4)

dll.head.next = second
second.prev = dll.head
second.next = third
third.prev = second

print("Original List:")
dll.print_list()

dll.insert_before(3, 2)
print("After Insertion:")
dll.print_list()

Detailed Explanation of Code:

• Class Definitions:
  • Node: Represents a single node in the doubly linked list, with attributes for data, prev, and next.
  • DoublyLinkedList: Represents the entire doubly linked list. Contains methods for insertion and printing the list.
• insert_before Method:
  • This method performs the insertion operation by first finding the key node, then creating and linking the new node appropriately.
• Edge Cases Handled:
  • Key Node Not Found: Prints a message and terminates without modifying the list.
  • Insertion Before the Head: Updates the head pointer of the list to the new node.

Coding Implementation In Multiple Programming Languages

Here is the code written in C, C++, C#, Java, JavaScript, and Python, along with a detailed step-by-step explanation for each language.

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

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

// Function to create a new node with the given data
struct Node *createNode(int new_data) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->prev = NULL;
    return new_node;
}

// Function to insert a new node before a given node
struct Node* insertBefore(struct Node *head, int key, int new_data) {
    struct Node *curr = head;

    while (curr != NULL) {
        if (curr->data == key) break;
        curr = curr->next;
    }

    if (curr == NULL) return head; // Key not found

    struct Node *new_node = createNode(new_data);
    new_node->prev = curr->prev;
    new_node->next = curr;

    if (curr->prev != NULL) {
        curr->prev->next = new_node;
    } else {
        head = new_node;
    }

    curr->prev = new_node;

    return head;
}

void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf(" %d", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    struct Node *head = createNode(1);
    head->next = createNode(3);
    head->next->prev = head;
    head->next->next = createNode(4);
    head->next->next->prev = head->next;

    printf("Original Linked List:");
    printList(head);

    printf("Inserting Node with data 2 before node 3:");
    head = insertBefore(head, 3, 2);

    printList(head);

    return 0;
}

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;

    Node(int new_data) {
        data = new_data;
        next = nullptr;
        prev = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    void insertBefore(int key, int new_data) {
        Node* curr = head;

        while (curr != nullptr) {
            if (curr->data == key) break;
            curr = curr->next;
        }

        if (curr == nullptr) return;

        Node* new_node = new Node(new_data);
        new_node->prev = curr->prev;
        new_node->next = curr;

        if (curr->prev != nullptr) {
            curr->prev->next = new_node;
        } else {
            head = new_node;
        }

        curr->prev = new_node;
    }

    void printList() {
        Node* curr = head;
        while (curr != nullptr) {
            cout << " " << curr->data;
            curr = curr->next;
        }
        cout << endl;
    }
};

int main() {
    DoublyLinkedList list;
    list.head = new Node(1);
    list.head->next = new Node(3);
    list.head->next->prev = list.head;
    list.head->next->next = new Node(4);
    list.head->next->next->prev = list.head->next;

    cout << "Original Linked List:";
    list.printList();

    cout << "Inserting Node with data 2 before node 3:";
    list.insertBefore(3, 2);

    list.printList();

    return 0;
}

using System;

class Node {
    public int Data;
    public Node Next;
    public Node Prev;

    public Node(int data) {
        Data = data;
        Next = null;
        Prev = null;
    }
}

class DoublyLinkedList {
    public Node Head;

    public void InsertBefore(int key, int newData) {
        Node curr = Head;

        while (curr != null) {
            if (curr.Data == key) break;
            curr = curr.Next;
        }

        if (curr == null) return;

        Node newNode = new Node(newData);
        newNode.Prev = curr.Prev;
        newNode.Next = curr;

        if (curr.Prev != null) {
            curr.Prev.Next = newNode;
        } else {
            Head = newNode;
        }

        curr.Prev = newNode;
    }

    public void PrintList() {
        Node curr = Head;
        while (curr != null) {
            Console.Write(" " + curr.Data);
            curr = curr.Next;
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.Head = new Node(1);
        list.Head.Next = new Node(3);
        list.Head.Next.Prev = list.Head;
        list.Head.Next.Next = new Node(4);
        list.Head.Next.Next.Prev = list.Head.Next;

        Console.WriteLine("Original Linked List:");
        list.PrintList();

        Console.WriteLine("Inserting Node with data 2 before node 3:");
        list.InsertBefore(3, 2);

        list.PrintList();
    }
}

class Node {
    int data;
    Node next, prev;

    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    Node head;

    void insertBefore(int key, int newData) {
        Node curr = head;

        while (curr != null) {
            if (curr.data == key) break;
            curr = curr.next;
        }

        if (curr == null) return;

        Node newNode = new Node(newData);
        newNode.prev = curr.prev;
        newNode.next = curr;

        if (curr.prev != null) {
            curr.prev.next = newNode;
        } else {
            head = newNode;
        }

        curr.prev = newNode;
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(" " + curr.data);
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.head = new Node(1);
        list.head.next = new Node(3);
        list.head.next.prev = list.head;
        list.head.next.next = new Node(4);
        list.head.next.next.prev = list.head.next;

        System.out.println("Original Linked List:");
        list.printList();

        System.out.println("Inserting Node with data 2 before node 3:");
        list.insertBefore(3, 2);

        list.printList();
    }
}

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
    }

    insertBefore(key, newData) {
        let curr = this.head;

        while (curr) {
            if (curr.data === key) break;
            curr = curr.next;
        }

        if (!curr) return;

        const newNode = new Node(newData);
        newNode.prev = curr.prev;
        newNode.next = curr;

        if (curr.prev) {
            curr.prev.next = newNode;
        } else {
            this.head = newNode;
        }

        curr.prev = newNode;
    }

    printList() {
        let curr = this.head;
        while (curr) {
            process.stdout.write(` ${curr.data}`);
            curr = curr.next;
        }
        console.log();
    }
}

const list = new DoublyLinkedList();
list.head = new Node(1);
list.head.next = new Node(3);
list.head.next.prev = list.head;
list.head.next.next = new Node(4);
list.head.next.next.prev = list.head.next;

console.log("Original Linked List:");
list.printList();

console.log("Inserting Node with data 2 before node 3:");
list.insertBefore(3, 2);

list.printList();

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_before(self, key, new_data):
        curr = self.head

        while curr:
            if curr.data == key:
                break
            curr = curr.next

        if not curr:
            return

        new_node = Node(new_data)
        new_node.prev = curr.prev
        new_node.next = curr

        if curr.prev:
            curr.prev.next = new_node
        else:
            self.head = new_node

        curr.prev = new_node

    def print_list(self):
        curr = self

.head
        while curr:
            print(curr.data, end=" ")
            curr = curr.next
        print()

dll = DoublyLinkedList()
dll.head = Node(1)
dll.head.next = Node(3)
dll.head.next.prev = dll.head
dll.head.next.next = Node(4)
dll.head.next.next.prev = dll.head.next

print("Original Linked List:")
dll.print_list()

print("Inserting Node with data 2 before node 3:")
dll.insert_before(3, 2)

dll.print_list()

Output

Original Linked List: 
1 3 4
Inserting Node with data 2 before node 3: 
1 2 3 4

Time Complexity: O(N), where N is the number of nodes in the doubly linked list
Auxiliary Space: O(1)

Key Takeaways:

• Node Structure: Each language defines a structure or class to represent a node.
• Memory Management:
  • C uses malloc for dynamic memory allocation.
  • C++ uses new to allocate memory for nodes.
  • C#, Java, JavaScript, and Python manage memory automatically with garbage collection, but we still need to instantiate objects via new in most cases.
• Pointer Handling: C and C++ work directly with pointers for node linking, while higher-level languages abstract this away.
• Syntax Differences: Each language has a different way of handling memory allocation, node creation, and syntax for defining classes or structures.

Time Complexity Analysis

• Traversal to Locate Key Node: O(N), where N is the number of nodes in the doubly linked list.
• Pointer Updates: O(1) (constant time for pointer adjustments).
• Overall Time Complexity: O(N)

Conclusion

The task of inserting a node before a given node in a doubly linked list is an excellent example of pointer manipulation and list traversal. By understanding the relationships between nodes and ensuring careful updates to the prev and next pointers, the operation can be performed efficiently while maintaining the integrity of the data structure.

This fundamental technique has applications in a variety of real-world scenarios, from implementing undo/redo functionality in text editors to managing browser history. Mastery of this concept provides a strong foundation for solving more complex problems in data structures and algorithms.

Frequently Asked Questions (FAQs)

What is a Doubly Linked List (DLL), and how does it differ from a Singly Linked List?

A Doubly Linked List (DLL) is a type of linked list where each node contains three parts:

• Data Field: Stores the actual data of the node.
• Prev Pointer: Points to the previous node in the list.
• Next Pointer: Points to the next node in the list.

This structure allows traversal in both directions (from head to tail and tail to head), unlike a Singly Linked List (SLL), where traversal is restricted to a single direction. Additionally, insertion and deletion operations are more flexible in DLLs because of the prev pointer, which enables efficient backtracking.

Why is inserting a node before a given node in a DLL more efficient than in a Singly Linked List?

In a Singly Linked List, to insert a node before a given node, we must traverse the list to locate the previous node of the target node. This can add significant overhead because there is no backward linkage.

However, in a Doubly Linked List, each node has a prev pointer that directly points to the previous node. This means:

• We don’t need to traverse the list again to access the previous node.
• Pointer updates are straightforward, as the bidirectional structure provides access to both adjacent nodes.

Thus, insertion operations in a DLL are typically more efficient and require fewer steps.

What are the detailed steps for inserting a node before a given node in a DLL?

The process involves the following steps:

• Locate the Key Node:
  Traverse the list starting from the head until the node with the specified key (data value) is found.
• Create a New Node:
  Allocate memory for a new node and store the new data value in it.
• Update the New Node’s Pointers:
  • Set the prev pointer of the new node to the key node’s previous node.
  • Set the next pointer of the new node to the key node.
• Adjust the Previous Node’s Pointer (if it exists):
  • If the key node is not the head, update the next pointer of the key node’s previous node to point to the new node.
  • If the key node is the head, update the head of the DLL to the new node.
• Update the Key Node’s Prev Pointer:
  Finally, set the prev pointer of the key node to point to the new node.

What happens if the key node is not found in the list?

If the key node is not found:

• The insertion process is terminated.
• The original linked list remains unchanged.
  In the Python implementation provided, this case is explicitly handled with a message:

if not curr:
    print("Key node not found.")
    return

This ensures the program does not attempt to modify the list when the key node is absent, avoiding potential errors like dereferencing a null pointer.

How does the insertion process handle the case where the key node is the head of the DLL?

If the key node is the head node, the following adjustments are made:

• The new node is set as the head of the list.
  • self.head = new_node
• The prev pointer of the new node is set to NULL (or None in Python) because it is now the head.
• The prev pointer of the original head node (key node) is updated to point to the new node.

This ensures the head reference of the DLL is updated correctly, maintaining list integrity.

What is the time complexity of inserting a node before a given node in a DLL?

The time complexity can be analyzed as follows:

• Traversal to Locate the Key Node:
  This step involves traversing the list from the head to the key node, which takes O(N) time, where N is the number of nodes in the list.
• Pointer Updates:
  Updating the pointers of the new node, key node, and possibly the key node’s previous node takes O(1) time, as it involves constant-time operations.

Thus, the overall time complexity is O(N).

How is memory allocated for the new node, and why is it important?

In the Python implementation, memory for the new node is allocated using the Node class constructor:

new_node = Node(new_data)

This step ensures that:

• A dedicated block of memory is created for the new node.
• The new node’s prev and next pointers can be initialized properly.

Efficient memory allocation is critical in dynamic data structures like linked lists because it ensures that new elements can be added without predefining the list’s size.

What edge cases should be considered when inserting a node before a given node in a DLL?

Here are some key edge cases:

• Empty List:
  • If the list is empty, the insertion process cannot proceed because there are no nodes in the list.
• Key Node Not Found:
  • If the key node does not exist in the list, the insertion is skipped, and the list remains unchanged.
• Key Node is the Head:
  • Special handling is required to update the head reference and ensure the new node becomes the head.
• Key Node is the Only Node:
  • The insertion operation must ensure the new node correctly updates its pointers to the single existing node.
• Multiple Nodes with the Same Key:
  • The insertion process typically targets the first occurrence of the key node unless otherwise specified.

Can this process be extended to insert nodes after a given node in a DLL?

Yes, the process can be modified to insert nodes after a given node. The key differences are:

• Update the next pointer of the new node to point to the key node’s next node.
  • new_node->next = curr->next
• Update the prev pointer of the new node to point to the key node.
  • new_node->prev = curr
• Adjust the key node’s next pointer to point to the new node.
  • curr->next = new_node
• Update the prev pointer of the key node’s original next node (if any) to point to the new node.

What are the real-world applications of Doubly Linked Lists and the discussed insertion process?

Doubly Linked Lists are widely used in various applications where bidirectional traversal or dynamic memory allocation is required. Some common examples include:

• Undo/Redo Operations:
  • Many text editors use a DLL to manage the undo and redo stack, allowing efficient navigation between states.
• Browser History Management:
  • DLLs enable efficient navigation between previous and next pages in web browsers.
• Playlist Management in Media Players:
  • Songs in a playlist can be represented as a DLL to support forward and backward traversal.
• Memory Management:
  • Operating systems use DLLs to manage free and allocated memory blocks efficiently.