Insertion in Doubly Linked List with Implementation: A Detailed Exploration

C Implementation

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

// Define the structure of a doubly linked list node
struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
};

// Function to create a new node
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 at the front of the doubly linked list
struct Node *insertAtFront(struct Node *head, int new_data) {
    struct Node *new_node = createNode(new_data);
    new_node->next = head;
    if (head != NULL) {
        head->prev = new_node;
    }
    return new_node;
}

// Function to print the doubly linked list
void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf(" %d", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // Create a doubly linked list: 2 <-> 3 <-> 4
    struct Node *head = createNode(2);
    head->next = createNode(3);
    head->next->prev = head;
    head->next->next = createNode(4);
    head->next->next->prev = head->next;

    // Print the original list
    printf("Original Linked List:");
    printList(head);

    // Insert a new node at the front of the list
    printf("After inserting Node at the front:");
    int data = 1;
    head = insertAtFront(head, data);

    // Print the updated list
    printList(head);

    return 0;
}

Explanation

• Structure Definition:
  • The Node structure contains three fields: data (to store the value), next (pointer to the next node), and prev (pointer to the previous node).
  • It allows bidirectional traversal.
• Creating Nodes:
  • The createNode function allocates memory for a new node and initializes its data, next, and prev fields.
• Insertion Logic:
  • In insertAtFront, the new node is created and its next is linked to the current head.
  • If the list is non-empty, the prev pointer of the current head is updated to point to the new node.
  • Finally, the new node is returned as the updated head of the list.
• Printing the List:
  • The printList function traverses the list using the next pointer and prints the data of each node.
• Main Function:
  • A hardcoded list (2 <-> 3 <-> 4) is created.
  • A new node with data 1 is inserted at the front, updating the head pointer.
  • Both the original and updated lists are printed.

C++ Implementation

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int new_data) : data(new_data), next(nullptr), prev(nullptr) {}
};

// Function to insert at the front
Node* insertAtFront(Node* head, int new_data) {
    Node* new_node = new Node(new_data);
    new_node->next = head;
    if (head != nullptr) {
        head->prev = new_node;
    }
    return new_node;
}

// Function to print the list
void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        cout << " " << curr->data;
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // Create a doubly linked list: 2 <-> 3 <-> 4
    Node* head = new Node(2);
    head->next = new Node(3);
    head->next->prev = head;
    head->next->next = new Node(4);
    head->next->next->prev = head->next;

    // Print the original list
    cout << "Original Linked List:";
    printList(head);

    // Insert a new node at the front
    cout << "After inserting Node at the front:";
    int data = 1;
    head = insertAtFront(head, data);

    // Print the updated list
    printList(head);

    return 0;
}

C# Implementation

using System;

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

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

class DoublyLinkedList {
    // Insert at the front
    public static Node InsertAtFront(Node head, int newData) {
        Node newNode = new Node(newData);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        return newNode;
    }

    // Print the list
    public static void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            Console.Write(" " + curr.data);
            curr = curr.next;
        }
        Console.WriteLine();
    }

    static void Main() {
        // Create a doubly linked list: 2 <-> 3 <-> 4
        Node head = new Node(2);
        head.next = new Node(3);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        // Print the original list
        Console.WriteLine("Original Linked List:");
        PrintList(head);

        // Insert a new node at the front
        Console.WriteLine("After inserting Node at the front:");
        int data = 1;
        head = InsertAtFront(head, data);

        // Print the updated list
        PrintList(head);
    }
}

Java Implementation

class Node {
    int data;
    Node next, prev;

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

public class DoublyLinkedList {
    // Insert at the front
    static Node insertAtFront(Node head, int newData) {
        Node newNode = new Node(newData);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        return newNode;
    }

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

