Close Menu
Data Structures

Inserting a Node at the Beginning of a Doubly Linked List: A Detailed Exploration

By

In this detailed guide, we will delve into the process of inserting a node at the beginning/front of a Doubly Linked List (DLL). This operation is an essential concept in computer science and plays a critical role in data structures. By understanding this technique, programmers can efficiently manipulate and manage linked lists, which are fundamental for dynamic memory usage and flexible data organization.

What is a Doubly Linked List?

A Doubly Linked List is a type of Linked List where each node consists of three parts:

  1. Data: The actual value stored in the node.
  2. Pointer to the Previous Node (prev): A reference that points to the preceding node in the list.
  3. Pointer to the Next Node (next): A reference that points to the succeeding node in the list.

This structure allows traversal in both directions, making DLLs more versatile than Singly Linked Lists (SLLs), where traversal is only possible in one direction.

Insertion at the Beginning in Doubly Linked List

Why Insert at the Beginning?

Inserting a node at the beginning of a Doubly Linked List is a common operation used in numerous scenarios:

  • Dynamic Stack Implementation: By adding elements to the head, the list behaves like a stack (LIFO structure).
  • Priority Queues: Insertions at the start can represent high-priority elements.
  • Dynamic Memory Usage: Quickly updating lists without needing to shift memory as in arrays.

Adding at the start is efficient, as it takes constant time ( O(1) ), regardless of the list’s length, making it ideal for scenarios requiring high-speed insertions.

Approach to Insert at the beginning of a Doubly Linked List

To insert a node at the beginning of a Doubly Linked List, follow these steps:

1. Create a New Node

First, a new node is created with the given data.

  • Set the prev pointer of this new node to NULL because it will be the first node of the list.
  • Set the next pointer of this new node to the current head of the list.

This ensures that the new node points forward to the current first node while having no previous node.

2. Update the Current Head

If the list is not empty, the current head node’s prev pointer must be updated to point to the newly created node. This links the new node to the existing list.

3. Return the New Node

Finally, return the newly created node as the new head of the Doubly Linked List.

Algorithm

The steps for the algorithm are as follows:

  • Allocate Memory for the New Node:
    • Create a new node using the data provided.
    • Example: Node* new_node = new Node(data);
  • Set Prev and Next Pointers of the New Node:
    • new_node->prev = NULL;
    • new_node->next = head;
  • Update Head Node’s Prev Pointer (If the List is Not Empty):
    • if (head != NULL) head->prev = new_node;
  • Make the New Node the Head:
    • head = new_node;

Example 1: Non-Empty List

Input:

  • Linked List: 2 <-> 3 <-> 4 -> NULL
  • New Node Data: 1

Execution:

  • Create a new node with data 1:
    • new_node->prev = NULL;
    • new_node->next = 2;
  • Update the current head (node 2):
    • head->prev = new_node;
  • Set the new node as the head:
    • head = new_node;

Output:

The updated list is: 1 <-> 2 <-> 3 <-> 4 -> NULL.

Example 2: Empty List

Input:

  • Linked List: NULL
  • New Node Data: 10

Execution:

  • Create a new node with data 10:
    • new_node->prev = NULL;
    • new_node->next = NULL;
  • Set the new node as the head:
    • head = new_node;

Output:

The updated list is: 10 -> NULL.

Code Implementation

Below is the C++ implementation of the discussed approach:

#include <iostream>
using namespace std;

// Node Structure
struct Node {
    int data;
    Node* prev;
    Node* next;

    // Constructor to create a new node
    Node(int val) {
        data = val;
        prev = NULL;
        next = NULL;
    }
};

// Function to insert a node at the beginning of a doubly linked list
Node* insertAtBeginning(Node* head, int data) {
    // Create a new node
    Node* new_node = new Node(data);

    // Update pointers
    new_node->next = head;
    if (head != NULL) {
        head->prev = new_node;
    }

    // Return the new head
    return new_node;
}

