Insert at Beginning of Doubly Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting 10 at the beginning?

Consider a doubly linked list initially containing nodes with values 20 -> 30 -> 40 -> null. We insert a new node with value 10 at the beginning. What is the printed list after this operation?

DSA C++

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

void insertAtBeginning(Node*& head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->prev = nullptr;
    newNode->next = head;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

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

int main() {
    Node* head = new Node{20, nullptr, nullptr};
    head->next = new Node{30, head, nullptr};
    head->next->next = new Node{40, head->next, nullptr};

    insertAtBeginning(head, 10);
    printList(head);
    return 0;
}

A 20 -> 30 -> 40 -> 10 -> null

B 10 -> 30 -> 40 -> null

C 10 -> 20 -> 30 -> 40 -> null

D 20 -> 10 -> 30 -> 40 -> null

💡 Hint

Remember, inserting at the beginning means the new node becomes the head and points to the old head.

The new node with value 10 is inserted before the current head (20). So the list becomes 10 -> 20 -> 30 -> 40 -> null.

❓ Predict Output

intermediate

What is the output after inserting 5 at the beginning of an empty list?

Given an empty doubly linked list (head is nullptr), we insert a node with value 5 at the beginning. What is the printed list after this operation?

DSA C++

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

void insertAtBeginning(Node*& head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->prev = nullptr;
    newNode->next = head;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

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

int main() {
    Node* head = nullptr;
    insertAtBeginning(head, 5);
    printList(head);
    return 0;
}

A 5 -> null

B null

C 0 -> 5 -> null

D 5 -> 0 -> null

💡 Hint

Inserting into an empty list creates a single node which is the head.

Since the list was empty, the new node with value 5 becomes the only node and head of the list.

🔧 Debug

advanced

Identify the bug in this insertAtBeginning function

The following code attempts to insert a node at the beginning of a doubly linked list. What is the bug that will cause incorrect behavior?

DSA C++

void insertAtBeginning(Node*& head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->prev = head;
    newNode->next = nullptr;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

A newNode->next should be nullptr, not head

B newNode->prev should be nullptr, not head

C head->prev should not be set at all

D head should not be updated to newNode

💡 Hint

The previous pointer of the new head node should point to nothing before it.

When inserting at the beginning, the new node's prev pointer must be nullptr because it becomes the first node. Setting it to head is wrong.

❓ Predict Output

advanced

What is the output after multiple insertions at beginning?

Starting with an empty doubly linked list, we insert 3, then 2, then 1 at the beginning in that order. What is the printed list after these operations?

DSA C++

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

void insertAtBeginning(Node*& head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->prev = nullptr;
    newNode->next = head;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

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

int main() {
    Node* head = nullptr;
    insertAtBeginning(head, 3);
    insertAtBeginning(head, 2);
    insertAtBeginning(head, 1);
    printList(head);
    return 0;
}

A 2 -> 1 -> 3 -> null

B 3 -> 2 -> 1 -> null

C 3 -> 1 -> 2 -> null

D 1 -> 2 -> 3 -> null

💡 Hint

Each new insertion at beginning becomes the new head.

Inserting 3 first makes list 3 -> null, then 2 at beginning makes 2 -> 3 -> null, then 1 at beginning makes 1 -> 2 -> 3 -> null.

🧠 Conceptual

expert

Why must the previous pointer of the old head be updated when inserting at beginning?

When inserting a new node at the beginning of a doubly linked list, why is it necessary to update the previous pointer of the old head node to point to the new node?

A To maintain the backward link so traversal from tail to head works correctly

B To avoid memory leaks by freeing the old head node

C To ensure the new node's next pointer is not null

D To prevent the list from becoming circular

💡 Hint

Think about how doubly linked lists allow moving backwards.

The previous pointer of the old head must point to the new node to keep the backward links intact, enabling traversal from tail to head.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To delete the first node of the list

B. To add a new node before the current head node

C. To add a new node after the tail node

D. To reverse the entire list

Solution

1. Step 1: Understand the head node position

   The head node is the first node in the doubly linked list.

2. Step 2: Insert new node before head

   Inserting at the beginning means placing the new node before the current head and updating pointers.

3. Final Answer:

   To add a new node before the current head node -> Option B

4. Quick Check:

   Insert at beginning = Add before head [OK]

Hint: Insert at beginning means new node becomes the head [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Not updating the previous head's previous pointer
• Trying to delete instead of insert

2. Which of the following is the correct syntax to create a new node and insert it at the beginning of a doubly linked list in C++?

easy

A. Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode;

B. Node newNode = Node(data); newNode->next = head; head = newNode;

C. Node* newNode = new Node(data); head->next = newNode; newNode->prev = head; head = newNode;

D. Node* newNode = new Node(data); newNode->next = head; head = newNode;

Solution

1. Step 1: Create new node with pointer

   Use pointer syntax: Node* newNode = new Node(data);

2. Step 2: Update pointers for doubly linked list

   Set newNode->next to current head, update head->prev to newNode, then update head to newNode.

3. Final Answer:

   Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode; -> Option A

4. Quick Check:

   Correct pointer updates = Node* newNode = new Node(data); head->prev = newNode; newNode->next = head; head = newNode; [OK]

Hint: Remember to update both next and prev pointers [OK]

Common Mistakes:

• Using object instead of pointer for new node
• Not updating head->prev pointer
• Swapping next and prev pointers incorrectly

3. What will be the output of the following code snippet after inserting 10 at the beginning of the doubly linked list?

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

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

Node* newNode = new Node(10);
newNode->next = head;
head->prev = newNode;
head = newNode;

// Print list from head
Node* temp = head;
while(temp) {
  std::cout << temp->data << " -> ";
  temp = temp->next;
}
std::cout << "null";

medium

A. 30 -> 20 -> 10 -> null

B. 20 -> 30 -> 10 -> null

C. 10 -> 20 -> 30 -> null

D. 10 -> 30 -> 20 -> null

Solution

1. Step 1: Initial list setup

   List initially: 20 <-> 30, head points to 20.

2. Step 2: Insert 10 at beginning

   New node 10 points next to 20, 20's prev points to 10, head updated to 10.

3. Step 3: Print list from head

   Traverse from head: 10 -> 20 -> 30 -> null

4. Final Answer:

   10 -> 20 -> 30 -> null -> Option C

5. Quick Check:

   New head is 10, followed by 20 and 30 [OK]

Hint: New node becomes head, old head shifts right [OK]

Common Mistakes:

• Not updating head pointer after insertion
• Incorrect pointer assignments causing wrong order
• Printing from tail instead of head

4. Identify the error in the following code snippet that inserts a node at the beginning of a doubly linked list:

void insertAtBeginning(Node*& head, int data) {
  Node* newNode = new Node(data);
  newNode->next = head;
  head->prev = newNode;
  head = newNode;
}

medium

A. newNode->prev should be set to head

B. newNode->next should be set to nullptr

C. head pointer should not be passed by reference

D. Missing check if head is nullptr before accessing head->prev

Solution

1. Step 1: Analyze pointer usage

   Code accesses head->prev without checking if head is nullptr (empty list).

2. Step 2: Identify potential runtime error

   If head is nullptr, accessing head->prev causes a crash (null pointer dereference).

3. Final Answer:

   Missing check if head is nullptr before accessing head->prev -> Option D

4. Quick Check:

   Always check head != nullptr before head->prev [OK]

Hint: Check if list is empty before updating pointers [OK]

Common Mistakes:

• Ignoring nullptr checks causing crashes
• Incorrect pointer assignments for prev
• Passing head by value instead of reference

5. Given a doubly linked list with nodes containing values [5, 15, 25], write the sequence of node values after inserting 1 at the beginning and then 35 at the beginning. What is the final list?

hard

A. 35 -> 1 -> 5 -> 15 -> 25 -> null

B. 1 -> 35 -> 5 -> 15 -> 25 -> null

C. 5 -> 15 -> 25 -> 1 -> 35 -> null

D. 35 -> 5 -> 15 -> 25 -> 1 -> null

Solution

1. Step 1: Initial list

   List is 5 -> 15 -> 25 -> null.

2. Step 2: Insert 1 at beginning

   New head is 1, list becomes 1 -> 5 -> 15 -> 25 -> null.

3. Step 3: Insert 35 at beginning

   New head is 35, list becomes 35 -> 1 -> 5 -> 15 -> 25 -> null.

4. Final Answer:

   35 -> 1 -> 5 -> 15 -> 25 -> null -> Option A

5. Quick Check:

   Last inserted node is new head [OK]

Hint: Last inserted node at beginning becomes new head [OK]

Common Mistakes:

• Inserting nodes at end instead of beginning
• Not updating head pointer after each insertion
• Mixing order of inserted nodes