    public static void main(String[] args) {
        // Create a doubly linked list: 2 <-> 3 <-> 4
        Node head = new Node(2);
        head.next = new Node(3);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        // Print the original list
        System.out.println("Original Linked List:");
        printList(head);

        // Insert a new node at the front
        System.out.println("After inserting Node at the front:");
        int data = 1;
        head = insertAtFront(head, data);

        // Print the updated list
        printList(head);
    }
}

JavaScript Implementation

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

class DoublyLinkedList {
    // Insert at the front
    static insertAtFront(head, newData) {
        const newNode = new Node(newData);
        newNode.next = head;
        if (head !== null) {
            head.prev = newNode;
        }
        return newNode;
    }

    // Print the list
    static printList(head) {
        let curr = head;
        while (curr !== null) {
            process.stdout.write(" " + curr.data);
            curr = curr.next;
        }
        console.log();
    }
}

// Main execution
let head = new Node(2);
head.next = new Node(3);
head.next.prev = head;
head.next.next = new Node(4);
head.next.next.prev = head.next;

// Print the original list
console.log("Original Linked List:");
DoublyLinkedList.printList(head);

// Insert a new node at the front
console.log("After inserting Node at the front:");
head = DoublyLinkedList.insertAtFront(head, 1);

// Print the updated list
DoublyLinkedList.printList(head);

Python Implementation

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

class DoublyLinkedList:
    @staticmethod
    def insert_at_front(head, new_data):
        new_node = Node(new_data)
        new_node.next = head
        if head is not None:
            head.prev = new_node
        return new_node

    @staticmethod
    def print_list(head):
        curr = head
        while curr:
            print(curr.data, end=" ")
            curr = curr.next
        print()

# Main execution
# Create a doubly linked list: 2 <-> 3 <-> 4
head = Node(2)
head.next = Node(3)
head.next.prev = head
head.next.next = Node(4)
head.next.next.prev = head.next

# Print the original list
print("Original Linked List:")
DoublyLinkedList.print_list(head)

# Insert a new node at the front
print("After inserting Node at the front:")
head = DoublyLinkedList.insert_at_front(head, 1)

# Print the updated list
DoublyLinkedList.print_list(head)

C Implementation

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

// Define the structure of a doubly linked list node
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 after a given node
struct Node *insertAfter(struct Node *head, int key, int new_data) {
    struct Node *curr = head;

    // Traverse the list to find the node with the given key
    while (curr != NULL) {
        if (curr->data == key)
            break;
        curr = curr->next;
    }

    // If key is not found, return the original head
    if (curr == NULL)
        return head;

    // Create a new node
    struct Node *new_node = createNode(new_data);

    // Update links to insert the new node
    new_node->prev = curr;
    new_node->next = curr->next;

    // Update the next pointer of the current node
    curr->next = new_node;

    // Update the previous pointer of the new node's next
    if (new_node->next != NULL)
        new_node->next->prev = new_node;