// Function to display the linked list
void display(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " <-> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = NULL;

    // Insert nodes
    head = insertAtBeginning(head, 4);
    head = insertAtBeginning(head, 3);
    head = insertAtBeginning(head, 2);
    head = insertAtBeginning(head, 1);

    // Display the list
    display(head);

    return 0;
}

Complexity Analysis

  • Time Complexity: ( O(1) )
    Since we only update pointers, the operation is performed in constant time, regardless of the size of the list.
  • Space Complexity: ( O(1) )
    The space usage is constant as we only allocate memory for the new node.

Code Implementation in Multiple Programming Languages

Insertion at the Beginning in Doubly Linked List

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

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)

Output Across all Languages

Original Linked List: 2 3 4
After inserting Node at the front: 1 2 3 4
  • Time Complexity: O(1)
  • Auxiliary Space: O(1)

Detailed Step-by-Step Explanation

  • Node Structure: Define a node structure with three fields: data (to store the value), next (pointer to the next node), and prev (pointer to the previous node).
  • Create Node Function: Dynamically allocate or instantiate a new node and initialize it with the given data.
  • Insert at Front: Create a new node, point its next to the current head, and update the current head’s prev pointer (if the list is not empty). Finally, return the new node as the updated head.
  • Print List: Traverse the list starting from the head, printing the data of each node.
  • Main Function: Create a hardcoded DLL and perform the insert operation to verify the functionality.

Key Differences Between C, C++, C#, Java, JavaScript, and Python

Here’s a comparison of C, C++, C#, Java, JavaScript, and Python based on syntax, memory management, data structure handling, and printing, derived from the above code examples:

1. Syntax

  • C Programming:
    • Procedural programming with functions.
    • Manual memory allocation using malloc.
    • Structs are used to define the data structure (no methods in the struct itself).
    • Pointers are extensively used for linking nodes.
    • Code tends to be verbose due to the manual management of memory and pointers.
  • C++ Programming:
    • Object-oriented and procedural paradigms.
    • class keyword allows defining objects with methods and constructors.
    • new operator is used for memory allocation (no explicit malloc).
    • Pointer-like references (Node*) simplify node linking.
    • Inline cout statements make output simpler.
  • C# Programming:
    • Purely object-oriented.
    • Struct-like nodes implemented using class with methods and properties.
    • Memory management is handled by the garbage collector, so explicit allocation/deallocation is unnecessary.
    • Access modifiers like public are mandatory for class members.
  • Java Programming:
    • Object-oriented and strictly class-based.
    • Memory management is automatic via garbage collection.
    • Uses new to create objects.
    • The System.out.println() method is verbose for printing compared to other languages.
  • JavaScript Programming:
    • Dynamically typed, interpreted language with object-oriented and functional capabilities.
    • class and constructor mimic object-oriented patterns.
    • Memory management is implicit via the JavaScript Engine’s garbage collector.
    • Printing uses console.log() or process.stdout.write().
  • Python:
    • Simple, dynamically typed, and highly readable.
    • Uses class to define structures, with straightforward syntax.
    • Automatic memory management via the Python garbage collector.
    • Printing is the simplest with the print() function.

2. Memory Management

  • C Programming:
    • Manual memory management using malloc and free (not shown here but necessary to avoid memory leaks).
    • Direct pointers are used, making it prone to segmentation faults.
  • C++ Programming:
    • Semi-automatic memory management: objects are allocated with new but must be manually deallocated with delete unless smart pointers are used.
    • Uses constructors to initialize nodes.
  • C# Programming:
    • Fully automated memory management with garbage collection.
    • No explicit memory allocation or pointer usage for data structures.
  • Java Programming:
    • Similar to C# with garbage collection.
    • Memory for objects is automatically handled by the Java Virtual Machine (JVM).
  • JavaScript Programming:
    • Fully automatic memory management is handled by the JavaScript runtime.
    • Simplified for dynamic, browser-based, or server-side programming.
  • Python Programming:
    • Fully automatic memory management with garbage collection.
    • Memory allocation and deallocation are implicit.

