Doubly Linked List: Structure and Operations Explained

In this blog, we’ll break down: 

• What a doubly linked list is 
• How it works 
• Its structure 
• Various operations (like insertion and deletion) 
• Real-world applications 
• Interview-relevant code examples 

By the end, you’ll not only understand doubly linked lists you’ll feel confident using them. 

 Want to master DSA with clarity and coding support? 
Join Uncodemy’s Data Structures Course learn from industry experts with live sessions and hands-on practice. 

What is a Doubly Linked List? 

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

1. Data 

2. Pointer to the next node 

3. Pointer to the previous node 

This allows you to traverse the list in both directions forward and backward. 

Visual Representation of a Doubly Linked List 

Here's a simple text-based visualization: 

NULL <- [10 | * | *] <-> [20 | * | *] <-> [30 | * | *] -> NULL 

Each [data | prev | next] box shows a node. 

• The prev pointer of the first node is NULL 
• The next pointer of the last node is NULL 

Structure of a Node in C 

struct Node { 

    int data; 

    struct Node* prev; 

    struct Node* next; 

};

• data holds the actual value. 
• prev points to the previous node. 
• next points to the next node. 

Creating a Node 

struct Node* createNode(int data) { 

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); 

    newNode->data = data; 

    newNode->prev = NULL; 

    newNode->next = NULL; 

    return newNode; 

}

Always allocate memory dynamically to create a new node. 

Insertion Operations 

1. Insert at the Beginning 

void insertAtBeginning(struct Node** head, int data) { 

    struct Node* newNode = createNode(data); 

    newNode->next = *head; 

    if (*head != NULL) 

        (*head)->prev = newNode; 

    *head = newNode; 

}

2. Insert at the End 

void insertAtEnd(struct Node** head, int data) { 

    struct Node* newNode = createNode(data); 

    if (*head == NULL) { 

        *head = newNode; 

        return; 

    } 

    struct Node* temp = *head; 

    while (temp->next != NULL) 

        temp = temp->next; 

    temp->next = newNode; 

    newNode->prev = temp; 

}

3. Insert After a Given Node 

void insertAfter(struct Node* prevNode, int data) { 

    if (prevNode == NULL) return; 

    struct Node* newNode = createNode(data); 

    newNode->next = prevNode->next; 

    prevNode->next = newNode; 

    newNode->prev = prevNode; 

    if (newNode->next != NULL) 

        newNode->next->prev = newNode; 

}

Deletion Operations 

1. Delete From Beginning 

void deleteFromBeginning(struct Node** head) { 

    if (*head == NULL) return; 

    struct Node* temp = *head; 

    *head = (*head)->next; 

    if (*head != NULL) 

        (*head)->prev = NULL; 

    free(temp); 

}

2. Delete From 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); 

}

3. Delete a Specific Node 

void deleteNode(struct Node** head, struct Node* delNode) { 

    if (*head == NULL || delNode == NULL) return; 

    if (*head == delNode) 

        *head = delNode->next; 

    if (delNode->next != NULL) 

        delNode->next->prev = delNode->prev; 

    if (delNode->prev != NULL) 

        delNode->prev->next = delNode->next; 

    free(delNode); 

}

Traversal in a Doubly Linked List 

Forward Traversal 

void printForward(struct Node* head) { 

    struct Node* temp = head; 

    while (temp != NULL) { 

        printf("%d ", temp->data); 

        temp = temp->next; 

    } 

}

Backward Traversal 

void printBackward(struct Node* tail) { 

    struct Node* temp = tail; 

    while (temp != NULL) { 

        printf("%d ", temp->data); 

        temp = temp->prev; 

    } 

}

Advantages of Doubly Linked List 

Disadvantages of Doubly Linked List 

• Takes extra memory for the prev pointer 
• Slightly more complex to manage 
• Increased code size for insertions and deletions 

Real-World Applications 

• Browsers (forward and backward history) 
• Undo/Redo operations in text editors 
• Navigation systems 
• Music playlists with previous/next track buttons 
• Implementation of LRU cache 

Interview Tip 

Common question: 
"What’s the difference between singly and doubly linked lists?" 

Answer: 
Singly linked lists have only a forward pointer, while doubly linked lists have both forward and backward pointers. DLLs allow easier deletion and bidirectional traversal but use more memory. 

FAQs - Doubly Linked List 

Q1. Why use a doubly linked list instead of a singly linked list? 

It allows two-way traversal and efficient deletion from both ends without needing a previous pointer. 

Q2. Is DLL used in real applications? 

Yes, DLLs are heavily used in memory-intensive applications like cache systems, music players, and undo/redo features. 

Q3. How much extra space does a DLL take? 

Each node requires an additional pointer (prev), which doubles the pointer memory usage compared to singly linked lists. 

Q4. What is the time complexity for insertion and deletion? 

Both operations take O(1) time if you already have a reference to the node. 

Q5. Are doubly linked lists implemented in STL? 

Yes, in C++, the std::list container is a doubly linked list implementation. 

Final Thoughts 

Doubly Linked Lists are all about flexibility. While they may take up more memory than singly linked lists, they offer faster and more efficient operations for many real-world use cases. Whether you're building your own text editor or prepping for a tech interview, understanding DLLs will definitely give you an edge. 

Ready to practice with real coding problems and guided projects? 

 Start Learning DSA with Uncodemy