Insertion in Doubly Linked List (DLL)

Welcome to the world of data structures! Today, we'll delve into the fascinating concept of Doubly Linked Lists (DLL) and explore how to perform insertion operations. By the end of this tutorial, you'll be able to create and manage DLLs with ease. 🎯

What is a Doubly Linked List (DLL)?

A Doubly Linked List (DLL) is a linear data structure consisting of nodes, where each node contains a data part and two reference parts (pointers) pointing to the adjacent nodes, one for the previous node and one for the next node. This makes DLLs unique, as they allow bidirectional traversal. 📝

Creating a Doubly Linked List

To create a DLL, we first need to define the Node structure. Here's a simple example in C++:

cpp

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

In this structure, data holds the actual data of the node, while next and prev are pointers pointing to the next and previous nodes, respectively.

Insertion in a Doubly Linked List

There are two main ways to insert a new node into a DLL: at the beginning (also known as the head) and at the end (also known as the tail).

Insertion at the Head (Front Insertion)

To insert a node at the head (beginning) of a DLL, follow these steps:

Create a new node with the desired data.
Set the next pointer of the new node to point to the current head node (if the DLL is empty, set it to NULL).
Set the prev pointer of the new node to NULL (as it will be the head).
Update the prev pointer of the current head node (if the DLL is not empty) to point to the new node.
Set the next pointer of the current head node (if the DLL is not empty) to point to the new node.
The new node is now the head of the DLL.

Here's an example code for front insertion in C++:

cpp

void insertAtHead(Node*& head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    newNode->prev = NULL;
    if (head != NULL) {
        head->prev = newNode;
    }
    head = newNode;
}

Insertion at the Tail (Rear Insertion)

To insert a node at the tail (end) of a DLL, follow these steps:

Create a new node with the desired data.
Set the prev pointer of the new node to point to the current tail node (if the DLL is empty, set it to NULL).
Set the next pointer of the new node to NULL (as it will be the tail).
Update the next pointer of the current tail node (if the DLL is not empty) to point to the new node.
If the DLL is empty, set the head pointer to the new node.
The new node is now the tail of the DLL.

Here's an example code for rear insertion in C++:

cpp

void insertAtTail(Node*& head, Node*& tail, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = tail;
    if (head == NULL) {
        head = newNode;
        tail = newNode;
    } else {
        tail->next = newNode;
        tail = tail->next;
    }
}

Quiz Time 💡

That's all for today! With this new knowledge, you're one step closer to mastering DLLs. Keep learning, and happy coding! ✅