Doubly Linked List B.Tech/BCA Notes 2025 with Code and Examples

A Doubly Linked List (DLL) is a type of linear data structure where each element is represented as a node that contains three parts: a pointer to the previous node, the data field, and a pointer to the next node. This structure allows traversal in both forward and backward directions, making certain operations more efficient than with a singly linked list.

In contrast to a singly linked list, where traversal is only possible in a forward direction, the doubly linked list provides a more versatile and flexible approach to data handling and is widely used in applications such as undo-redo operations in software, navigation systems, and more.

Structure of a Doubly Linked List Node

Each node in a doubly linked list typically consists of:

• prev: A pointer to the previous node.
• data: The data to be stored in the node.
• next: A pointer to the next node.

Node Representation in C:

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

Basic Operations on Doubly Linked List

Let us explore the fundamental operations performed on a doubly linked list:

1. Insertion in a Doubly Linked List

Insertion can be done at the following locations:

• At the beginning
• At the end
• At a specified position

Insertion at the Beginning:

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head != NULL)
        (*head)->prev = newNode;
    *head = newNode;
}

Insertion at the End:

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = newNode;
    newNode->prev = last;
}

Insertion at a Given Position:

void insertAtPosition(struct Node** head, int data, int pos) {
    if (pos == 1) {
        insertAtBeginning(head, data);
        return;
    }
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* temp = *head;
    newNode->data = data;
    for (int i = 1; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;
    if (temp == NULL)
        return;
    newNode->next = temp->next;
    if (temp->next != NULL)
        temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}

2. Deletion in a Doubly Linked List

Similar to insertion, deletion can be done from the:

• Beginning
• End
• A specific position

Deletion from the Beginning:

void deleteFromBeginning(struct Node** head) {
    if (*head == NULL)
        return;
    struct Node* temp = *head;
    *head = temp->next;
    if (*head != NULL)
        (*head)->prev = NULL;
    free(temp);
}

Deletion from the End:

void deleteFromEnd(struct Node** head) {
    if (*head == NULL)
        return;
    struct Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    if (temp->prev != NULL)
        temp->prev->next = NULL;
    else
        *head = NULL;
    free(temp);
}

Deletion from a Specific Position:

void deleteAtPosition(struct Node** head, int pos) {
    if (*head == NULL || pos <= 0)
        return;
    struct Node* temp = *head;
    for (int i = 1; temp != NULL && i < pos; i++)
        temp = temp->next;
    if (temp == NULL)
        return;
    if (temp->prev != NULL)
        temp->prev->next = temp->next;
    else
        *head = temp->next;
    if (temp->next != NULL)
        temp->next->prev = temp->prev;
    free(temp);
}

3. Traversal of a Doubly Linked List

Forward Traversal:

void printForward(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

Backward Traversal:

void printBackward(struct Node* node) {
    struct Node* last = NULL;
    while (node != NULL) {
        last = node;
        node = node->next;
    }
    while (last != NULL) {
        printf("%d ", last->data);
        last = last->prev;
    }
}

📌 Insert Diagram: Doubly Linked List Traversal (Forward and Backward Arrows)

Advantages of Doubly Linked List

• Allows traversal in both directions
• Easier to delete a node when a reference to it is given
• Better utilization in certain operations like insertion and deletion at both ends

Disadvantages of Doubly Linked List

• Requires more memory (extra pointer per node)
• More complex implementation compared to singly linked list

Applications of Doubly Linked List

• Navigation systems (forward and backward navigation)
• Undo and redo functionality in editors
• Implementation of browser history
• Linked data structures like stacks, queues, and deques

Comparison: Singly vs Doubly Linked List

Feature	Singly Linked List	Doubly Linked List
Traversal	Only Forward	Forward and Backward
Memory	Less (1 pointer)	More (2 pointers)
Insertion/Deletion at end	Costlier	Easier
Reverse Traversal	Not possible	Possible

---

🔹 Short Answer Questions (2-3 Marks)

1. What is a doubly linked list? A doubly linked list is a type of linked list where each node contains a pointer to both the previous and next nodes, allowing bidirectional traversal.
2. What are the basic operations on a doubly linked list? Insertion, deletion, and traversal (both forward and backward).
3. State one advantage and one disadvantage of a doubly linked list. Advantage: bidirectional traversal. Disadvantage: more memory required.
4. How does a doubly linked list differ from a singly linked list? A doubly linked list supports traversal in both directions, unlike a singly linked list which only allows forward traversal.
5. What is the time complexity of insertion at the beginning of a DLL? The time complexity is O(1).
6. Is backward traversal possible in a DLL? Yes, because each node has a pointer to the previous node.
7. What does the prev pointer in a DLL point to? It points to the previous node in the list.

🔸 Long Answer Questions (5-10 Marks)

1. Explain the structure and working of a doubly linked list with examples. A DLL contains nodes with three fields: data, prev, and next. The prev field links to the previous node, and the next to the next node, enabling two-way traversal. Example code for insertion and traversal demonstrates its utility in real-world scenarios.
2. Write a program to insert and delete nodes at the beginning and end of a doubly linked list. Explain each step. The program uses dynamic memory allocation. Each insert modifies head and pointer links accordingly. Deletion ensures pointer reassignment to maintain list integrity.
3. Compare and contrast singly linked list and doubly linked list. The primary difference lies in directionality. While singly linked lists are memory-efficient, doubly linked lists offer operational flexibility. A comparative table can be used for clarity.
4. Describe applications of DLL and justify why DLL is preferred in certain systems. DLLs are used in applications requiring bidirectional navigation like editors, music players, and browser history, where moving both forward and backward is essential.
5. Discuss the challenges and solutions involved in implementing a doubly linked list. Challenges include careful pointer handling and memory usage. Solutions involve disciplined code structure, thorough testing, and visualization.

📝 Chapter Summary Doubly Linked List is a linear data structure with forward and backward pointersEach node has three parts: data, prev, and nextInsertions and deletions can occur at beginning, end, or any positionTraversal is possible in both directionsUsed in software systems requiring undo/redo or bidirectional navigationMore memory is required compared to singly linked listOperations are more flexible and powerfulPointer handling is crucial in DLL implementation

📘 Model Paper / Sample Internal Exam Questions

1. Write a C program to insert a node at a specific position in a doubly linked list.
2. Explain the difference between singly and doubly linked lists with diagrams.
3. Describe the traversal mechanism in a doubly linked list and provide code.
4. What are the advantages and disadvantages of a doubly linked list?
5. Compare the time and space complexities of various operations in DLL.