3. Data Structure Handling

  • C Programming:
    • Relies on struct for defining a data structure (no methods inside the structure).
    • Separate functions are required to manipulate data.
  • C++ Programming:
    • Combines struct and class, allowing methods and constructors to operate on the structure.
    • Node creation and list handling are encapsulated within classes.
  • C# Programming:
    • Fully object-oriented; class is used exclusively.
    • Supports properties and methods, making data structure handling abstract and simple.
  • Java Programming:
    • Similar to C#; uses class to encapsulate data and behavior.
  • JavaScript Programming:
    • Dynamic and flexible with data handling.
    • Uses class to mimic traditional OOP patterns, but objects are inherently flexible.
  • Python Programming:
    • The most straightforward approach with class.
    • Dynamically typed and does not require explicit data types for variables.

4. Printing

  • C Programming:
    • Uses printf with format specifiers (%d for integers).
    • Requires explicit newline (\n) for formatting.
  • C++ Programming:
    • Uses cout with insertion operator (<<).
    • Output is clean and intuitive.
  • C# Programming:
    • Uses Console.WriteLine, similar to Java but less verbose.
  • Java Programming:
    • Relies on System.out.println() for printing, which is verbose compared to other languages.
  • JavaScript Programming:
    • Uses console.log() or process.stdout.write() for output, commonly used in web and server contexts.
  • Python Programming:
    • Simplest output mechanism using print().

Summary Table

FeatureCC++C#JavaJavaScriptPython
Syntax StyleProceduralOOP + ProceduralPurely OOPStrict OOPDynamic, HybridSimple and Dynamic
Memory ManagementManual (malloc)Semi-ManualAutomaticAutomaticAutomaticAutomatic
Data Structuresstructclassclassclassclassclass
PrintingprintfcoutConsole.WriteLineSystem.out.printlnconsole.log()print()

**Full Form of OOP is – Object-Oriented Programming**

This comparison highlights the strengths and weaknesses of each language, helping to choose the right tool for a given problem.

Conclusion

Inserting a node at the beginning of a Doubly Linked List is a simple yet powerful operation. It enables efficient data handling in a variety of real-world applications, from stack implementations to memory management systems. By mastering this operation, programmers can enhance their understanding of linked lists and optimize their algorithms for speed and flexibility.

  1. Insertion in Doubly Linked List with Implementation: A Detailed Exploration
  2. Inserting a Node at the Beginning of a Doubly Linked List: A Detailed Exploration
  3. Inserting a Node After a Given Node in a Doubly Linked List: A Detailed Exploration
  4. Inserting a Node Before a Given Node in a Doubly Linked List: A Detailed Exploration
  5. Inserting a Node at a Specific Position in a Doubly Linked List: A Detailed Exploration
  6. Inserting a New Node at the End of a Doubly Linked List: A Detailed Exploration

Frequently Asked Questions (FAQs)

What is a Doubly Linked List (DLL)?

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

  • Data: The actual value or information stored in the node.
  • Prev Pointer: A reference (pointer) to the previous node in the list.
  • Next Pointer: A reference (pointer) to the next node in the list.

This structure enables bidirectional traversal, meaning you can navigate both forward and backward through the list. This contrasts with Singly Linked Lists (SLLs), where nodes only link in one direction. DLLs are used in applications like navigation systems, undo/redo functionality in software, and memory management.

Why is it efficient to insert a node at the beginning of a Doubly Linked List?

Inserting a node at the beginning of a Doubly Linked List is efficient because:

  • It takes constant time { O(1) }.
  • Only a few pointers need to be updated: the new node’s next pointer, the current head’s previous pointer, and the head pointer itself.
  • No traversal is needed, unlike in operations that involve inserting at arbitrary positions or at the end of the list.

This makes it ideal for scenarios where speed is critical, such as implementing stacks or high-priority insertions.

What are the steps to insert a node at the beginning of a Doubly Linked List?

The steps are as follows:

  • Create a New Node:
    • Allocate memory for the new node.
    • Set its prev pointer to NULL since it will be the first node.
    • Set its next pointer to the current head of the list.
  • Update the Current Head (if the list is not empty):
    • Update the previous pointer of the current head node to point to the new node.
  • Set the New Node as the Head:
    • Update the head pointer to point to the new node.

