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.

Practice

1. What is the main difference between a doubly linked list node and a singly linked list node?

easy

A. A doubly linked list node has pointers to both the previous and next nodes.

B. A doubly linked list node stores data twice.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node does not store any data.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the next node and one to the previous node.

3. Final Answer:

   A doubly linked list node has pointers to both the previous and next nodes. -> Option A

4. Quick Check:

   Doubly linked list node = two pointers [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Thinking doubly linked nodes store data twice
• Confusing singly and doubly linked list pointers
• Assuming doubly linked nodes have only one pointer

2. Which of the following is the correct C struct definition for a doubly linked list node storing an integer?

easy

A. typedef struct Node { int data; struct Node* next; } Node;

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

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

D. typedef struct Node { int data; struct Node* prev; } Node;

Solution

1. Step 1: Identify required pointers in doubly linked list node

   It must have pointers to both previous and next nodes of type struct Node*.

2. Step 2: Check each option for correct pointer types and members

   typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; correctly defines data, prev, and next pointers as struct Node*.

3. Final Answer:

   typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; -> Option C

4. Quick Check:

   Correct struct has prev and next pointers [OK]

Hint: Doubly linked node needs both prev and next pointers [OK]

Common Mistakes:

• Missing prev pointer in struct
• Using wrong pointer types like int* for nodes
• Defining only one pointer instead of two

3. Consider the following code snippet for a doubly linked list node initialization in C:

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

int main() {
    Node* node = createNode(10);
    printf("%d %p %p", node->data, node->prev, node->next);
    return 0;
}

What will be the output of this program?

medium

A. 10 garbage garbage

B. 10 0x0 0x0

C. 10 NULL NULL

D. Compilation error

Solution

1. Step 1: Analyze node initialization

   Node data is set to 10, prev and next pointers are set to NULL (which is 0x0 in memory).

2. Step 2: Understand printf output for pointers

   Printing pointers with %p shows their memory address; NULL prints as 0x0.

3. Final Answer:

   10 0x0 0x0 -> Option B

4. Quick Check:

   NULL pointers print as 0x0 in %p format [OK]

Hint: NULL pointers print as 0x0 with %p in C [OK]

Common Mistakes:

• Expecting 'NULL' string instead of 0x0
• Assuming garbage values for initialized pointers
• Confusing pointer print format specifiers

4. Identify the error in the following C code snippet for inserting a new node at the beginning of a doubly linked list:

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

medium

A. The condition if (*head != NULL) should be before updating *head.

B. newNode->prev should point to *head, not NULL.

C. The malloc size is incorrect.

D. No error; code is correct.

Solution

1. Step 1: Trace pointer updates

   newNode->next is set to current head, then head is updated to newNode.

2. Step 2: Check the if condition usage

   After updating *head, the condition if (*head != NULL) is always true because *head is newNode. The intention is to update old head's prev pointer.

3. Step 3: Correct order

   The if condition should check if old head (newNode->next) is not NULL before setting its prev pointer.

4. Final Answer:

   The condition if (*head != NULL) should be before updating *head. -> Option A

5. Quick Check:

   Check old head before changing pointers [OK]

Hint: Update old head's prev before changing head pointer [OK]

Common Mistakes:

• Checking *head after it points to newNode
• Setting prev pointer incorrectly
• Ignoring NULL checks before pointer updates

5. You want to design a function to delete a node from a doubly linked list given a pointer to that node. Which of the following steps is NOT required in the deletion process?

hard

A. Free the memory allocated to the node.

B. Update the next node's prev pointer to the node's prev pointer.

C. Update the previous node's next pointer to the node's next pointer.

D. Set the node's data to zero before deletion.

Solution

1. Step 1: Understand deletion in doubly linked list

   To delete a node, update the previous node's next and next node's prev pointers to bypass the node.

2. Step 2: Check necessity of setting data to zero

   Setting the node's data to zero is unnecessary because the node will be freed and memory reclaimed.

3. Step 3: Confirm freeing memory

   Freeing the node's memory is essential to avoid memory leaks.

4. Final Answer:

   Set the node's data to zero before deletion. -> Option D

5. Quick Check:

   Data reset before free is unnecessary [OK]

Hint: Free memory; no need to clear data first [OK]

Common Mistakes:

• Clearing data before freeing memory
• Forgetting to update prev or next pointers
• Not freeing the node memory