Doubly Linked List Structure and Node Design in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List Node Insertion

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA C

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

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

int main() {
    Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    printList(head);
    return 0;
}

A 10 <-> 20 <-> 30 <-> NULL

B 30 <-> 20 <-> 10 <-> NULL

C 10 -> 20 -> 30 -> NULL

D NULL

💡 Hint

Trace the insertEnd function to see how nodes are linked at the end.

Nodes are inserted at the end, so the list prints from 10 to 30 in order with '<->' showing links.

❓ Predict Output

intermediate

Output after Deleting a Node from Doubly Linked List

Given a doubly linked list with nodes 5 <-> 15 <-> 25 <-> NULL, what is the printed list after deleting the node with value 15?

DSA C

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

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }
    if (temp == NULL) return;
    if (*head == temp) *head = temp->next;
    if (temp->next != NULL) temp->next->prev = temp->prev;
    if (temp->prev != NULL) temp->prev->next = temp->next;
    free(temp);
}

int main() {
    Node* head = createNode(5);
    Node* second = createNode(15);
    Node* third = createNode(25);
    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    deleteNode(&head, 15);
    printList(head);
    return 0;
}

A 5 <-> NULL

B 5 <-> 15 <-> 25 <-> NULL

C 15 <-> 25 <-> NULL

D 5 <-> 25 <-> NULL

💡 Hint

Check how pointers are updated when the node with value 15 is removed.

Deleting node 15 links 5 directly to 25, removing 15 from the list.

🔧 Debug

advanced

Identify the Bug in Node Insertion at Beginning

What is the error in this code that inserts a node at the beginning of a doubly linked list?

DSA C

void insertBeginning(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    // Missing update here
}

A Memory allocation for new node is missing.

B The new node's next pointer is not set correctly.

C The head pointer is not updated to point to the new node.

D The previous pointer of the old head is not updated.

💡 Hint

After inserting at beginning, head must point to new node.

The function forgets to update *head to newNode, so list head remains old node.

❓ Predict Output

advanced

Output of Traversing Doubly Linked List Backwards

Given a doubly linked list 1 <-> 2 <-> 3 <-> NULL, what is the output when traversing from tail to head?

DSA C

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

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

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));

    head->data = 1; head->prev = NULL; head->next = second;
    second->data = 2; second->prev = head; second->next = third;
    third->data = 3; third->prev = second; third->next = NULL;

    printReverse(third);
    return 0;
}

A 3 <-> 2 <-> 1 <-> NULL

B 1 <-> 2 <-> 3 <-> NULL

C NULL

D 1 -> 2 -> 3 -> NULL

💡 Hint

Traverse using prev pointers starting from tail node.

Starting from tail (3), moving prev prints 3, 2, 1 in order.

🧠 Conceptual

expert

Why is a Doubly Linked List More Suitable than Singly Linked List for Certain Operations?

Which reason best explains why doubly linked lists are preferred over singly linked lists for operations like backward traversal and deletion of a given node?

A Because doubly linked lists use less memory than singly linked lists, making them faster.

B Because doubly linked lists store pointers to both previous and next nodes, enabling easy backward traversal and direct node deletion without traversal from head.

C Because doubly linked lists do not require pointers, simplifying node management.

D Because doubly linked lists automatically sort nodes, improving search speed.

💡 Hint

Think about how having two pointers per node helps in navigation and deletion.

Doubly linked lists have prev and next pointers, allowing backward moves and deletion without starting from head.