These steps ensure that the new node is correctly inserted at the beginning while maintaining the structure of the Doubly Linked List.

What happens if the list is empty when inserted at the beginning?

If the Doubly Linked List is empty, inserting a new node is straightforward:

  • The new node’s prev and next pointers are set to NULL since there are no other nodes in the list.
  • The head pointer is updated to point to the new node.

For example, if the list is initially NULL and a new node with data 10 is inserted, the list becomes 10 -> NULL.

Can this operation be implemented in multiple programming languages?

Yes, this operation can be implemented in various programming languages, such as C++, Java, Python, and C. Below are brief examples:

  • C++:
    Use structures and pointers to define nodes and manage memory dynamically.
    Example:
  struct Node {
      int data;
      Node* prev;
      Node* next;
  };
  • Python:
    Leverage classes and object-oriented programming to define the Node structure and handle list operations.
    Example:
  class Node:
      def __init__(self, data):
          self.data = data
          self.prev = None
          self.next = None

The implementation logic remains consistent across languages.

What is the difference between Singly Linked Lists (SLLs) and Doubly Linked Lists (DLLs)?

The main differences are:

FeatureSingly Linked List (SLL)Doubly Linked List (DLL)
Pointers per NodeOne pointer (to the next node)Two pointers (prev and next)
TraversalUnidirectional (forward only)Bidirectional (forward and backward)
Memory OverheadLower (fewer pointers)Higher (extra pointer per node)
Insert/Delete OpsMore complex (especially at arbitrary positions)Simplified due to dual pointers

What is the time complexity of inserting at the beginning of a Doubly Linked List?

The time complexity is ( O(1) ) because:

  • No traversal is required to locate the position for insertion.
  • Only three-pointers are updated:
    • New Node’s Next Pointer.
    • Current Head’s Prev Pointer (if the list is not empty).
    • Head Pointer.

This efficiency makes it an ideal choice for operations requiring frequent insertions at the front.

What are some practical applications of inserting nodes at the beginning of a DLL?

Practical applications include:

  • Dynamic Stacks: Using a DLL, elements can be added to the front to mimic stack behavior (LIFO).
  • Browser History: Storing visited URLs in reverse chronological order for navigation.
  • Undo/Redo Operations: Maintaining state changes in software to allow forward and backward navigation.
  • Priority Queues: Inserting high-priority elements at the start.

By supporting bidirectional traversal, DLLs improve flexibility in these applications.

How does the implementation differ when inserting at other positions in the list?

When inserting at arbitrary positions (e.g., middle or end), the following changes occur:

  • Traversal is required to locate the insertion point, increasing the time complexity to ( O(n) ).
  • Pointer updates are more complex:
    • The new node must connect to the nodes before and after it.
    • The nodes at the insertion point must update their previous and next pointers accordingly.

In contrast, inserting at the beginning involves fewer steps and is faster.

Can you provide a real-world example demonstrating this concept?

Scenario: A music playlist app maintains a list of songs. Each song is represented as a node in a Doubly Linked List, with the ability to navigate forward and backward.

Requirement: Add a new song to the beginning of the playlist.

Implementation:

  • Create a new node for the song.
  • Set its prev pointer to NULL.
  • Update its next pointer to point to the current head of the playlist.
  • Update the current head’s prev pointer (if the list is not empty).
  • Make the new node the head of the playlist.

This operation ensures the new song becomes the first song in the playlist, allowing easy addition without disrupting the list’s structure.

Share.
Examsmeta Logo

Examsmeta is your one-stop destination for comprehensive educational resources across a wide array of disciplines. At Examsmeta, we are dedicated to providing high-quality, topic-wise notes and articles that cater to students, educators, researchers, and lifelong learners. Our mission is to make learning accessible, engaging, and effective for everyone. Our mission is to empower learners by offering detailed, accurate, and up-to-date educational content. We strive to foster a love for learning and to support the academic and professional growth of our users. Whether you're preparing for exams, conducting research, or simply expanding your knowledge, Examsmeta is here to guide you every step of the way.