Node Structure and Pointer Design in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linked List Node Insertion

What is the printed output of the linked list after inserting nodes in this order?

DSA C++

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

Node* head = new Node(1);
head->next = new Node(2);
Node* temp = new Node(3);
temp->next = head->next;
head->next = temp;

Node* curr = head;
while (curr != nullptr) {
    std::cout << curr->data << " -> ";
    curr = curr->next;
}
std::cout << "null";

A 1 -> 3 -> 2 -> null

B 1 -> 2 -> 3 -> null

C 3 -> 1 -> 2 -> null

D 1 -> null

💡 Hint

Think about how the new node is inserted between existing nodes.

The new node with value 3 is inserted between nodes with values 1 and 2. So the list becomes 1 -> 3 -> 2 -> null.

❓ Predict Output

intermediate

Output after Reversing a Simple Linked List

What is the output of the linked list after reversing it using the given code?

DSA C++

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

Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);

Node* prev = nullptr;
Node* curr = head;
Node* next = nullptr;
while (curr != nullptr) {
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
head = prev;

Node* temp = head;
while (temp != nullptr) {
    std::cout << temp->data << " -> ";
    temp = temp->next;
}
std::cout << "null";

A 30 -> 20 -> 10 -> null

B null

C 10 -> 20 -> 30 -> null

D 10 -> null

💡 Hint

Reversing changes the direction of the pointers.

The code reverses the linked list by changing the next pointers to point backward. The original list 10 -> 20 -> 30 -> null becomes 30 -> 20 -> 10 -> null.

🧠 Conceptual

advanced

Pointer Design in Doubly Linked List

In a doubly linked list node structure, which pointer setup correctly allows traversal in both directions?

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

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

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

D struct Node { int data; Node* next; Node* child; };

💡 Hint

Think about what pointers are needed to move forward and backward.

A doubly linked list node needs two pointers: one to the previous node and one to the next node to allow traversal in both directions.

🔧 Debug

advanced

Identify the Bug in Node Pointer Assignment

What error occurs when running this code snippet for a singly linked list node insertion?

DSA C++

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

Node* head = nullptr;
Node* newNode = new Node(5);
newNode->next = head;
head = newNode;

// Insert another node
Node* anotherNode = new Node(10);
head->next = anotherNode;
anotherNode->next = nullptr;

// Incorrect insertion
Node* wrongNode = new Node(15);
wrongNode->next = head;
head = wrongNode;
head->next->next = nullptr;

A No error, list is 15 -> 5 -> 10 -> null

B Runtime error: nullptr dereference

C Logical error: list loses node with value 10

D Compilation error: invalid pointer assignment

💡 Hint

Check what happens to the node with value 10 after the last insertion.

The last insertion sets head to wrongNode (15), whose next points to old head (5). But then head->next->next is set to nullptr, which breaks the link to node 10, losing it from the list.

🚀 Application

expert

Designing a Circular Linked List Node Structure

Which node pointer design best supports a circular singly linked list where the last node points back to the head?

A struct Node { int data; Node* next; Node* tail; }; // tail pointer inside each node

B struct Node { int data; Node* prev; Node* next; }; // circular doubly linked list

C struct Node { int data; Node* next; Node* random; }; // random pointer for arbitrary jumps

D struct Node { int data; Node* next; }; // last node's next points to head

💡 Hint

Focus on the minimal pointer needed for circular singly linked list.

A circular singly linked list requires only one pointer per node (next). The last node's next points back to the head, forming a circle.

Practice

1. What is the main purpose of a next pointer in a singly linked list node structure?

easy

A. To store the data value of the node

B. To keep track of the size of the list

C. To point to the previous node in the list

D. To store the address of the next node in the list

Solution

1. Step 1: Understand the role of pointers in linked lists

   In a singly linked list, each node contains data and a pointer to the next node.

2. Step 2: Identify the function of the next pointer

   The next pointer stores the address of the next node, allowing traversal through the list.

3. Final Answer:

   To store the address of the next node in the list -> Option D

4. Quick Check:

   next pointer = address of next node [OK]

Hint: Next pointer always links to the next node in the chain [OK]

Common Mistakes:

• Confusing data storage with pointer storage
• Thinking next points to previous node
• Assuming next stores list size

2. Which of the following is the correct syntax to define a node structure with an integer data and a pointer to the next node in C++?

easy

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

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

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

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

Solution

1. Step 1: Recall pointer declaration syntax in C++

   To declare a pointer to a type, use the syntax TypeName* pointerName;.

2. Step 2: Check each option for correct pointer syntax

   struct Node { int data; Node* next; }; correctly declares Node* next; as a pointer to a Node. Others have syntax errors.

3. Final Answer:

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

4. Quick Check:

   Pointer syntax = TypeName* [OK]

Hint: Pointer syntax always uses * after type name [OK]

Common Mistakes:

• Omitting the * for pointer declaration
• Placing * before variable name incorrectly
• Using variable name before type

3. What will be the output of the following C++ code snippet?

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

int main() {
  Node a = {10, nullptr};
  Node b = {20, nullptr};
  a.next = &b;
  std::cout << a.next->data << std::endl;
  return 0;
}

medium

A. 20

B. 10

C. Address of b

D. Compilation error

Solution

1. Step 1: Understand the node initialization and linking

   Node a has data 10 and next initially null. Node b has data 20. Then a.next points to b.

2. Step 2: Trace the output statement

   a.next->data accesses the data of the node pointed by a.next, which is b with value 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Pointer access a.next->data = 20 [OK]

Hint: Arrow operator accesses member via pointer [OK]

Common Mistakes:

• Printing a.data instead of a.next->data
• Confusing pointer dereference syntax
• Expecting address instead of data

4. Identify the error in the following node structure code snippet:

struct Node {
  int data;
  Node next;
};

medium

A. Missing semicolon after struct definition

B. Data member should be a pointer

C. Pointer to next node should be declared as Node* next;

D. Struct cannot contain another struct

Solution

1. Step 1: Analyze the declaration of next member

   The member next is declared as Node next;, which means it contains a full Node inside itself, causing infinite size.

2. Step 2: Correct pointer declaration

   To link nodes, next must be a pointer: Node* next; to store address of another node.

3. Final Answer:

   Pointer to next node should be declared as Node* next; -> Option C

4. Quick Check:

   Next node must be pointer type [OK]

Hint: Next node must be pointer, not full struct [OK]

Common Mistakes:

• Declaring next as full struct causes infinite recursion
• Forgetting * in pointer declaration
• Confusing pointer and object types

5. You want to design a doubly linked list node structure in C++ that stores an integer and has pointers to both previous and next nodes. Which of the following is the correct definition?

hard

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

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

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

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

Solution

1. Step 1: Understand doubly linked list node requirements

   Each node must have data and two pointers: one to previous node and one to next node.

2. Step 2: Check pointer declarations for both prev and next

   Both prev and next must be pointers to Node, declared as Node* prev; and Node* next;.

3. Final Answer:

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

4. Quick Check:

   Both prev and next are pointers [OK]

Hint: Both prev and next must be pointers in doubly linked list [OK]

Common Mistakes:

• Declaring prev or next as full Node instead of pointer
• Mixing pointer and non-pointer types
• Forgetting one of the pointers