DSA SERIES – DOUBLY LINKED LIST IN C

1. What is a Doubly Linked List?

A Doubly Linked List (DLL) is a linear, dynamic data structure where each node contains:

Data
A pointer to the next node (next)
A pointer to the previous node (prev)

This allows bidirectional traversal, which is impossible in a singly linked list.

Key Advantages Over Singly Linked List:

O(1) deletion anywhere (because you can access previous node directly)
Reverse traversal is possible
Better for applications requiring backtracking: editors, undo-redo, music playlist navigation, browser navigation

Drawback:

Extra memory for prev pointer
Slightly complex logic compared to singly LL

2. Node Structure in C (Deep Explanation)

struct Node {
    int data;
    struct Node* prev;   // Points to the previous node
    struct Node* next;   // Points to the next node
};

Memory Layout of a DLL Node (64-bit system)

Field	Size
int data	4 bytes
prev pointer	8 bytes
next pointer	8 bytes
Total per node	20 bytes (aligned to 24 bytes)

Why alignment to 24 bytes?

Most compilers align struct sizes to multiples of 8 bytes for faster access on 64-bit systems.
So although the raw field total is 20 bytes, actual memory used becomes 24 bytes.

3. Dynamic Memory Allocation of Node

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

What exactly happens internally?

malloc() requests memory from the heap.
Heap manager finds a contiguous free block of 24 bytes (aligned).
Returns a void* → typecasted to struct Node*.
Programmer initializes data, prev, next.

4. Visual Structure of a Doubly Linked List

For a list: 10 ⇄ 20 ⇄ 30

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

Each node points both ways.

5. Core Operations of Doubly Linked List (C Version)

Each operation is explained with:

Code
Logic
Memory behavior
Time complexity

A. Insert at Beginning

void insertAtBegin(struct Node** head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = *head;

    if (*head != NULL)
        (*head)->prev = newNode;

    *head = newNode;
}

Core Idea:

New node becomes the head.
If old head exists, connect its prev to newNode.
Maintains bidirectional structure.

Complexity:

Time: O(1)
Space: O(1)

B. Insert at End

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;
}

Memory Movement:

Traversal is always forward (next).
Attachment requires updating both:

temp->next = newNode
newNode->prev = temp

C. Insert at Any Position

void insertAtPos(struct Node** head, int value, int pos) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;

    if (pos == 1) {
        newNode->prev = NULL;
        newNode->next = *head;

        if (*head != NULL)
            (*head)->prev = newNode;

        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    for (int i = 1; i < pos - 1; i++) {
        if (temp == NULL) return; // invalid 
        temp = temp->next;
    }

    newNode->next = temp->next;
    newNode->prev = temp;

    if (temp->next != NULL)
        temp->next->prev = newNode;

    temp->next = newNode;
}

Deep Understanding:

DLL insertion at any position is easier than singly LL because:

You always know the node before insertion (temp)
Can update pointer links clearly

D. Deleting the First Node

void deleteBegin(struct Node** head) {
    if (*head == NULL) return;

    struct Node* temp = *head;
    *head = temp->next;

    if (*head != NULL)
        (*head)->prev = NULL;

    free(temp);
}

Memory Released:

free(temp) returns the 24-byte aligned block to heap.

E. Delete Last Node

void deleteEnd(struct Node** head) {
    if (*head == NULL) return;

    struct Node* temp = *head;

    if (temp->next == NULL) {
        free(temp);
        *head = NULL;
        return;
    }

    while (temp->next != NULL)
        temp = temp->next;

    temp->prev->next = NULL;
    free(temp);
}

Why DLL deletion at end is easier?

No need to track second-last node separately.
temp->prev gives it directly.

F. Delete at Any Position

void deleteAtPos(struct Node** head, int pos) {
    if (*head == NULL) return;

    struct Node* temp = *head;

    if (pos == 1) {
        *head = temp->next;

        if (*head != NULL)
            (*head)->prev = NULL;

        free(temp);
        return;
    }

    for (int i = 1; i < pos; i++) {
        if (temp == NULL) return;
        temp = temp->next;
    }

    temp->prev->next = temp->next;

    if (temp->next != NULL)
        temp->next->prev = temp->prev;

    free(temp);
}

6. Traversal of Doubly Linked List

Forward Traversal