    return head;
}

// Function to print the doubly linked list
void printList(struct Node *head) {
    struct Node *curr = head;
    while (curr != NULL) {
        printf(" %d", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // Create a doubly linked list: 1 <-> 3 <-> 4
    struct Node *head = createNode(1);
    head->next = createNode(3);
    head->next->prev = head;
    head->next->next = createNode(4);
    head->next->next->prev = head->next;

    // Print the original list
    printf("Original Linked List:");
    printList(head);

    // Insert a new node after node with key 1
    printf("Inserting Node with data 2 after node 1 :");
    head = insertAfter(head, 1, 2);

    // Print the updated list
    printList(head);

    return 0;
}

Step by Step Explanation

• Structure Definition:
  • The Node structure has three fields:
    • data: Stores the value.
    • next: Points to the next node in the list.
    • prev: Points to the previous node.
• createNode Function:
  • Allocates memory for a new node.
  • Initializes data, next, and prev.
• insertAfter Function:
  • Traverses the list to find the node with the given key.
  • If the key is found, creates a new node and updates:
    • prev of the new node to point to the current node.
    • next of the new node to point to the current node’s next.
  • Updates the next pointer of the current node to point to the new node.
  • Updates the prev pointer of the next node (if it exists) to point back to the new node.
• Printing Function:
  • Traverses the list and prints data of each node.
• Main Function:
  • Creates a doubly linked list: 1 <-> 3 <-> 4.
  • Inserts 2 after 1.
  • Prints both the original and updated lists.

C++ Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int new_data) : data(new_data), next(nullptr), prev(nullptr) {}
};

// Function to insert a node after a given node
Node* insertAfter(Node* head, int key, int new_data) {
    Node* curr = head;

    // Traverse to find the key
    while (curr) {
        if (curr->data == key)
            break;
        curr = curr->next;
    }

    // If key is not found, return the original head
    if (!curr)
        return head;

    // Create new node and update links
    Node* new_node = new Node(new_data);
    new_node->prev = curr;
    new_node->next = curr->next;
    curr->next = new_node;

    if (new_node->next)
        new_node->next->prev = new_node;

    return head;
}

// Function to print the list
void printList(Node* head) {
    Node* curr = head;
    while (curr) {
        cout << " " << curr->data;
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // Create a doubly linked list: 1 <-> 3 <-> 4
    Node* head = new Node(1);
    head->next = new Node(3);
    head->next->prev = head;
    head->next->next = new Node(4);
    head->next->next->prev = head->next;

    // Print the original list
    cout << "Original Linked List:";
    printList(head);

    // Insert a new node after node with key 1
    cout << "Inserting Node with data 2 after node 1 :";
    head = insertAfter(head, 1, 2);

    // Print the updated list
    printList(head);

    return 0;
}

Step by Step Explanation

• Structure Definition:
  • The Node structure has three fields:
    • data: Stores the value.
    • next: Points to the next node in the list.
    • prev: Points to the previous node.
• createNode Function:
  • Allocates memory for a new node.
  • Initializes data, next, and prev.
• insertAfter Function:
  • Traverses the list to find the node with the given key.
  • If the key is found, creates a new node and updates:
    • prev of the new node to point to the current node.
    • next of the new node to point to the current node’s next.
  • Updates the next pointer of the current node to point to the new node.
  • Updates the prev pointer of the next node (if it exists) to point back to the new node.
• Printing Function:
  • Traverses the list and prints data of each node.
• Main Function:
  • Creates a doubly linked list: 1 <-> 3 <-> 4.
  • Inserts 2 after 1.
  • Prints both the original and updated lists.

C# Implementation

using System;

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

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

class DoublyLinkedList {
    public Node InsertAfter(Node head, int key, int newData) {
        Node current = head;

        // Traverse the list to find the key
        while (current != null) {
            if (current.data == key)
                break;
            current = current.next;
        }

        // If key is not found, return the original head
        if (current == null) return head;

        // Create a new node
        Node newNode = new Node(newData);

        // Update links to insert the new node
        newNode.prev = current;
        newNode.next = current.next;

        if (current.next != null)
            current.next.prev = newNode;

        current.next = newNode;

        return head;
    }

    public void PrintList(Node head) {
        Node current = head;
        while (current != null) {
            Console.Write(" " + current.data);
            current = current.next;
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();

        // Create a doubly linked list: 1 <-> 3 <-> 4
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        // Print the original list
        Console.WriteLine("Original Linked List:");
        dll.PrintList(head);

        // Insert a new node after node with key 1
        Console.WriteLine("Inserting Node with data 2 after node 1 :");
        head = dll.InsertAfter(head, 1, 2);

        // Print the updated list
        dll.PrintList(head);
    }
}

Explanation

• Class Node:
  • Defines a doubly linked list node with data, next, and prev properties.
• Class DoublyLinkedList:
  • Contains the method InsertAfter to insert a new node after a specific key.
  • Updates the links (next and prev) of the nodes involved.
• InsertAfter Method:
  • Traverses the list to find the key.
  • If the key is found:
    • Creates a new node.
    • Updates the pointers of the current node and the new node.
    • Updates the prev pointer of the new node’s next node, if it exists.
• Printing Method:
  • Traverses the list from the head, printing each node’s data.
• Main Method:
  • Creates a doubly linked list with hardcoded values.
  • Inserts a node with data = 2 after data = 1.
  • Prints the original and updated lists.

Java Implementation

class Node {
    int data;
    Node next;
    Node prev;

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

class DoublyLinkedList {
    // Method to insert a new node after a given key
    Node insertAfter(Node head, int key, int newData) {
        Node current = head;

        // Traverse to find the key
        while (current != null) {
            if (current.data == key)
                break;
            current = current.next;
        }

        // If key is not found, return the original head
        if (current == null) return head;

        // Create a new node
        Node newNode = new Node(newData);

        // Update links
        newNode.prev = current;
        newNode.next = current.next;

        if (current.next != null)
            current.next.prev = newNode;

        current.next = newNode;

        return head;
    }

    // Method to print the list
    void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(" " + current.data);
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();

        // Create a doubly linked list: 1 <-> 3 <-> 4
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.prev = head;
        head.next.next = new Node(4);
        head.next.next.prev = head.next;

        // Print the original list
        System.out.println("Original Linked List:");
        dll.printList(head);

        // Insert a new node after node with key 1
        System.out.println("Inserting Node with data 2 after node 1 :");
        head = dll.insertAfter(head, 1, 2);

        // Print the updated list
        dll.printList(head);
    }
}

Step-by-Step Explanation

1. Node Class

The Node class represents each node in the doubly linked list.

• Attributes:
  • data: Stores the integer data for the node.
  • next: Points to the next node in the list.
  • prev: Points to the previous node in the list.
• Constructor:
  • Initializes the data attribute with the given value.
  • Sets next and prev pointers to null.

2. DoublyLinkedList Class

(a.) insertAfter Method

• Input Parameters:
  • Node head: The head node of the doubly linked list.
  • int key: The value after which the new node will be inserted.
  • int newData: The data for the new node.
• Traversal:
  • Starts traversing the list from the head using a pointer (current).
  • Compares the data of each node with key until it finds the node with the key or reaches the end of the list.
• If key Is Not Found:
  • If the traversal completes without finding the key (current == null), the method returns the original list without making any changes.
• Node Creation:
  • Creates a new Node object, passing newData to its constructor.
• Updating Links:
  • Sets newNode.prev = current (points the new node’s prev to the node containing the key).
  • Sets newNode.next = current.next (points the new node’s next to the node that follows the current node).
  • If current.next exists, updates its prev pointer to the newNode.
  • Updates current.next to point to newNode, effectively inserting the new node after the current node.

(b.) printList Method

• Traversal:
  • Starts at the head node and iterates through the list.
  • Prints the data of each node until the end of the list is reached.

3. Main Class

• Creating the Doubly Linked List:
  • Constructs a hardcoded list: 1 <-> 3 <-> 4.
  • Manually links the next and prev pointers for each node.
• Printing the Original List:
  • Calls the printList method to display the initial list.
• Inserting a New Node:
  • Calls the insertAfter method to insert a node with data = 2 after the node with data = 1.
• Printing the Updated List:
  • Calls the printList method to display the modified list.

JavaScript Implementation

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

class DoublyLinkedList {
    insertAfter(head, key, newData) {
        let current = head;

        // Traverse to find the key
        while (current) {
            if (current.data === key) break;
            current = current.next;
        }

        // If key is not found, return the original head
        if (!current) return head;

        // Create a new node
        const newNode = new Node(newData);

        // Update links
        newNode.prev = current;
        newNode.next = current.next;

        if (current.next) current.next.prev = newNode;

        current.next = newNode;

        return head;
    }

    printList(head) {
        let current = head;
        let result = [];
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        console.log(result.join(" "));
    }
}

// Create a doubly linked list: 1 <-> 3 <-> 4
const dll = new DoublyLinkedList();
let head = new Node(1);
head.next = new Node(3);
head.next.prev = head;
head.next.next = new Node(4);
head.next.next.prev = head.next;

// Print the original list
console.log("Original Linked List:");
dll.printList(head);

// Insert a new node after node with key 1
console.log("Inserting Node with data 2 after node 1 :");
head = dll.insertAfter(head, 1, 2);

// Print the updated list
dll.printList(head);

Step-by-Step Explanation

1. Node Class

The Node class represents a node in the doubly linked list.

• Attributes:
  • data: Stores the value of the node.
  • next: Points to the next node in the list.
  • prev: Points to the previous node in the list.
• Constructor:
  • Accepts the data and initializes the next and prev pointers as null.

2. DoublyLinkedList Class

(a.) insertAfter Method

• Input Parameters:
  • head: The head node of the doubly linked list.
  • key: The value after which the new node will be inserted.
  • newData: The data for the new node.
• Traversal:
  • Uses a variable current to traverse the list from the head.
  • Checks if the data of each node matches the key.
• If key Is Not Found:
  • If the traversal completes and the key is not found (current === null), the method returns the original list unchanged.
• Node Creation:
  • Creates a new Node object, passing newData to its constructor.
• Updating Links:
  • Sets newNode.prev = current (points the new node’s prev to the node containing the key).
  • Sets newNode.next = current.next (points the new node’s next to the node following the current node).
  • If current.next exists, updates its prev pointer to the newNode.
  • Updates current.next to point to newNode, inserting the new node after the current node.

b. printList Method

• Traversal:
  • Starts from the head and iterates through the list.
  • Stores the data of each node in an array.
  • Joins the array into a string and prints the result.

3. Main Program

• Creating the Doubly Linked List:
  • Constructs a list: 1 <-> 3 <-> 4.
  • Manually sets the next and prev pointers for each node.
• Printing the Original List:
  • Calls the printList method to display the initial list.
• Inserting a New Node:
  • Calls the insertAfter method to insert a node with data = 2 after the node with data = 1.
• Printing the Updated List:
  • Calls the printList method to display the modified list.

Python Implementation

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


class DoublyLinkedList:
    # Function to insert a new node after a given key
    def insert_after(self, head, key, new_data):
        current = head

        # Traverse to find the key
        while current:
            if current.data == key:
                break
            current = current.next

        # If key is not found, return the original head
        if not current:
            return head

        # Create a new node
        new_node = Node(new_data)

        # Update links
        new_node.prev = current
        new_node.next = current.next

        if current.next:
            current.next.prev = new_node

        current.next = new_node

        return head

    # Function to print the list
    def print_list(self, head):
        current = head
        while current:
            print(current.data, end=" ")
            current = current.next
        print()


# Create a doubly linked list: 1 <-> 3 <-> 4
dll = DoublyLinkedList()
head = Node(1)
head.next = Node(3)
head.next.prev = head
head.next.next = Node(4)
head.next.next.prev = head.next

# Print the original list
print("Original Linked List:")
dll.print_list(head)

# Insert a new node after node with key 1
print("Inserting Node with data 2 after node 1:")
head = dll.insert_after(head, 1, 2)

# Print the updated list
dll.print_list(head)

Step-by-Step Explanation

(1.) Node Class

• Purpose: Represents each node in the doubly linked list.
• Attributes:
  • data: Stores the data for the node.
  • next: Points to the next node in the list.
  • prev: Points to the previous node in the list.
• Initialization: The __init__ constructor initializes the data, next, and prev pointers to None.

(2.) DoublyLinkedList Class

• This class contains utility methods for the doubly linked list.

(a.) insert_after Method

• Input Parameters:
  • head: The head node of the doubly linked list.
  • key: The value after which the new node is to be inserted.
  • new_data: The data of the new node.
• Traversal:
  • Starts from the head and traverses through the list to locate the node containing the key.
  • If the key is not found (current becomes None), it returns the original list without any modification.
• Node Creation:
  • A new node is created with new_data.
• Updating Links:
  • new_node.prev is set to current (the node containing the key).
  • new_node.next is set to current.next.
  • If current.next exists, its prev is updated to point to new_node.
  • Finally, current.next is updated to point to new_node.

(b.) print_list Method

• Traverses the list starting from the head and prints the data of each node until the end of the list.

(3.) Main Program

• List Creation:
  • Creates a hardcoded doubly linked list: 1 <-> 3 <-> 4.
  • Links are established manually for the next and prev pointers of the nodes.
• Print the Original List:
  • Calls the print_list method to display the list.
• Insert New Node:
  • Calls the insert_after method to insert a node with data = 2 after the node with data = 1.
• Print the Updated List:
  • Prints the modified list to confirm the insertion.

C Program Implementation

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

C++ Implementation

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

C# Implementation

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

Java Implementation

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

JavaScript Implementation

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();

Python Implementation

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()

C Program Implementation

#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 at a given position
struct Node* insertAtPosition(struct Node *head, int pos, int new_data) {
    struct Node *new_node = createNode(new_data);

    // Insertion at the beginning
    if (pos == 1) {
        new_node->next = head;
        if (head != NULL) {
            head->prev = new_node;
        }
        head = new_node;
        return head;
    }

    struct Node *curr = head;
    for (int i = 1; i < pos - 1 && curr != NULL; ++i) {
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("Position is out of bounds.\n");
        free(new_node);
        return head;
    }

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

    return head;
}

// Function to print the linked list
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(2);
    head->next->prev = head;
    head->next->next = createNode(4);
    head->next->next->prev = head->next;

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

    int data = 3;
    int pos = 3;
    head = insertAtPosition(head, pos, data);

    printf("Inserting Node with data 3 at position 3: ");
    printList(head);

    return 0;
}

Step by Step Explanation

• Define the Node Structure
  • A Node contains three elements:
    • data: The actual data of the node.
    • next: A pointer/reference to the next node in the list.
    • prev: A pointer/reference to the previous node in the list.
• Create a New Node Function
  • The function createNode(int new_data) will create a new node with the provided data and initialize its next and prev pointers to NULL (or None in Python, JavaScript, Java, C#).
• Insert a Node at a Given Position
  • The function insertAtPosition(struct Node *head, int pos, int new_data) inserts a new node at the specified position:
    • If the position is 1, the new node is inserted at the head of the list.
    • For other positions, the list is traversed to the correct location, and the new node is inserted.
    • The list is updated to link the previous and next nodes correctly.
• Print the List
  • The printList() function will traverse the list and print each node’s data until the end of the list is reached.

C++ Implementation

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

Node* insertAtPosition(Node* head, int pos, int new_data) {
    Node* new_node = new Node(new_data);

    if (pos == 1) {
        new_node->next = head;
        if (head != nullptr) {
            head->prev = new_node;
        }
        head = new_node;
        return head;
    }

    Node* curr = head;
    for (int i = 1; i < pos - 1 && curr != nullptr; ++i) {
        curr = curr->next;
    }

    if (curr == nullptr) {
        cout << "Position is out of bounds." << endl;
        delete new_node;
        return head;
    }

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

    return head;
}

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

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(4);
    head->next->next->prev = head->next;

    cout << "Original Linked List: ";
    printList(head);

    int data = 3;
    int pos = 3;
    head = insertAtPosition(head, pos, data);

    cout << "Inserting Node with data 3 at position 3: ";
    printList(head);

    return 0;
}

C# Implementation

using System;

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

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

class Program {
    static Node InsertAtPosition(Node head, int pos, int new_data) {
        Node newNode = new Node(new_data);

        if (pos == 1) {
            newNode.Next = head;
            if (head != null) {
                head.Prev = newNode;
            }
            head = newNode;
            return head;
        }

        Node curr = head;
        for (int i = 1; i < pos - 1 && curr != null; ++i) {
            curr = curr.Next;
        }

        if (curr == null) {
            Console.WriteLine("Position is out of bounds.");
            return head;
        }

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

        return head;
    }

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

    static void Main() {
        Node head = new Node(1);
        head.Next = new Node(2);
        head.Next.Prev = head;
        head.Next.Next = new Node(4);
        head.Next.Next.Prev = head.Next;

        Console.Write("Original Linked List: ");
        PrintList(head);

        int data = 3;
        int pos = 3;
        head = InsertAtPosition(head, pos, data);

        Console.Write("Inserting Node with data 3 at position 3: ");
        PrintList(head);
    }
}

Java Implementation

class Node {
    int data;
    Node next, prev;

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

public class DoublyLinkedList {

    static Node insertAtPosition(Node head, int pos, int new_data) {
        Node newNode = new Node(new_data);

        if (pos == 1) {
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            }
            head = newNode;
            return head;
        }

        Node curr = head;
        for (int i = 1; i < pos - 1 && curr != null; ++i) {
            curr = curr.next;
        }

        if (curr == null) {
            System.out.println("Position is out of bounds.");
            return head;
        }

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

        return head;
    }

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

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

        System.out.print("Original Linked List: ");
        printList(head);

        int data = 3;
        int pos = 3;
        head = insertAtPosition(head, pos, data);

        System.out.print("Inserting Node with data 3 at position 3: ");
        printList(head);
    }
}

JavaScript Implementation

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

function insertAtPosition(head, pos, new_data) {
    let newNode = new Node(new_data);

    if (pos === 1) {
        newNode.next = head;
        if (head !== null) {
            head.prev = newNode;
        }
        head = newNode;
        return head;
    }

    let curr = head;
    for (let i = 1; i < pos - 1 && curr !== null; ++i) {
        curr = curr.next;
    }

    if (curr === null) {
        console.log("Position is out of bounds.");
        return head;
    }

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

    return head;
}

function printList(head) {
    let curr = head;
    while (curr !== null) {
        process.stdout.write(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}

let head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(4);
head.next.next.prev = head.next;

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

let data = 3;
let pos = 3;
head = insertAtPosition(head, pos, data);

console.log("Inserting Node with data 3 at position 3: ");
printList(head);

Python Implementation

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

def insert_at_position(head, pos, new_data):
    new_node = Node(new_data)

    if pos == 1:
        new_node.next = head
        if head is not None:
            head.prev = new_node
        head = new_node
        return head

    curr = head
    for _ in range(1, pos - 1):
        if curr is None:
            print("Position is out of bounds.")
            return head
        curr = curr.next

    new_node.prev = curr
    new_node.next = curr.next
    curr.next = new_node
    if new_node.next is not None:
        new_node.next.prev = new_node

    return head

def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()

head = Node(1)
head.next = Node(2)
head.next.prev = head
head.next.next = Node(4)
head.next.next.prev = head.next

print("Original Linked List: ")
print_list(head)

data = 3
pos = 3
head = insert_at_position(head, pos, data)

print("Inserting Node with data 3 at position 3: ")
print_list(head)

C Program Implementation

#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 at the end of the doubly linked list
struct Node* insertEnd(struct Node *head, int new_data) {
    struct Node *new_node = createNode(new_data);

    if (head == NULL) {
        head = new_node;
    } else {
        struct Node *curr = head;
        while (curr->next != NULL) {
            curr = curr->next;
        }

        curr->next = new_node;
        new_node->prev = curr;
    }

    return head;
}

// Function to print the linked list
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(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;

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

    printf("Inserting Node with data 4 at the end: ");
    head = insertEnd(head, 4);

    printList(head);

    return 0;
}

Step by Step Explanation

• Define the Node Structure/Class:
  • A Node class/struct is created to represent each element in the doubly linked list. It contains:
    • data: The value stored in the node.
    • next: A pointer/reference to the next node.
    • prev: A pointer/reference to the previous node.
• Create a Node Function:
  • The function createNode(int new_data) initializes a new node with the given data and sets both next and prev pointers to NULL.
• Insert at the End Function:
  • The function insertEnd() inserts a new node at the end of the doubly linked list:
    • If the list is empty (head == NULL), the new node becomes the head.
    • If the list is not empty, the function traverses to the last node and attaches the new node at the end.
    • The prev pointer of the new node is set to the last node, and the next pointer of the last node is set to the new node.
• Print the List:
  • The printList() function traverses the list from the head and prints each node’s data.

C++ Implementation

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

Node* insertEnd(Node* head, int new_data) {
    Node* new_node = new Node(new_data);

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

        curr->next = new_node;
        new_node->prev = curr;
    }

    return head;
}

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

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;

    cout << "Original Linked List: ";
    printList(head);

    cout << "Inserting Node with data 4 at the end: ";
    head = insertEnd(head, 4);

    printList(head);

    return 0;
}

C# Implementation

using System;

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

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

class Program {
    static Node InsertEnd(Node head, int new_data) {
        Node newNode = new Node(new_data);

        if (head == null) {
            head = newNode;
        } else {
            Node curr = head;
            while (curr.Next != null) {
                curr = curr.Next;
            }

            curr.Next = newNode;
            newNode.Prev = curr;
        }

        return head;
    }

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

