Doubly Linked List Structure and Node Design in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a pointer to the previous node in a doubly linked list node.

DSA C++

struct Node {
    int data;
    Node* next;
    Node* [1];
};

Drag options to blanks, or click blank then click option'

Abefore

BpreviousNode

Clast

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using longer or uncommon names like 'previousNode' instead of 'prev'.

Using names that do not clearly indicate the previous node.

The standard name for the pointer to the previous node in a doubly linked list is 'prev'.

2fill in blank

medium

Complete the constructor to initialize the data and set both pointers to nullptr.

DSA C++

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

    Node(int val) {
        data = val;
        next = [1];
        prev = [1];
    }
};

Drag options to blanks, or click blank then click option'

Anullptr

BNULL

C0

DNULLPTR

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'NULL' which is legacy and less type-safe.

Using integer 0 which is less clear.

In modern C++, 'nullptr' is used to represent a null pointer safely and clearly.

3fill in blank

hard

Fix the error in the method that sets the next pointer of the current node.

DSA C++

void setNext(Node* node) {
    this->[1] = node;
}

Drag options to blanks, or click blank then click option'

Aprev

Bnext

Cdata

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning to 'prev' instead of 'next'.

Assigning to 'data' which is an int, not a pointer.

To set the next pointer, assign the parameter 'node' to 'this->next'.

4fill in blank

hard

Fill both blanks to correctly link two nodes in a doubly linked list.

DSA C++

void linkNodes(Node* first, Node* second) {
    first->[1] = second;
    second->[2] = first;
}

Drag options to blanks, or click blank then click option'

Anext

Bprev

Cdata

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up 'next' and 'prev' pointers.

Trying to assign to 'data' which is not a pointer.

The first node's next pointer should point to the second node, and the second node's prev pointer should point back to the first node.

5fill in blank

hard

Fill all three blanks to create a new node and link it between two existing nodes.

DSA C++

Node* insertBetween(Node* prevNode, Node* nextNode, int val) {
    Node* newNode = new Node([1]);
    newNode->prev = [2];
    newNode->next = [3];
    return newNode;
}

Drag options to blanks, or click blank then click option'

Aval

BprevNode

CnextNode

Dnullptr

Attempts:

3 left

💡 Hint

Common Mistakes

Passing pointers instead of the value to the constructor.

Mixing up prevNode and nextNode assignments.

The new node is created with the value 'val', its prev pointer set to 'prevNode', and its next pointer set to 'nextNode'.

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