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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

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

DSA C++

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insertEnd(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " -> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(10);
    dll.insertEnd(20);
    dll.insertEnd(30);
    dll.printList();
    return 0;
}

A 30 <-> 20 <-> 10 -> null

B 10 -> 20 -> 30 -> null

C 10 <-> 20 <-> 30 -> null

D null

💡 Hint

Remember that insertEnd adds nodes at the tail, so the order is the same as insertion.

Nodes are inserted at the end, so the list prints 10, then 20, then 30 connected by <-> arrows, ending with -> null.

🧠 Conceptual

intermediate

Understanding Node Pointers in Doubly Linked List

In a doubly linked list node, which pointers are used to navigate the list?

A No pointers, only data

B A pointer to the next node only

C A pointer to the previous node only

D A pointer to the next node and a pointer to the previous node

💡 Hint

Think about how you can move forward and backward in the list.

A doubly linked list node has two pointers: one to the next node and one to the previous node, allowing traversal in both directions.

🔧 Debug

advanced

Identify the Bug in Node Deletion Code

What error will occur when deleting the head node in this doubly linked list code snippet?

DSA C++

void deleteHead() {
    if (!head) return;
    Node* temp = head;
    head = head->next;
    head->prev = nullptr;
    delete temp;
}

A No error, deletion works correctly

B Runtime error due to dereferencing nullptr when list has one node

C Compilation error due to missing return type

D Memory leak because node is not deleted

💡 Hint

What happens if the list has only one node?

If the list has one node, after head = head->next, head becomes nullptr. Then head->prev causes a runtime error (nullptr dereference).

❓ Predict Output

advanced

Result of Reversing a Doubly Linked List

What is the printed state of the doubly linked list after reversing it?

DSA C++

void reverseList(Node*& head) {
    Node* temp = nullptr;
    Node* current = head;
    while (current) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp) head = temp->prev;
}

int main() {
    DoublyLinkedList dll;
    dll.insertEnd(1);
    dll.insertEnd(2);
    dll.insertEnd(3);
    reverseList(dll.head);
    dll.printList();
    return 0;
}

A 3 <-> 2 <-> 1 -> null

B 1 <-> 2 <-> 3 -> null

C null

D 1 -> 2 -> 3 -> null

💡 Hint

Reversing swaps next and prev pointers for each node and updates head.

After reversing, the list order is reversed, so it prints 3 <-> 2 <-> 1 -> null.

🧠 Conceptual

expert

Memory Management in Doubly Linked List Node Deletion

When deleting a node from a doubly linked list, which step is crucial to avoid memory leaks and dangling pointers?

A Update the previous node's next pointer and the next node's prev pointer, then delete the node

B Only delete the node without updating any pointers

C Set the node's data to zero before deleting

D Update only the previous node's next pointer, ignore the next node's prev pointer

💡 Hint

Think about how the list stays connected after removal.

To safely remove a node, pointers of adjacent nodes must be updated to bypass the node, then the node memory is freed.

Practice

1. What is the main advantage of a doubly linked list over a singly linked list?

easy

A. It can only be traversed forward.

B. It uses less memory than a singly linked list.

C. It requires only one pointer per node.

D. It allows traversal in both forward and backward directions.

Solution

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

   Each node has two pointers: one to the next node and one to the previous node.

2. Step 2: Compare traversal capabilities

   This allows moving forward and backward through the list, unlike singly linked lists which only allow forward traversal.

3. Final Answer:

   It allows traversal in both forward and backward directions. -> Option D

4. Quick Check:

   Doubly linked list = two-way traversal [OK]

Hint: Remember: two pointers mean two directions [OK]

Common Mistakes:

• Thinking it uses less memory than singly linked list
• Assuming it has only one pointer per node
• Believing it can only traverse forward

2. Which of the following is the correct way to declare a node structure for a doubly linked list in C++?

easy

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

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

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

D. struct Node { int data; int next; int prev; };

Solution

1. Step 1: Check pointer usage for next and prev

   In a doubly linked list, next and prev must be pointers to Node, so Node* next and Node* prev are correct.

2. Step 2: Identify incorrect declarations

   struct Node { int data; Node next; Node prev; }; uses Node next and Node prev (not pointers), C uses int prev, and D uses int for both next and prev, which is incorrect.

3. Final Answer:

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

4. Quick Check:

   Pointers for next and prev = struct Node { int data; Node* next; Node* prev; }; [OK]

Hint: Pointers to Node must use * symbol [OK]

Common Mistakes:

• Using Node instead of Node* for next and prev
• Using int type for pointers
• Missing pointer symbols

3. Consider the following code snippet for a doubly linked list node insertion at the front:

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

Node* head = nullptr;

Node* newNode = new Node{10, nullptr, nullptr};
newNode->next = head;
if (head != nullptr) {
  head->prev = newNode;
}
head = newNode;

// What is the data in head->next after insertion?

medium

A. nullptr

B. 10

C. Undefined

D. Garbage value

Solution

1. Step 1: Analyze initial head value

   Initially, head is nullptr, meaning the list is empty.

2. Step 2: After insertion, newNode->next points to old head (nullptr)

   Since head was nullptr, newNode->next is set to nullptr, so head->next is nullptr after insertion.

3. Final Answer:

   nullptr -> Option A

4. Quick Check:

   Empty list insertion sets next to nullptr [OK]

Hint: New node next points to old head, which is nullptr here [OK]

Common Mistakes:

• Assuming head->next has data 10
• Thinking head->next is undefined or garbage
• Ignoring initial nullptr head

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

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

void insertEnd(Node*& head, int val) {
  Node* newNode = new Node{val, nullptr, nullptr};
  if (head == nullptr) {
    head = newNode;
    return;
  }
  Node* temp = head;
  while (temp->next != nullptr) {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->prev = nullptr;
}

medium

A. temp should be initialized to nullptr.

B. head should be passed by value, not reference.

C. newNode->prev should point to temp, not nullptr.

D. newNode->next should point to head.

Solution

1. Step 1: Check newNode's prev pointer assignment

   After finding the last node (temp), newNode is added after temp, so newNode->prev must point to temp.

2. Step 2: Identify incorrect assignment

   Code sets newNode->prev = nullptr, which breaks backward link; it should be newNode->prev = temp.

3. Final Answer:

   newNode->prev should point to temp, not nullptr. -> Option C

4. Quick Check:

   Prev pointer links new node to last node [OK]

Hint: Prev of new node = last node before insertion [OK]

Common Mistakes:

• Setting newNode->prev to nullptr instead of last node
• Passing head by value losing list updates
• Incorrect initialization of temp pointer

5. You want to design a function to delete a node from a doubly linked list given a pointer to that node (not the head). Which pointer updates are necessary to maintain list integrity?

hard

A. No pointer updates needed; just delete the node.

B. Set node's prev->next to node's next and node's next->prev to node's prev.

C. Set node's prev to nullptr and node's next to nullptr only.

D. Set node's next->next to node's prev and node's prev->prev to node's next.

Solution

1. Step 1: Understand node removal in doubly linked list

   To remove a node, the previous node's next pointer must skip the node and point to node's next.

2. Step 2: Update next node's prev pointer

   Similarly, the next node's prev pointer must skip the node and point to node's prev.

3. Final Answer:

   Set node's prev->next to node's next and node's next->prev to node's prev. -> Option B

4. Quick Check:

   Prev and next pointers bypass deleted node [OK]

Hint: Link prev and next nodes directly to remove node [OK]

Common Mistakes:

• Not updating both prev and next pointers
• Setting wrong pointers to nullptr
• Deleting node without fixing links