    static void Main() {
        Node head = new Node(1);
        head.Next = new Node(2);
        head.Next.Prev = head;
        head.Next.Next = new Node(3);
        head.Next.Next.Prev = head.Next;

        Console.Write("Original Linked List: ");
        PrintList(head);

        Console.Write("Inserting Node with data 4 at the end: ");
        head = InsertEnd(head, 4);

        PrintList(head);
    }
}

Java Implementation

class Node {
    int data;
    Node next, prev;

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

public class DoublyLinkedList {

    static Node insertEnd(Node head, int new_data) {
        Node newNode = new Node(new_data);

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

            curr.next = newNode;
            newNode.prev = curr;
        }

        return head;
    }

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

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

        System.out.print("Original Linked List: ");
        printList(head);

        System.out.print("Inserting Node with data 4 at the end: ");
        head = insertEnd(head, 4);

        printList(head);
    }
}

JavaScript Implementation

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

function insertEnd(head, new_data) {
    let newNode = new Node(new_data);

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

        curr.next = newNode;
        newNode.prev = curr;
    }

    return head;
}

function printList(head) {
    let curr = head;
    while (curr !== null) {
        process.stdout.write(curr.data + " ");
        curr = curr.next;
    }
    console.log();
}

let head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;

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

let data = 4;
head = insertEnd(head, data);

console.log("Inserting Node with data 4 at the end: ");
printList(head);

Python Implementation

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

def insert_end(head, new_data):
    new_node = Node(new_data)

    if head is None:
        head = new_node
    else:
        curr = head
        while curr.next is not None:
            curr = curr.next

        curr.next = new_node
        new_node.prev = curr

    return head

def print_list(head):
    curr = head
    while curr is not None:
        print(curr.data, end=" ")
        curr = curr.next
    print()

head = Node(1)
head.next = Node(2)
head.next.prev = head
head.next.next = Node(3)
head.next.next.prev = head.next

print("Original Linked List: ")
print_list(head)

data = 4
head = insert_end(head, data)

print("Inserting Node with data 4 at the end: ")
print_list(head)