void displayForward(struct Node* head) {
    while (head != NULL) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

Backward Traversal

void displayReverse(struct Node* head) {
    struct Node* temp = head;
    if (temp == NULL) return;

    while (temp->next != NULL)
        temp = temp->next;

    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}

7. Complete C Program for Doubly Linked List

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

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

void insertAtBegin(struct Node** head, int value);
void insertAtEnd(struct Node** head, int value);
void displayForward(struct Node* head);
void displayReverse(struct Node* head);

int main() {
    struct Node* head = NULL;

    insertAtBegin(&head, 30);
    insertAtBegin(&head, 20);
    insertAtBegin(&head, 10);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);

    printf("Forward: ");
    displayForward(head);

    printf("Reverse: ");
    displayReverse(head);

    return 0;
}

8. Time & Space Analysis

Operation	Time	Space
Insert at beginning	O(1)	O(1)
Insert at end	O(n)	O(1)
Insert at position	O(n)	O(1)
Delete beginning	O(1)	O(1)
Delete end	O(n)	O(1)
Delete at position	O(n)	O(1)
Traverse forward	O(n)	O(1)
Traverse backward	O(n)	O(1)

9. Professional Insights (Engineering-Level)

When to prefer DLL over SLL?

Frequent backtracking
When deletion in middle is needed frequently
When working with navigation-based structures

Where used?

Browser forward/backward
Undo/redo systems
Media player playlist
Tab navigation
Memory management systems

Exercises on Doubly Linked List (C Version)

SECTION 1 — BASIC LEVEL (10 Questions)

Create a DLL and insert 5 elements using Insert-at-End. Display the list in forward direction.
Create a DLL and insert 5 elements using Insert-at-Beginning. Display forward and backward.
Write a program to count the number of nodes in a DLL.
Write a function to search an element in a DLL. Return its position if found.
Delete the first node of a DLL and display the updated list.
Delete the last node of a DLL and display the updated list.
Insert an element at a given position (pos). Validate for invalid positions.
Create a DLL of 7 nodes. Print only even numbers from the DLL.
Create a DLL of characters and display it in reverse order.
Check whether a DLL is empty or not and print an appropriate message.

SECTION 2 — INTERMEDIATE LEVEL (10 Questions)

Write a function to delete a node at a given position in a DLL (pos).
Given a DLL, find the largest and smallest elements without converting to array.
Reverse a DLL by changing links (not by swapping data).
Create two DLLs. Merge them into a single DLL (append second at end).
Insert a node after a node containing a given key.
Delete a node just before a given key in a DLL.
Delete a node just after a given key in a DLL.
Check whether the DLL is palindrome (without extra array).
Given a sorted DLL, insert a new element maintaining the sorted order.
Count occurrences of a given number in a DLL.

SECTION 3 — ADVANCED LEVEL (10 Questions)

(These questions require deep pointer handling & conceptual understanding)

Implement DLL using a structure containing: data, prev, next, and an extra pointer “mid” which points to the middle of the list (update “mid” during insertions).
Implement a Doubly Linked List that supports O(1) insertion at both ends and O(1) deletion from both ends (like a DEQUE using DLL).
Rotate a DLL left by k positions.
Rotate a DLL right by k positions.
Given a DLL, split it into two equal halves.
Flatten a multilevel DLL (each node may contain a child pointer pointing to another DLL).
Convert a DLL into a circular DLL and back to a normal DLL.
Convert a DLL into a binary search tree (BST) without using an array.
Given two sorted DLLs, merge them into one sorted DLL (like merge step of merge-sort).
Reverse a DLL in groups of size k (like reversing linked list in k-groups).

SECTION 4 — Real-World Scenario-Based Questions (10 Questions)

(For engineering professionals, interview-oriented)

Implement a browser system using DLL where users can move forward/backward through pages.
Design an Undo-Redo system using two DLLs.
Music player playlist navigation using DLL where user can move next/previous.
Tab navigation system using DLL where closing a tab deletes the current node.
Implement LRU Cache using DLL + Hashing (explain DLL role clearly).
Given a DLL storing train bogie numbers, insert a new bogie before a specific bogie.
Implement a customer-service ticket system with priority-based DLL ordering.
Implement a queue using DLL with O(1) enqueue and dequeue.
Represent a polynomial expression using DLL. Perform addition of two polynomials.
Implement a “time-travel debugging” model where execution frames are stored in DLL nodes.